费马小定理

费马小定理（）是数论中的一个定理。假如a是一个整数，p是一个質数，那么a^p - a 是p的倍数，可以表示为

:a^p \equiv a \pmod{p}

如果a不是p的倍数，這個定理也可以寫成更加常用的一種形式
:a^{p-1} \equiv 1 \pmod{p}

註：如果a是p的倍数，則
:a^{p-1} \equiv 0 \pmod{p}

費馬小定理的逆敘述不成立，即假如a^p - a 是p的倍数，p不一定是一个質数。例如2^{341}-2是341的倍数，但341=11 \times 31，不是質数。滿足費馬小定理的合數被稱為费马伪素数。

历史
皮埃爾·德·費馬于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。

1736年，歐拉出版了一本名為“一些與素數有關的定理的證明”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）”的論文集，其中第一次给出了證明。但從萊布尼茨未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明。

有些數學家獨立提出相關的假說（有時也被錯誤地稱為中國猜想），當2^{p} \equiv 2 \pmod{p}成立時，p是質數。這是費馬小定理的一個特殊情況。然而，這一假說的前設是錯的：例如，2^{341} \equiv 2 \pmod{341}，而341 = 11 \times 31是一個偽素數。所有的偽素數都是此假說的反例。

卡邁克爾數
如前述，中國猜想是有反例的。符合中國猜想的條件但不是素数的数被称为伪素数。

更极端的反例是卡邁克爾數：假設a與561互质，則a^{560}被561除都余1。这样的数被称为卡邁克爾數，561是最小的卡邁克爾数。Korselt在1899年就给出了卡邁克爾數的等价定义，但直到1910年才由卡邁克爾（Robert Daniel Carmichael）发现第一个卡邁克爾数：561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡邁克爾数有无穷多个。

证明
方法一
（i）若a是整数，p是质数，且\gcd(a,p)=1。若p不能整除x-y，则p不能整除a(x-y)。取整數集A为所有小於p的正整数集合（A构成p的完全剩余系，即A中不存在两个数同余p），B是A中所有的元素乘以a组成的集合。因为A中的任何两个元素之差都不能被p整除，所以B中的任何两个元素之差也不能被p整除。

換句話說，\gcd(a,p)=1，考慮a, 2a, 3a,....(p-1)a共(p-1)個數，將它們分別除以p，餘數分別為r_1,r_2,r_3,....,r_{p-1}，則集合\{r_1,r_2,r_3,....,r_{p-1}\}為集合\{ 1,2,3,\ldots,(p-1) \}的重新排列，即1,2,3,\ldots,(p-1) 在餘數中各出現恰好一次；這是因為對於任兩個相異ka而言（k=1,2,3,\ldots,(p-1)），其差不是p的倍數（所以不會有相同餘數），且任一個ka亦不為p的倍數（所以餘數不為0）。因此
:1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) \equiv a \cdot 2a \cdot 3a \dots\cdot(p-1)a \pmod{ p},
即
:W \equiv W\cdot a^{p-1} \pmod{p},

在这里W=1\cdot 2\cdot 3\cdot \ldots\cdot (p-1)，且(W,p)=1，因此将整个公式除以W即得到：

:a^{p-1} \equiv 1 \pmod{p}
:也即 a^p \equiv a \pmod{p}
（ii）若p整除a，则显然有p整除a^{p}，即a^p \equiv a\equiv 0 \pmod{p}。

方法二
若p为质数，n为整数，且1 \le n\le p-1。考慮二項式係數\tbinom{p}{n}=\tfrac{p!}{n!(p-n)!}，因為n不為p或0，則由於分子有質數p，但分母不含p，故分子的p能保留，不被約分而除去，即\tbinom{p}{n}恆為p的倍數。

再考慮(a+1)^p的二項式展開，模p，則
:(a+1)^p \equiv \dbinom{p}{p}a^p+\dbinom{p}{p-1}a^{p-1}+\dbinom{p}{p-2}a^{p-2}+\dots+\dbinom{p}{2}a^2+ \dbinom{p}{1}a^1+ \dbinom{p}{0}a^0
:\equiv \dbinom{p}{p}a^p+ \dbinom{p}{0}a^0
:\equiv a^p+1 \pmod{p}

因此
:(a+1)^p \equiv a^p+1
:\equiv (a-1)^p+1+1
:\equiv (a-2)^p+1+1+1
:\equiv (a-3)^p+1+1+1+1
:\dots
:\equiv \begin{matrix} \underbrace{1+1+\dots+1+1 } \\ a+1 \end{matrix}
:\equiv a+1 \pmod{p}
因為a^p+1 \equiv a+1 \pmod{p}，兩邊同減1，即得a^p \equiv a \pmod{p}。。这里只给出a不是p的倍数时 a^{p-1} \equiv 1 \pmod{p}的证明。

对于所有p的非倍数整数b，\pmod{p}的同余集合对乘法构成一个群，记作：

\{\overline{1},\overline{2},\overline{3} , ... ,\overline{p-1}\}

\overline{n} 为\pmod{p}余数为n的所有整数集合（因为b不是p的倍数，所以不会出现 \overline{0}）。这个群的阶是 p-1，单位元为 \overline{1}。根据群的基本原理可得:

