费马小定理【证明】【复习】

复习一下。
定理:
ppp为质数,pap \nmid ap∤a
ap11(modp)a^{p-1}\equiv 1\pmod{p}ap−1≡1(modp)

是不是一个很让人谔谔的式子?
证明:
A={1,2,3,,p1}f=(p1)!fa×A1×a×A2××a×Ap1(modp)1ip1gcd(Ai,p)=1,gcd(a,p)=11ip1gcd(Ai×a,p)=1Ai×a(modp)OIwiki1i,jp1,ijAi×a≢Aj×a(modp)Ai×a(modp)Aj(1jp1)ap1×ff(modp)1f,ap11(modp) 构造序列A=\{1,2,3,\cdots,p-1\}\\ 设f=(p-1)!,则f\equiv a\times A_1\times a \times A_2 \times \cdots \times a \times A_{p-1}\pmod{p}\\ 证明:\\ 因为\forall_{1 \le i \le p-1}\gcd(A_i,p)=1,\gcd(a,p)=1\\ 所以\forall_{1 \le i \le p-1}\gcd(A_i\times a,p)=1\\ 而且因为每一个A_i\times a\pmod{p}都是独一无二(参考OI_{wiki}),即\\ \forall_{1 \le i,j \le p-1,i\not = j}A_i \times a \not \equiv A_j \times a \pmod{p}\\ 而且每一个A_i\times a \pmod{p}都对应了一个A_j(1 \le j \le p-1)\\ 得证。\\ 所以整理式子珂得:\\ a^{p-1}\times f \equiv f \pmod{p}\\ 两边同时乘\frac{1}{f},得 a^{p-1} \equiv 1 \pmod{p}\\ 证毕。 构造序列A={1,2,3,⋯,p−1}设f=(p−1)!,则f≡a×A1​×a×A2​×⋯×a×Ap−1​(modp)证明:因为∀1≤i≤p−1​gcd(Ai​,p)=1,gcd(a,p)=1所以∀1≤i≤p−1​gcd(Ai​×a,p)=1而且因为每一个Ai​×a(modp)都是独一无二(参考OIwiki​),即∀1≤i,j≤p−1,i​=j​Ai​×a​≡Aj​×a(modp)而且每一个Ai​×a(modp)都对应了一个Aj​(1≤j≤p−1)得证。所以整理式子珂得:ap−1×f≡f(modp)两边同时乘f1​,得ap−1≡1(modp)证毕。
运用:
挖坑待填。

参考文章:OI_wiki 参考文章

上一篇:Baby-step Giant-step and its extension


下一篇:同余3:解高次同余方程的BSGS算法及其扩展学习笔记