1.设p=23和a=3，使用费尔马小定理计算a^2019 mod p
3 2019 ≡ 3 22 ∗ 91 + 17 ≡ 3 17 m o d 23 3 2 ≡ 9 m o d 23 3 4 ≡ 9 ∗ 9 ≡ 15 m o d 23 3 8 ≡ 15 ∗ 15 ≡ 5 m o d 23 3 16 ≡ 5 ∗ 5 ≡ 3 m o d 23 3 17 ≡ 9 m o d 23 所以 3 2019 m o d 23 = 9 3^{2019}\equiv3^{22*91+17}\equiv3^{17}\bmod23\\
3^{2}\equiv9\bmod 23\\
3^{4}\equiv9*9\equiv15\bmod 23\\
3^{8}\equiv15*15\equiv5\bmod23\\
3^{16}\equiv5*5\equiv3\bmod23\\
3^{17}\equiv9\bmod 23\\
所以3^{2019}\bmod23=9
3 2019 ≡ 3 22 ∗ 91 + 17 ≡ 3 17 mod 23 3 2 ≡ 9 mod 23 3 4 ≡ 9 ∗ 9 ≡ 15 mod 23 3 8 ≡ 15 ∗ 15 ≡ 5 mod 23 3 16 ≡ 5 ∗ 5 ≡ 3 mod 23 3 17 ≡ 9 mod 23 所以 3 2019 mod 23 = 9
2.使用费尔马小定理求解同余方程x^50=2(mod 17).
x 50 ≡ x 16 ∗ 3 + 2 ≡ x 2 ≡ 2 m o d 17 所以存在整数 k 使得 x 2 = 2 + 17 ∗ k 易解出当 k = 2 时， x = 6. x^{50}\equiv x^{16*3+2}\equiv x^{2}\equiv2\bmod17\\
所以存在整数k使得x^{2}=2+17*k\\
易解出当k=2时，x=6.
x 50 ≡ x 16 ∗ 3 + 2 ≡ x 2 ≡ 2 mod 17 所以存在整数 k 使得 x 2 = 2 + 17 ∗ k 易解出当 k = 2 时， x = 6.
5.请证明13整除2^70+3^70.[提示：这是一道名为证明题的计算题。]
即证明 2 70 + 3 70 ≡ 0 m o d 13 即证明 2 12 ∗ 5 + 10 + 3 12 ∗ 5 + 10 ≡ 0 m o d 13 根据费马小定理，即证 2 10 + 3 10 ≡ 0 m o d 13 即证 2 10 ≡ − 3 10 m o d 13 因为 2 2 ≡ 4 m o d 13 . . . . 2 10 ≡ 10 m o d 13 又因为 − 3 2 ≡ − 9 m o d 13 . . . . − 3 10 ≡ − 3 ≡ 10 − 13 ≡ 10 m o d 13 所以得证 2 10 ≡ − 3 10 m o d 13 , 所以 13 能整除 2 70 + 3 70 即证明2^{70}+3^{70}\equiv0\bmod 13\\
即证明2^{12*5+10}+3^{12*5+10}\equiv0\bmod 13\\
根据费马小定理，即证2^{10}+3^{10}\equiv0\bmod 13\\
即证2^{10}\equiv-3^{10}\bmod 13\\
因为2^{2}\equiv4\bmod13\\
....\\
2^{10}\equiv10\bmod 13\\
又因为-3^{2}\equiv-9\bmod13\\
....\\
-3^{10}\equiv-3\equiv10-13\equiv10\bmod13\\
所以得证2^{10}\equiv-3^{10}\bmod13,\\
所以13能整除2^{70}+3^{70}
即证明 2 70 + 3 70 ≡ 0 mod 13 即证明 2 12 ∗ 5 + 10 + 3 12 ∗ 5 + 10 ≡ 0 mod 13 根据费马小定理，即证 2 10 + 3 10 ≡ 0 mod 13 即证 2 10 ≡ − 3 10 mod 13 因为 2 2 ≡ 4 mod 13 .... 2 10 ≡ 10 mod 13 又因为 − 3 2 ≡ − 9 mod 13 .... − 3 10 ≡ − 3 ≡ 10 − 13 ≡ 10 mod 13 所以得证 2 10 ≡ − 3 10 mod 13 , 所以 13 能整除 2 70 + 3 70
6.使用欧拉定理计算2^100000 mod 55.
Φ ( 55 ) = Φ ( 5 ∗ 11 ) = Φ ( 5 ) ∗ Φ ( 11 ) = 4 ∗ 10 = 40. 根据欧拉定理 2 100000 ≡ 2 2500 ∗ 40 ≡ 1 m o d 55 所以 2 100000 m o d 55 = 1 \Phi(55)=\Phi(5*11)=\Phi(5)*\Phi(11)=4*10=40.\\
根据欧拉定理\\
2^{100000}\equiv2^{2500*40}\equiv1\bmod55\\
所以2^{100000}\bmod55=1
Φ ( 55 ) = Φ ( 5 ∗ 11 ) = Φ ( 5 ) ∗ Φ ( 11 ) = 4 ∗ 10 = 40. 根据欧拉定理 2 100000 ≡ 2 2500 ∗ 40 ≡ 1 mod 55 所以 2 100000 mod 55 = 1
8.手动计算7^1000的最后两个数位等于什么？
求最后两位数即模 100 Φ ( 100 ) = Φ ( 2 2 ∗ 5 2 ) = Φ ( 2 2 ) ∗ Φ ( 5 2 ) = Φ 2 ( 2 ) ∗ Φ 2 ( 5 ) = 16. 根据欧拉定理 7 1000 ≡ 7 62 ∗ 16 + 8 ≡ 7 8 m o d 100 7 2 ≡ 49 m o d 100 7 4 ≡ 1 m o d 100 7 8 ≡ 1 m o d 100. 所以最后两个数位等于 01 求最后两位数即模100\\
\Phi(100)=\Phi(2^{2}*5^{2})=\Phi(2^{2})*\Phi(5^{2})\\
=\Phi^{2}(2)*\Phi^{2}(5)=16.\\
根据欧拉定理\\
7^{1000}\equiv7^{62*16+8}\equiv7^{8}\bmod100\\
7^{2}\equiv49\bmod100\\
7^{4}\equiv1\bmod100\\
7^{8}\equiv1\bmod100.\\
所以最后两个数位等于01
求最后两位数即模 100 Φ ( 100 ) = Φ ( 2 2 ∗ 5 2 ) = Φ ( 2 2 ) ∗ Φ ( 5 2 ) = Φ 2 ( 2 ) ∗ Φ 2 ( 5 ) = 16. 根据欧拉定理 7 1000 ≡ 7 62 ∗ 16 + 8 ≡ 7 8 mod 100 7 2 ≡ 49 mod 100 7 4 ≡ 1 mod 100 7 8 ≡ 1 mod 100. 所以最后两个数位等于 01
9.编写Python语言程序完成欧拉Phi函数的计算，即输入正整数n，计算并返回φ(n).
import mathdef gcd (a,b ): if b==0 : return a else : return gcd(b,a%b) def jud (num ): a=1 for i in range (2 ,math.ceil(math.sqrt(num))): if num%i==0 : a=0 if a==1 : return 1 else : return 0 def Phi (n ): if jud(n)==1 : return n-1 else : count=0 for i in range (1 ,n): if gcd(n,i)==1 : count=count+1 return count
10.设p是素数，计算(p-1)! mod p,并找出规律，写成定理，并给出证明。
设 ( p − 1 ) ! m o d p = A , 代入素数得 p = 2 时， A = 1 ; p = 3 时， A = 2 ; p = 5 时， A = 4 ; p = 7 时， A = 6 ; 写出定理：如果 p 是一个素数，则 ( p − 1 ) ! m o d p = p − 1. 设(p-1)!\bmod p=A,代入素数得\\
p=2时，A=1;\\
p=3时，A=2;\\
p=5时，A=4;\\
p=7时，A=6;\\
写出定理：如果p是一个素数，则(p-1)!\bmod p=p-1.\\
设 ( p − 1 )! mod p = A , 代入素数得 p = 2 时， A = 1 ; p = 3 时， A = 2 ; p = 5 时， A = 4 ; p = 7 时， A = 6 ; 写出定理：如果 p 是一个素数，则 ( p − 1 )! mod p = p − 1.
证明：
因为 p 是一个素数，所以小于 p 的所有正整数都与 p 互素， 对于 1 ≤ c < p , 总存在 c 的唯一的确定的乘法逆元 , 使得 c ∗ c − 1 ≡ 1 m o d p ( c − 1 < p ) , 即 c − 1 存在与 { 1.2.3... p − 1 } 的最小剩余系 , 除 1 和 p − 1 外，存在 i , j ∈ { 2.3.4... p − 2 } 使得 i ∗ j ≡ 1 m o d p , 所以 ( p − 1 ) ! ≡ p − 1 m o d p , 所以 ( p − 1 ) ! m o d p = p − 1 成立。 因为p是一个素数，所以小于p的所有正整数都与p互素，\\
对于1\leq c< p,总存在c的唯一的确定的乘法逆元,\\
使得c*c^{-1}\equiv1\bmod p(c^{-1}<p),\\
即c^{-1}存在与\{1.2.3...p-1\}的最小剩余系,\\
除1和p-1外，存在i,j\in\{2.3.4...p-2\}\\
使得i*j\equiv 1\bmod p,\\
所以(p-1)!\equiv p-1\bmod p,\\
所以(p-1)!\bmod p =p-1 成立。\\
因为 p 是一个素数，所以小于 p 的所有正整数都与 p 互素， 对于 1 ≤ c < p , 总存在 c 的唯一的确定的乘法逆元 , 使得 c ∗ c − 1 ≡ 1 mod p ( c − 1 < p ) , 即 c − 1 存在与 { 1.2.3... p − 1 } 的最小剩余系 , 除 1 和 p − 1 外，存在 i , j ∈ { 2.3.4... p − 2 } 使得 i ∗ j ≡ 1 mod p , 所以 ( p − 1 )! ≡ p − 1 mod p , 所以 ( p − 1 )! mod p = p − 1 成立。