b^r \in \overline{1}，（r为b的阶），即

b^r \equiv 1 \pmod{p}

根据拉格朗日定理（的推论），r 必是群的阶p-1的约数，可得

b^{p-1} \equiv 1 \pmod{p}

b为所有p的非倍数整数，因此

a^{p-1} \equiv 1 \pmod{p}

证毕。

應用
*計算2^{100}除以13的餘數
:2^{100} \equiv 2^{12 \times 8+4}
:\equiv (2^{12})^8 \cdot 2^4
:\equiv 1^8 \cdot 16
:\equiv 16
:\equiv 3 \pmod{13}
故餘數為3。

*證明對於任意整數a而言，a^{13}-a恆為2730的倍數。
**易由a^{p-1} \equiv 1 \pmod{p}推得a^{n(p-1)+1} \equiv 1^n \cdot a \equiv a \pmod{p}，其中n為正整數。
*故對指數13操作如下：13減1為12，12的正因數有1, 2, 3, 4, 6, 12，分別加1，為2, 3, 4, 5, 7, 13，其中2, 3, 5, 7, 13為質數，根據定理的延伸表達式，a^{13}-a為2的倍數、為3的倍數、為5的倍數、為7的倍數、為13的倍數，即2357*13=2730的倍數。
*證明對於任意整數a而言，a^{22}-a^{2}恆為3300的倍數。

*a^{22}-a^2為132的倍數。
*#模仿前述操作，11減1為10，10的正因數有1, 2, 5, 10，分別加1，為2, 3, 6, 11，其中2, 3, 11為質數，因此a^{11}-a為2, 3, 11的最小公倍數的倍數，即66的倍數。
*#考慮a^{11}+a，因為奇數的11次方仍為奇數，且奇數與奇數之和為偶數，故當a為奇數時，a^{11}+a為偶數；同理可知當a為偶數時，a^{11}+a仍為偶數。因此當a為任意整數時，a^{11}+a為偶數。
*#因此a^{22}-a^2=(a^{11}-a)(a^{11}+a)=66的倍數 \times 2的倍數=132的倍數。
*a^{22}-a^2為25的倍數。
**由後文的欧拉定理可知a^{20} \equiv 1 \pmod {25}（當a與25互質時），即a^{21} \equiv a \pmod {25}（當a為任意整數時）。因此a^{22}-a^2=a(a^{21}-a)為25的倍數。
*因此a^{22}-a^2為132與25的的最小公倍數的倍數，即3300的倍數。

推广
欧拉定理
费马小定理是欧拉定理的一个特殊情况：如果 (a,n)=1 ，那么
:a^{\varphi (n)} \equiv 1 \pmod{n}
这里 \varphi(n) 是欧拉函数。欧拉函数的值是所有小于或等于 n 的正整数中与 n 互質的数的个数。假如 n 是一个素数，则 \varphi(n)=n-1 ，即费马小定理。

;证明
上面证明费马小定理的群论方法，可以同理地证明欧拉定理。

考虑所有与 n 互素的数，这些数模 n 的余数所构成的集合，记为 {\cal S}，并将群乘法定义为相乘后模 n 的同余。显然 {\cal S} 是一个群，因为它对群乘法封闭（若 (a,n)=1 和 (b,n)=1 则 (ab,n)=1），含幺元（即“1”），且任何一个元素 a 的逆元素也在集合中（因为若 a\in{\cal S} 则由群乘法封闭性任何a 的幂次都在 {\cal S} 中，所以 \langle a\rangle 是 {\cal S} 这个有限集的子集）。根据定义， {\cal S} 的阶是 \varphi(n)，于是根据拉格朗日定理， {\cal S} 中任何一个元素的阶必整除 \varphi(n)。证毕。

卡邁克爾函數
卡邁克爾函數比欧拉函数更小。费马小定理也是它的特殊情况。
:a^{\lambda (n)} \equiv 1 \pmod{n}

多项式除法
因為p|x^p-x \Rightarrow p^k|(x^p-x)^k

所以由x^N\pmod{(x^p-x)^k}的結果可以得出x^N\pmod{p^k}的結果

用多項式除法可以得出x^N除以(x^p-x)^k的次數少於p^k的餘式

例如3 \mid x^3-x，由多項式除法得到x^5=(x^2+1)(x^3-x)+x，則x^5\equiv x\pmod{3}

這個餘式的一般結果是：

\displaystyle x^{pk} \equiv \sum_{i=1}^k(-1)^{i-1} \binom{k}{i} x^{pk-(p-1)i} \pmod {p^k}（除式）

\displaystyle x^{pk+(p-1)n} \equiv \sum_{i=1}^k(-1)^{i-1} \binom{n+i-1}{i-1} \binom{n+k}{k-i} x^{pk-(p-1)i} \pmod {p^k}

n=0时为除式，用数学归纳法证明余式。

:求x^{1000}\pmod{5^2}

x^{10+4n} \equiv(n+2)x^6 -(n+1)x^2 \pmod {5^2}

x^{1000} \equiv 249x^8 -248x^4 \equiv 24x^8 -23x^4 \pmod{5^2}

注释
参见
*费马大定理
*拉格朗日定理

參考