数论-费马小定理 学习笔记

1.定理内容

如果p是一个质数，而整数a不是p的倍数，则有 a p − 1 ≡ 1 ( m o d p ) a^{p - 1} \equiv 1 \pmod{p} ap−1≡1(modp)。即：

若 p p p 为素数， gcd ⁡ ( a , p ) = 1 \gcd(a, p) = 1 gcd(a,p)=1，则 a p − 1 ≡ 1 ( m o d p ) a^{p - 1} \equiv 1 \pmod{p} ap−1≡1(modp)。

第二种表述形式：对于任意整数 a a a，有 a p ≡ a ( m o d p ) a^p \equiv a \pmod{p} ap≡a(modp)。

在实际的应用中，我们最多用的是第二种表述形式。

2.证明

设一个质数为 p p p，我们取一个不为 p p p 倍数的数 a a a。

构造一个序列： A = { 1 , 2 , 3 … , p − 1 } A=\{1,2,3\dots,p-1\} A={1,2,3…,p−1}，这个序列有着这样一个性质：

∏ i = 1 n   A i ≡ ∏ i = 1 n ( A i × a ) ( m o d p ) \prod_{i=1}^{n}\space A_i\equiv\prod_{i=1}^{n} (A_i\times a) \pmod p i=1∏n​ Ai​≡i=1∏n​(Ai​×a)(modp)

证明：

∵ ( A i , p ) = 1 , ( A i × a , p ) = 1 \because (A_i,p)=1,(A_i\times a,p)=1 ∵(Ai​,p)=1,(Ai​×a,p)=1

又因为每一个 A i × a ( m o d p ) A_i\times a \pmod p Ai​×a(modp) 都是独一无二的，且 A i × a ( m o d p ) < p A_i\times a \pmod p < p Ai​×a(modp)