8.3费马定理和欧拉定理 定理8.1费马定理 Fermat' s Theorem 若p是素数,a是正整数且不能被p整除,则ap-modp=1 证明: 0因为 a mod p,2 a mod p,…,(p-1) a mod p}是{1,2, (p-1)的置换形,所以,(ax2ax…x(p-1)a)≡(1x2 X…x(p-1)(modp)≡(p-1)!modp 0但是,ax2ax…(p-1)a=(p-1)ap-1,因此(p-1)aP 三(p-1)!modp,两边去掉(p-1),即得 ap-Imod p 证毕 例如:a=7,p=19, ap-Imod p=718mod19=? 72=49三11mod1974=121≡7mod19 78=49≡11mod19716=121≡7mod19 Qp-1=718716X72=7x11≡1modl9 outer science& technolo ash mfy@ustc.edu.cn 现代密码学理论与实践 25/81mfy@ustc.edu.cn 现代密码学理论与实践 25/81 定理8.1 费马定理 Fermat’s Theorem 若p是素数, a是正整数且不能被p整除, 则a p-1 mod p=1  证明： ◦ 因为{a mod p, 2a mod p, ..., (p-1)a mod p}是{1, 2, ..., (p-1)}的置换形, 所以, (aｘ2aｘ ... ｘ (p-1)a)≡(1ｘ2 ｘ ... ｘ(p-1)) (mod p)≡ (p-1)! mod p. ◦ 但是, aｘ2aｘ...ｘ(p-1)a=(p-1)!ap-1 , 因此(p-1)!ap- 1≡(p-1)! mod p, 两边去掉(p-1)!, 即得a p-1mod p = 1 证毕  例如：a=7, p=19, ap-1mod p=718 mod 19=? 72=49≡11 mod 19 74=121≡7 mod 19 78=49≡11 mod 19 716=121≡7 mod 19 a p-1=718=716x72≡7x11≡1 mod 19