CSI讲义6-- 有趣的Mod算术运算-欧拉定理
前文再续，书接上一回，我们说到费尔马小定理，这里我们......
欧拉
Mod数为合数时的算术运算
同样的Python代码：
给定任意一个整数n，比如让n＝11.
for i in range(1, n): #i循环从1到n-1
for j in range(1, n): #j循环从1到n-1
print ((i * j) % n), #输出 i*j mod n
print #只是控制换行
当n＝12，我们的程序输出：
1 2 3 4 5 6 7 8 9 10 11
2 4 6 8 10 0 2 4 6 8 10
3 6 9 0 3 6 9 0 3 6 9
4 8 0 4 8 0 4 8 0 4 8
5 10 3 8 1 6 11 4 9 2 7
6 0 6 0 6 0 6 0 6 0 6
7 2 9 4 11 6 1 8 3 10 5
8 4 0 8 4 0 8 4 0 8 4
9 6 3 0 9 6 3 0 9 6 3
10 8 6 4 2 0 10 8 6 4 2
11 10 9 8 7 6 5 4 3 2 1
是不是没有规律？呃，慢着，我看看......第1行怎么那么熟悉？慢着，似乎第5行的结果也很漂亮，因为结果就是1到11到一次重排。哦，原来第7行、第11行，结果都是1到11到一次重排。1、5、7、11都是什么数？不难看出，是与12互素的整数。似乎，规律出来了。我们是不是可以使用上一次课到方法得到：
如果i与n互素，那么i*1 mod n，i*2 mod n，i*3 mod n，...，i*(n-1) mod n是[1..n-1]这些数的重排。所以：
i^(n-1)*(n-1)! ≡ (n-1)! mod n
所以，**i^(n-1) ≡ 1 mod n** ？啊，一个新的“费尔马小定理”？！
慢着，有点不对......因为(n-1)!并不与n互素！！！所以，我们并不可以做两边的“消去”术。似乎有点失望。那为什么费尔马小定理可以那样做？因为n是素数，1到n-1之间到所有数都与n互素。
既然如此，那么，如果n为合数，1到n-1之间的那些数与n互素？它们的相乘是不是还是与n互素？
答案是，1到n-1之间的那些与n互素的数（不就是gcd(i, n)==1 ?）的相乘确实与n互素！
作业：证明n个与N互素的整数相乘得到的整数与N互素。
现在，如果我们只考虑与n互素的数会怎么样？计算机程序就是帮助我们找规律的利器。为何不尝试用C语言写个程序看看？（虽然我给出的是Python代码。）
for i in range(1, n): #1到n-1的循环
if gcd(i, n)==1: #如果i与n互素
for j in range(1, n): #1到n-1的循环
if gcd(j, n) == 1: #如果j与n互素
print ((i * j) % n), #输出(i * j) mod n
print #内循环结束，输出换行
令n=12，程序输出是：
1 5 7 11
5 1 11 7
7 11 1 5
11 7 5 1
这是什么意思？规律是什么？看多一些数据。令n＝21，输出为：
1 2 4 5 8 10 11 13 16 17 19 20
2 4 8 10 16 20 1 5 11 13 17 19
4 8 16 20 11 19 2 10 1 5 13 17
5 10 20 4 19 8 13 2 17 1 11 16
8 16 11 19 1 17 4 20 2 10 5 13
10 20 19 8 17 16 5 4 13 2 1 11
11 1 2 13 4 5 16 17 8 19 20 10
13 5 10 2 20 4 17 1 19 11 16 8
16 11 1 17 2 13 8 19 4 20 10 5
17 13 5 1 10 2 19 11 20 16 8 4
19 17 13 11 5 1 20 16 10 8 4 2
20 19 17 16 13 11 10 8 5 4 2 1
请注意每一行开始的那个数字与n的关系！可以考虑30分钟再往下看。
规律：
一个与n互素的整数i，它分别与所有大于等于1、小于n且与n互素的整数相乘（mod n），所得的整数是所有大于等于1、小于n且与n互素的整数的排列。
记大于等于1、小于n且与n互素的整数的个数为phi(n)。记大于等于1、小于n且与n互素的整数的相乘为Pi(n)。利用在求费尔马小定理时的技巧:
i^phi(n) * Pi(n) ≡ Pi(n) mod n
即：i^phi(n) ≡ 1 mod n
这个公式就是大名鼎鼎的欧拉定理！当n为素数，那么phi(n) == n-1。所以，费尔马小定理只是欧拉定理的一种特殊情形。
欧拉定理：
若n，a为正整数，且 gcd(a,n)==1，
则 a^phi(n) ≡ 1 mod n.
注：
phi(n) = phi(n1)*phi(n2), if n == n1 * n2。
如何证明？It is easy，略。（注，如果你想问，容易到底有多容易？ 请期待！）
注意，无论是费尔马小定理还是欧拉定理，这里都没有严格证明。请有兴趣的同学自己完成。
2017-06-27整理修订
