要证明欧拉函数是积性函数,我们需要理解两个核心概念:欧拉函数 (Euler's totient function) 和 积性函数 (Multiplicative function)。一旦我们清晰地掌握了这两个概念,证明过程就会变得相当直观。
一、 理解欧拉函数 $phi(n)$
首先,让我们回顾一下欧拉函数 $phi(n)$ 的定义。对于一个正整数 $n$,$phi(n)$ 的值等于所有小于或等于 $n$ 且与 $n$ 互质的正整数的个数。
举个例子:
$phi(1) = 1$ (只有 1 与 1 互质)
$phi(2) = 1$ (只有 1 与 2 互质)
$phi(3) = 2$ (1, 2 与 3 互质)
$phi(4) = 2$ (1, 3 与 4 互质)
$phi(5) = 4$ (1, 2, 3, 4 与 5 互质)
$phi(6) = 2$ (1, 5 与 6 互质)
二、 理解积性函数
一个数论函数 $f(n)$ 被称为积性函数,如果对于任意两个互质的正整数 $m$ 和 $n$(即 $gcd(m, n) = 1$),都有:
$f(mn) = f(m)f(n)$
简单来说,积性函数在处理乘积时具有“乘法分配律”的性质,前提是这两个乘数必须是互质的。
三、 证明欧拉函数是积性函数
现在,我们的目标是证明对于任意互质的正整数 $m$ 和 $n$,满足 $phi(mn) = phi(m)phi(n)$。
为了做到这一点,我们将构造性地考虑小于 $mn$ 且与 $mn$ 互质的数的个数,并将它们与小于 $m$ 且与 $m$ 互质的数,以及小于 $n$ 且与 $n$ 互质的数联系起来。
证明的核心思想:利用中国剩余定理 (Chinese Remainder Theorem, CRT)
中国剩余定理是一个非常强大的工具,它告诉我们如何处理模数互质的同余方程组。它与我们证明欧拉函数积性性质的思路高度契合。
证明步骤:
1. 考虑数对 $(x, y)$ 的对应关系:
我们知道,对于任意正整数 $k$,如果 $k$ 与 $mn$ 互质,那么 $k$ 必须同时与 $m$ 和 $n$ 互质。反之,如果 $k$ 与 $m$ 互质,并且 $k$ 与 $n$ 互质,那么 $k$ 也一定与 $mn$ 互质。
这是因为如果一个素数 $p$ 整除 $k$ 和 $mn$,那么 $p$ 必须整除 $m$ 或者 $n$。如果 $k$ 与 $mn$ 互质,意味着不存在这样的素数 $p$ 同时整除 $k$ 和 $mn$。如果 $p$ 整除 $m$,$k$ 与 $m$ 互质就意味着 $p$ 不能整除 $k$。同样,如果 $p$ 整除 $n$,$k$ 与 $n$ 互质也意味着 $p$ 不能整除 $k$。因此,$k$ 与 $m$ 和 $n$ 都互质。
2. 构造一个映射:
让我们考虑所有小于 $mn$ 的正整数 $k$,满足 $gcd(k, mn) = 1$。
根据中国剩余定理,我们可以建立一个从这些数 $k$ 到数对 $(x, y)$ 的一个一一对应(双射)。具体来说,对于每一个满足 $gcd(k, mn) = 1$ 的整数 $k$(其中 $1 le k < mn$),我们可以将其表示为:
$k equiv x pmod{m}$
$k equiv y pmod{n}$
其中,$0 le x < m$ 和 $0 le y < n$。
为什么是这样映射的?
中国剩余定理告诉我们,对于任意给定的同余类 $x pmod m$ 和 $y pmod n$,只要 $gcd(m, n) = 1$,就存在一个唯一的整数 $k$ 模 $mn$ 满足这两个同余条件。
3. 分析映射的性质:
关键在于,这个映射保持了互质性。
如果 $gcd(k, mn) = 1$,那么根据上面的推论,我们知道 $gcd(k, m) = 1$ 且 $gcd(k, n) = 1$。
从同余关系 $k equiv x pmod m$ 可知,$gcd(k, m) = gcd(x, m)$。因此,如果 $gcd(k, m) = 1$,那么 $gcd(x, m) = 1$。
同理,从同余关系 $k equiv y pmod n$ 可知,$gcd(k, n) = gcd(y, n)$。因此,如果 $gcd(k, n) = 1$,那么 $gcd(y, n) = 1$。
反过来,如果 $gcd(x, m) = 1$ 且 $gcd(y, n) = 1$,根据中国剩余定理,存在唯一的 $k$ 模 $mn$ 满足 $k equiv x pmod m$ 和 $k equiv y pmod n$。而这个唯一的 $k$ 也必定满足 $gcd(k, mn) = 1$。
所以,我们可以建立一个从 ${k mid 1 le k < mn, gcd(k, mn) = 1}$ 到 ${(x, y) mid 0 le x < m, gcd(x, m) = 1, 0 le y < n, gcd(y, n) = 1}$ 的一个一一对应。
4. 计算两侧的元素个数:
左侧集合的大小就是 $phi(mn)$。这是欧拉函数的定义。
右侧集合的大小,我们可以分别计算:
满足 $0 le x < m$ 且 $gcd(x, m) = 1$ 的整数 $x$ 的个数是 $phi(m)$。(注意这里的范围,虽然定义是小于等于,但欧拉函数通常定义为小于等于,这里为了方便与 $mn$ 对应,考虑小于 $m$ 的范围,且 $gcd(0,m)=m
e 1$,所以0不计入。但我们通常理解 $phi(m)$ 是指 $1$ 到 $m$ 之间与 $m$ 互质的数,包含 $1$ 而不包含 $m$ 本身。如果 $m=1$, $phi(1)=1$. 这里的 $x$ 从 $0$ 到 $m1$ 考虑,正好对应 $1$ 到 $m1$ 的数,以及 $0$。如果 $m>1$, $gcd(0,m)=m
e 1$, 所以 $0$ 不会被数进去。那么考虑 $1$ 到 $m1$ 的数,与 $1$ 到 $m$ 之间与 $m$ 互质的数的个数是相同的,即 $phi(m)$ 个。更严谨地说,范围 $0 le x < m$ 和 $1 le x le m$ 对于计算与 $m$ 互质的数的个数是等价的,因为 $gcd(m, m) = m
e 1$ (当 $m>1$)。所以 $phi(m)$ 个数。)
满足 $0 le y < n$ 且 $gcd(y, n) = 1$ 的整数 $y$ 的个数是 $phi(n)$。(同理,此处也指 $1$ 到 $n$ 之间与 $n$ 互质的数的个数是 $phi(n)$ 个。)
由于这是一个一一对应,左侧集合的元素个数必须等于右侧集合的元素个数。
所以,$phi(mn) = phi(m) imes phi(n)$。
结论:
我们成功地证明了,对于任意互质的正整数 $m$ 和 $n$,欧拉函数 $phi(mn) = phi(m)phi(n)$。这一定义了欧拉函数 $phi(n)$ 是一个积性函数。
一些补充说明,让解释更自然:
当我们考虑与 $mn$ 互质的数时,我们可以想象我们正在使用中国剩余定理来“构建”这些数。中国剩余定理告诉我们,如果我们知道一个数模 $m$ 的余数(并且这个余数与 $m$ 互质),以及这个数模 $n$ 的余数(并且这个余数与 $n$ 互质),那么我们可以唯一地确定这个数模 $mn$ 的余数。
比如说,我们想找到所有小于 $mn$ 且与 $mn$ 互质的数。我们可以问这样的问题:“这个数模 $m$ 的余数是什么?这个数模 $n$ 的余数又是什么?”
因为我们要求这个数与 $mn$ 互质,那么它也必须与 $m$ 互质,并且与 $n$ 互质。所以,这个数模 $m$ 的余数必须与 $m$ 互质。同理,这个数模 $n$ 的余数也必须与 $n$ 互质。
有多少种选择呢?
对于模 $m$ 的余数,我们可以在 ${1, 2, ldots, m1}$ 中选择一个与 $m$ 互质的数。这里我们不包含 $m$ 本身,因为 $gcd(m, m) = m
e 1$ (假设 $m>1$)。所以,我们有 $phi(m)$ 个这样的选择。
对于模 $n$ 的余数,我们可以在 ${1, 2, ldots, n1}$ 中选择一个与 $n$ 互质的数。同理,我们有 $phi(n)$ 个这样的选择。
中国剩余定理告诉我们,每一种这样的“余数组合”(一个与 $m$ 互质的余数,一个与 $n$ 互质的余数)都唯一地对应着一个小于 $mn$ 且与 $mn$ 互质的整数。
所以,小于 $mn$ 且与 $mn$ 互质的整数的总数,就是所有可能的与 $m$ 互质的余数的数量乘以所有可能的与 $n$ 互质的余数的数量。这就直接给出了 $phi(mn) = phi(m) imes phi(n)$。
这种证明方式,依赖于中国剩余定理,是一个非常经典且简洁的证明方法,清晰地揭示了欧拉函数在“互质性”上的乘法性质。