CSI讲义5--有趣的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 #只是控制换行
当然，也可以用C语言来写写看。不断尝试，让n = 7，或者等于13，17 。接着，也可以尝试n等于10，20等等。
这个程序不断输出 i*j mod n的值。关键是，看懂这个程序，执行多次程序之后，你们能归纳出什么结论吗？我想，发现规律比学到知识要重要得多。
比如，在n等于11的时候，我得到这样的输出。
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 1 3 5 7 9
3 6 9 1 4 7 10 2 5 8
4 8 1 5 9 2 6 10 3 7
5 10 4 9 3 8 2 7 1 6
6 1 7 2 8 3 9 4 10 5
7 3 10 6 2 9 5 1 8 4
8 5 2 10 7 4 1 9 6 3
9 7 5 3 1 10 8 6 4 2
10 9 8 7 6 5 4 3 2 1
似乎很容易发现，每一行只是1到n-1的重排。这是偶然还是规律？如果n取13，我们还能得到同样规律的输出吗？我们会不会得到：
1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 8 10 12 1 3 5 7 9 11
3 6 9 12 2 5 8 11 1 4 7 10
4 8 12 3 7 11 2 6 10 1 5 9
5 10 2 7 12 4 9 1 6 11 3 8
6 12 5 11 4 10 3 9 2 8 1 7
7 1 8 2 9 3 10 4 11 5 12 6
8 3 11 6 1 9 4 12 7 2 10 5
9 5 1 10 6 2 11 7 3 12 8 4
10 7 4 1 11 8 5 2 12 9 6 3
11 9 7 5 3 1 12 10 8 6 4 2
12 11 10 9 8 7 6 5 4 3 2 1
如果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
似乎是令人失望的结果！
如果你并没有总结出规律，我想你暂时还是不要看下去，多思考思考，多尝试。如果你找到了规律，那请看下面。
mod n运算中n为素数的情形
令n为素数：
任意取一个大于等于1且小于等于n-1的整数i，重复用所有大于等于1且小于等于n-1的整数j(n-1个数)对i进行mod n的乘法，即求
i*j mod n，所得的整数刚好是所有大于等于1且小于等于n-1的整数(n-1个数)的某个排列。
即，任取一个i之后，我们算这n-1个值：
i*1 mod n, i*2 mod n, ..., i*(n-1) mod n (1)
得到的数刚好是（经过排列之后）：
1，2，3，...，n-1 (2)
我们把第(1)行的数乘起来并mod n：
i^(n-1) * (n-1)! mod n (3)
把第二行的数乘起来并mod n：
(n-1)! mod n (4)
我们知道(3) == (4)：
i^(n-1) * (n-1)! ≡ (n-1)! mod n (5)
由(5)我们可以得到（当然，我们必须问为什么？）：
i^(n-1) ≡ 1 mod n (6)
这个(6)就是颇为有名的费尔马小定理！
这是我们需要的一个条件。有同学问这道题的答案，答案是：it is easy！作为习题给大家做一下。
证明：if gcd(c,n)==1, and a*c ≡ b*c mod n,
then a ≡ b mod n.
想在“图灵班”混的同学请到“课堂派”交作业。
费尔马小定理：
对于素数n，取任意大于1小于n-1的整数（此条件并不必要，为什么？），我们有，i^(n-1) ≡ 1 mod n 。
对于以上的推导你懂(不懂)吗？懂不值得骄傲。不懂，不如问一下自己，在哪个环节让自己失去了逻辑关联？任何人都应该懂。
费尔马小定理有什么用？这个，敬请期待......
暂时回到这个小定理的条件开始，n为素数，这是一个较强的要求，如果n为任意整数呢？我们已经知道n=12的时候，得到的结果没有n为素数时那么有规律。但是，n为合数是不是就没有规律呢？这个.....嗯？怎么办？敬请期待下回分解。
2017-06-29整理
