費馬小定理

語出維基大典,自由之大典矣

費馬小定理者,基本數論一定理也。其曰: 若p為質數,則任一整數 a 之p − 1次方減 p 為p之倍數,書之如下:

a^p \equiv a \pmod{p},且a不為p之倍數

a不為p之倍數, 則: a^{p-1} \equiv 1 \pmod{p}.

費馬小定理為歐拉定理之殊. 歐拉定理表之如下:

a^{\phi (n)} \equiv 1 \pmod{n},且(a,n) = 1;

其中φ為歐拉 phi 函數.

[] 證明

1,2,3,......,p − 1皆互不同餘於彼此模pa,2a,3a,......,(p − 1)a亦然,故兩者皆為模p之一剩餘系也,凡模質數p之剩餘系所有數相乘,皆同餘於 − 1(威爾遜定理),故1 \times 2 \times 3 \times ...... \times p-1 \equiv a  \times  2a  \times  ...... (p-1)a \pmod{p},由是可得1 \times 2 \times 3 \times ...... \times p-1 \equiv a^{p-1} (1 \times 2 \times 3 \times ...... \times p-1) \pmod{p},故得1 \equiv a^{p-1} \pmod{p},或書之a^{p-1} \equiv 1 \pmod{p}

[] 參見

  • 同餘
  • 費馬
  • 費馬最後定理
  • 歐拉 phi 函數
Views