CSI

learning

费尔马小定理

#给定任意一个整数
for i in range(1,n):
    for j in range(1,n):
        print ((i*j)%n),
    print

当给定整数为质数时，如$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的整数i，计算这n-1个值：

i*1 mod n, i*2 mod n, ..., i*(n-1) mod n

得到的数经过排列后为：

1, 2，3, ..., n-1

将第一行数累乘后 mod n

i^(n-1) * (n-1)! mod n

将第二行数累乘后 mod n

(n-1)! mod n

由（3）==（4）得出结论

i^(n-1) $\equiv$ 1 mod n

但 i in range(1,n)这个条件是不必要的

c^(n-1) $\equiv$ 1 mod n 等价于 （c+k*n)^(n-1) $\equiv$ 1 mod n
其中，c ∈ [1,n], k为任意正整数。所以，i=c+k*n∈[1, $+\infty$]

证明：if gcd(c,n) == 1, and $a*c\equiv b*c$ mod n, then a $\equiv$ b mod n

由$a*c\equiv b*c$ mod n 得
$(a-b)*c\equiv 0$ mod n
因为 gcd(c,n) == 1
$a-b\equiv 0$ mod n
得$a\equiv b$ mod n

欧拉定理

当给定整数为合数时，如$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

观察发现，当i=1,5,7,11时，计算后得到的值经过排列后为

1, 2, 3, ..., n-1

但 i^(n-1) * (n-1)! $\equiv$ (n-1)! mod n 不能得到 i^(n-1) $\equiv$ 1 mod n
因为（n-1)! 与 n 不是互素

那么，当只考虑与n互素的数时

1 5 7 11
5 1 11 7 
7 11 1 5
11 7 5 1

发现规律：一个与n互素的整数i，它分别与所有大于等于1，小于n且与n互素的整数相乘后 mod n，所得的整数是所有大于等于1，小于n且与n互素的整数的排列。

即 i^phi(n) $\equiv$ 1 mod n ,其中，记大于等于1，小于n且与n互素的整数的个数为phi(n)

得出结论：
if gcd(a,n)==1,then a^phi(n) $\equiv$ 1 mod n

Josephus问题

疑问1.当k=2时，每一轮消除过后得到的都是等比数列，但是，当k=3或是其他数时，却没有这么好的性质，该怎么办？

然后我到网上查了，网上给出的递推式为f(n)=(f(n-1)+m)%n且f(1)=0;

初始情况： 0, 1, 2 ......n-2, n-1 (共n个人)

第一个人(编号一定是(m-1)%n,设之为(k-1) ,读者可以分m=n的情况分别试下，就可以得出结论) 出列之后，
剩下的n-1个人组成了一个新的约瑟夫环（以编号为k==m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ...,k-3, k-2

重新排序得
0 1 2 ... n-2 n-1

x' -> x

k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n

变成(n-1)个人报数的子问题，经过重新排序后，f(n)与f(n-1)的解相同
找出排序前和排序后的解关系，x' = (x+k)%n
所以，f(n)=(f(n-1)+m%n)%n=(f(n-1)+m)%n

疑问2.为什么要用二进制来表示？用二进制来表示对解题有什么帮助？