Euler's Totient Theorem

本篇为交互式 Jupyter Notebook 文档,请在 这里 查看完整版。

由于叫 欧拉定理 的定理太多所以就用这个名字了。

在开始讲解之前,首先要问这么一个问题:

32012mod17是多少?

看到取模,我们当然要先找找规律:

1
2
print([3**exponent%17 for exponent in range(1, 17)])
print([3**exponent%17 for exponent in range(17, 33)])

啊哈!3的幂对17取模,结果是循环的。

所以 2012=12516+12320123124(mod17).

我们应该再仔细思考一下,为什么是以16个数为一循环?

因为一个数对17取模,得到的结果只可能在 [0,16] 这个区间上。而如果一个结果是0,那么其他结果全是0,所以只能在 [1,16] 上。

那无论底数是什么,都是16个数一循环吗?一定会形成循环吗?

首先来看后面这个问题,答案是会。因为一定会有重复,有重复就会出现循环。

3x3y(mod17)3x+13y+1(mod17)

对于前一个问题,鉴于有重复就会出现循环,一个循环里面不可能有重复。总共只有16个数,根据鸽巢原理,循环的长度一定小于等于16. 问题也等价于:[1,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. 也即

a161(mod17)

联想到上面我们证明循环等价于重复的公式:

a161(mod17)a16+1a(mod17)

我们如果可以证明上式右边成立,我们就能证明无论如何第1到第16个数都会形成循环了。

作为严谨证明的大纲,先演示对于一个特殊情况:a=3,模数为 7 的证明。

我们先看一个引理:如果我们有正整数 p 并且它不被另一个正整数 a 整除,我们可以写下这样的数列

a,2a,3a,,(p1)a

我们对这数列的每一项都对 p 取余,就能得到一个从 1p1 的全排列。也就是说,每个数都会出现一次。

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))

在这之后,我们会把这两个数列分别乘起来。由于前者只是后者的 a 倍,所以它们模 p 同余。

a×2a×3a××(p1)a1×2×3××(p1)(modp)

化简得到

ap1(p1)!(p1)!(modp)

最后,我们会把两边的 (p1)! “消去”(我知道不能这么直接消,bear with me!)得到

ap11(modp)

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)

要完成这个证明,有两个地方需要我们详细说明:

  • 引理:如果我们有正整数 p 并且它不被另一个正整数 a 整除,i 为正整数且 ip1 时,{iamodp}={i}
  • 同余式两边何时能同时消去一个数

我们先看第二个:同余式除法,因为第一个依赖第二个证明。

上面我们已经用了同余式两边同时乘上同余的数,同余式仍然成立的性质。除此之外对于加减法也有效。但是对于除法,就没那么简单了。

首先把同余式写成等式。

acbc(modm)kZ,ac=bc+km

右式两边同时除以 c

a=b+kmc

如果 cm 那么我们还需要换掉整数 k 以使模数为一个整数。

k=kgcd(m,c)ca=kmgcd(m,c)

最后得到

acbc(modm)ab (modmgcd(m,c))

如果我们希望前后模数相等,当且仅当 gcd(m,c)=1 也即 mc 互质才成立。

回到刚才的这个式子

ap1(p1)!(p1)!(modp)

要让两边消掉 (p1)! 又不改变模数,有且仅有 (p1)!p 互质,这等价于 p 为一个质数。7 和 17 都满足这个要求。

现在再来看那个引理:如果有正整数 p 并且它不被另一个正整数 a 整除,i 为正整数且 ip1 时,{iamodp}={i}.

首先,小于 p 的数 ip 互质,而 a 也与 p 互质,所以这两个数乘起来仍然与 p 互质(欧几里得引理)。所以 iamodp[1,p1]. 然后要证明这些数互不相等。运用反证法,假设有两个不相等的数 x,y<i 使得

xaya(modp)

那么由上面推导的同余式除法得

xy(modp)

x<i,y<i 所以 x=y 与假设矛盾。证毕。

至此,证明全部完成。

由上面的推导,我们得到了费马小定理:

对于质数 p 以及任意正整数 a 满足 pa

ap11(modp)

如果你足够细心,你也许会注意到我刚才说第二点的时候并没有提到 p 一定是个素数。这让我们不禁想推广刚才得到的成果。我们先来感性的认识一下,当 p 不是素数时是什么样的。因为 p 是 prime 的意思,所以下面换成合数的情况下我们用 m 来代替。

我们先来看看 m=10 的情形:

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))

注意到,当 am 有公因数的时候,循环不一定会出现 1. 这是为什么呢?任意整数 kkm+1 这时候都肯定跟 m 互质,因此 axkm+1.

有没有整数 a,x 使得

ax1(modm)

呢?要找到这个数,我们就得找到一个数列 T,使其满足我们上面的两点要求

  • 对每个数乘以 amod m 得到的数列是 T 的全排列
  • T 中的数全乘起来,得到的数与 m 互质(可以从同余式两边消去)

m=p 的情况下,我们已经看到了 T={1,2,3,,p1}. 现在考虑的是 m 不为质数的情况。

先看第一点。需要 T 中的数 ti 都与 m 互质,am 互质,以及 tiamodmTT 是比 m 小且与 m 互质的数的集合。

再看第二点,由 T 是与 m 互质的数的集合,T 中的数全乘起来,得到的数与 m 互质,满足条件。

下面开始外层证明。令 rT 中所有数的乘积,即 r=ti. ϕ(m)m 对应的数组 T 中的元素个数。

at1×at2××atnt1×t2××tn(modm)aϕ(m)rr(modm)aϕ(m)1(modm)

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)

这就证明了欧拉定理(数论):

ma 是互质的正整数,ϕ(m) 为小于等于 n 的正整数中与 n 互质的数的数目(欧拉函数),有

aϕ(m)1(modm)

参考资料:

  1. Euler’s Totient Theorem, Misha Lavrov[PDF]
  2. Proofs of Fermat's little theorem, Wikipedia