费马小定理

维基百科,自由的百科全书
跳转至: 导航搜索

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

a^p \equiv a \pmod{p}

如果a不是p的倍数,这个定理也可以写成

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

这个书写方式更加常用。(符号的应用请参见同餘。)

历史[编辑]

皮埃爾·德·費馬

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

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

有些數學家獨立製作相關的假說(有時也被錯誤地稱為中國的假說),當2^{p} \equiv 2 \pmod{p}成立時,p是素數。這是費馬小定理的一個特殊情況。然而,這一假說的前設是錯的:例如,2^{341} \equiv 2 \pmod{341},而341=11×31是一個偽素數。所有的偽素數都是此假說的反例。

卡邁克爾數[编辑]

所述,中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。

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

证明[编辑]

方法一[编辑]

若n不能整除a - b,x>0,(x,n)=1,則n也不能整除x(a-b)。取整數集A为所有小於p的(A构成p的完全剩余系,即A中不存在两个数同余p),B是A中所有的元素乘以a组成的集合。因为A中的任何两个元素之差都不能被p整除,所以B中的任何两个元素之差也不能被p整除。

換句話說,gcd(a,p)=1,考慮1*a, 2*a, 3*a,....(p-1)*a共(p-1)個數,將它們分別除以p,餘數分別為r1,r2,r3,....,rp-1,則集合{r1,r2,r3,...,rp-1}為集合{1,2,3,...,(p-1)}的重新排列,即1,2,3,....,(p-1)在餘數中恰好各出現一次;這是因為對於任兩個相異k*a而言(k=1,2,3....(p-1)),其差不是p的倍數(所以不會有相同餘數),且任一個k*a亦不為p的倍數(所以餘數不為0)。因此

1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) \equiv (1 \cdot a)\cdot(2 \cdot a)\cdot\dots\cdot ((p-1) \cdot a) \pmod{ p},

W \equiv W\cdot a^{p-1} \pmod{p},

在这里W=1·2·3·...·(p-1),且(W, p) = 1,因此将整个公式除以W即得到:

a^{p-1} \equiv 1 \pmod{p}[3]

方法二[编辑]

考慮二項式係數\tbinom{p}{n}=\tfrac{p!}{n!(p-n)!},n不為p或0,由於分子有質數p,但分母不含p,故分子的p能保留,不被約分而除去,即\tbinom{p}{n}恆為p的倍數。

再考慮(b+1)p的二項式展開,模p,則

(b+1)^p \equiv \dbinom{p}{p}b^p+\dbinom{p}{p-1}b^{p-1}+\dbinom{p}{p-2}b^{p-2}+\dots+\dbinom{p}{2}b^2+ \dbinom{p}{1}b^1+ \dbinom{p}{0}b^0 \pmod{p}
\equiv \dbinom{p}{p}b^p+ \dbinom{p}{0}b^0 \pmod{p}
\equiv b^p+1 \pmod{p}

因此

(b+1)^p \equiv b^p+1 \pmod{p}
\equiv (b-1)^p+1+1 \pmod{p}
\equiv (b-2)^p+1+1+1 \pmod{p}
\equiv (b-3)^p+1+1+1+1 \pmod{p}
\dots
\equiv \begin{matrix} \underbrace{1+1+\dots+1+1 } \\ b+1 \end{matrix} \pmod{p}
\equiv b+1 \pmod{p}

令b=a-1,即得a^p \equiv a \pmod{p}[3]

應用[编辑]

  • 計算2^{100}除以13的餘數
2^{100} \equiv 2^{12 \times 8+4} \pmod{13}
\equiv (2^{12})^8 \cdot  2^4 \pmod{13}
\equiv 1^8 \cdot  16 \pmod{13}
\equiv 16 \pmod{13}
\equiv 3 \pmod{13}

故餘數為3。

  • 證明對於任意整數a而言,a^{13}-a恆為2730的倍數。

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的倍數,即2*3*5*7*13=2730的倍數。

推广[编辑]

欧拉定理[编辑]

费马小定理是欧拉定理的一个特殊情况:如果na的最大公约数是1,那么

a^{\varphi (n)} \equiv 1 \pmod{n}

这里φ(n)是欧拉函数。欧拉函数的值是所有小于或等于n的正整数中与n互質的数的个数。假如n是一个素数,则φ(n) = n-1,即费马小定理。

卡邁克爾函數[编辑]

卡邁克爾函數比欧拉函数更小,费马小定理也是它的特殊情况。

a^{\lambda (n)} \equiv 1 \pmod{n}

多项式除法[编辑]

p|x^p-x \Rightarrow p^k|(x^p-x)^k

除式:\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时为除式,用数学归纳法证明余式。[4]

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}

参见[编辑]

參考[编辑]

  1. ^ Fermat's Little Theorem.WolframMathWorld.(英文)
  2. ^ A proof of certain theorems regarding prime numbers
  3. ^ 3.0 3.1 許介彥. 費馬小定理. 科學教育月刊 (私立大葉大學 電機工程學系). 2006年-10, (第293期): 37–44. (原始内容存档于2015-04-18). 
  4. ^ 多项式除法解高次同余.