对于互质的正整数 a 和 n ,有 aφ(n) ≡ 1 mod n。
首先考虑两个集合:
Zn = {x1,x2,···xφ(n)}
S = {a * x1 mod n,a * x2 mod n,···a * xφ(n) mod n}
对于这两个集合,有以下点:
1. Zn和S两个集合元素个数都为φ(n)个。
2. a与n互质,xi(1 ≤ i ≤ φ(n))与n互质,那么a * xi与n互质,所以a * xi ∈ Zn。
3. 对于i ≠ j,那么xi ≠ xj,可得a * xi mod n ≠ a * xj mod n。证明很简单,因为a * xi - a * xj的值肯定不是n的倍数。
根据以上几点,我们知道:
1. 集合Zn和集合S元素个数相等。
2. 集合S中的元素都属于Zn。
3. 集合S中的任意两个元素值不相等。
所以,Zn = S。
两个集合所有元素乘积也相等
x1 * x2 * ··· * xφ(n) =
(a * x1 mod n) * (a * x2 mod n) * ··· * (a * xφ(n) mod n)
等式两遍mod n
x1 * x2 * ··· * xφ(n) ≡
(a * x1 mod n) * (a * x2 mod n) * ··· * (a * xφ(n) mod n) mod n
等式右侧合并a得
x1 * x2 * ··· * xφ(n) ≡
aφ(n) * (x1 mod n) * (x2 mod n) * ··· * (xφ(n) mod n) mod n
简化
x1 * x2 * ··· * xφ(n) ≡
aφ(n) * x1 * x2 * ··· * xφ(n) mod n
因为x1 * x2 * ··· * xφ(n)与n互质,可消去
1 ≡ aφ(n) mod n
得到
aφ(n) ≡ 1 mod n。
费马定理是欧拉定理的一个特例,即n为素数
a是不能被质数p整除的正整数,则有 ap-1 ≡ 1 mod p。
Leave a Reply