本篇为交互式 Jupyter Notebook 文档,请在 这里 查看完整版。
由于叫 欧拉定理 的定理太多所以就用这个名字了。
在开始讲解之前,首先要问这么一个问题:
是多少?
看到取模,我们当然要先找找规律:
1 2
| print([3**exponent%17 for exponent in range(1, 17)]) print([3**exponent%17 for exponent in range(17, 33)])
|
啊哈!3的幂对17取模,结果是循环的。
所以 ,.
我们应该再仔细思考一下,为什么是以16个数为一循环?
因为一个数对17取模,得到的结果只可能在 这个区间上。而如果一个结果是0,那么其他结果全是0,所以只能在 上。
那无论底数是什么,都是16个数一循环吗?一定会形成循环吗?
首先来看后面这个问题,答案是会。因为一定会有重复,有重复就会出现循环。
对于前一个问题,鉴于有重复就会出现循环,一个循环里面不可能有重复。总共只有16个数,根据鸽巢原理,循环的长度一定小于等于16. 问题也等价于: 中的每一个数都会出现吗?
1
| print([2**exponent%17 for exponent in range(1, 17)])
|
看来并不是。那么接下来怎么办呢?
我们不如换一种思路,看看有没有哪个数是一定会出现的。
1 2
| for base in range(0, 17): print(base, [base**exponent%17 for exponent in range(1, 17)])
|
令人惊奇的是,每个数的第16次方对17取余,结果都是1. 也即
联想到上面我们证明循环等价于重复的公式:
我们如果可以证明上式右边成立,我们就能证明无论如何第1到第16个数都会形成循环了。
作为严谨证明的大纲,先演示对于一个特殊情况:,模数为 7 的证明。
我们先看一个引理:如果我们有正整数 并且它不被另一个正整数 整除,我们可以写下这样的数列
我们对这数列的每一项都对 取余,就能得到一个从 到 的全排列。也就是说,每个数都会出现一次。
1 2 3 4 5
| a = 3 p = 7 print([a*i for i in range(1, p)]) print(perm := [a*i%p for i in range(1, p)]) print(set(perm))
|
在这之后,我们会把这两个数列分别乘起来。由于前者只是后者的 倍,所以它们模 同余。
化简得到
最后,我们会把两边的 “消去”(我知道不能这么直接消,bear with me!)得到
1 2 3 4 5 6 7 8 9
| lhs = 1 for i in range(1, p): lhs *= a*i rhs = 1 for i in range(1, p): rhs *= i print(lhs, '===', rhs, '(mod ' + str(p) + ') is', lhs%7 == rhs%7) print('Canceling out (p-1)! gives us:') print(lhs//rhs, '=== 1 (mod ' + str(p) + ') is', (lhs/rhs)%7 == 1)
|
要完成这个证明,有两个地方需要我们详细说明:
- 引理:如果我们有正整数 并且它不被另一个正整数 整除, 为正整数且 时,
- 同余式两边何时能同时消去一个数
我们先看第二个:同余式除法,因为第一个依赖第二个证明。
上面我们已经用了同余式两边同时乘上同余的数,同余式仍然成立的性质。除此之外对于加减法也有效。但是对于除法,就没那么简单了。
首先把同余式写成等式。
右式两边同时除以 得
如果 那么我们还需要换掉整数 以使模数为一个整数。
最后得到
如果我们希望前后模数相等,当且仅当 也即 与 互质才成立。
回到刚才的这个式子
要让两边消掉 又不改变模数,有且仅有 与 互质,这等价于 为一个质数。7 和 17 都满足这个要求。
现在再来看那个引理:如果有正整数 并且它不被另一个正整数 整除, 为正整数且 时,.
首先,小于 的数 与 互质,而 也与 互质,所以这两个数乘起来仍然与 互质(欧几里得引理)。所以 . 然后要证明这些数互不相等。运用反证法,假设有两个不相等的数 使得
那么由上面推导的同余式除法得
而 所以 与假设矛盾。证毕。
至此,证明全部完成。
由上面的推导,我们得到了费马小定理:
对于质数 以及任意正整数 满足 有
如果你足够细心,你也许会注意到我刚才说第二点的时候并没有提到 一定是个素数。这让我们不禁想推广刚才得到的成果。我们先来感性的认识一下,当 不是素数时是什么样的。因为 是 prime 的意思,所以下面换成合数的情况下我们用 来代替。
我们先来看看 的情形:
1 2 3 4 5 6 7 8
| def extract_repeat(arr): for index, value in enumerate(arr[1:]): if arr[0] == value: return arr[0:index+1]
m = 10 for a in range (1, m): print('a =', a, arr := [a**exponent%m for exponent in range(1, m)], extract_repeat(arr))
|
注意到,当 与 有公因数的时候,循环不一定会出现 1. 这是为什么呢?任意整数 , 这时候都肯定跟 互质,因此 .
有没有整数 使得
呢?要找到这个数,我们就得找到一个数列 ,使其满足我们上面的两点要求
- 对每个数乘以 再 得到的数列是 的全排列
- 把 中的数全乘起来,得到的数与 互质(可以从同余式两边消去)
在 的情况下,我们已经看到了 . 现在考虑的是 不为质数的情况。
先看第一点。需要 中的数 都与 互质, 与 互质,以及 是比 小且与 互质的数的集合。
再看第二点,由 是与 互质的数的集合, 中的数全乘起来,得到的数与 互质,满足条件。
下面开始外层证明。令 为 中所有数的乘积,即 . 为 对应的数组 中的元素个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| import math def phi(m): res = [] for k in range(1, m+1): if math.gcd(k, m) == 1: res.append(k) return res
def prod(arr): res = 1 for t in arr: res *= t return res a = 3 m = 10 T = phi(m) r = prod(T)
print(prod([a*t for t in T]), '===', r, '(mod ' + str(m) + ') is', prod([a*t for t in T])%m == r%m) print(a**len(T)*r, '===', r, '(mod ' + str(m) + ') is', a**len(T)*r%m == r%m) print(a**len(T) , '=== 1', '(mod ' + str(m) + ') is', a**len(T)%m == 1%m)
|
这就证明了欧拉定理(数论):
和 是互质的正整数, 为小于等于 的正整数中与 互质的数的数目(欧拉函数),有
参考资料:
- Euler’s Totient Theorem, Misha Lavrov[PDF]
- Proofs of Fermat's little theorem, Wikipedia