費馬小定理
語出維基大典,自由之大典矣
費馬小定理者,基本數論一定理也。其曰: 若p為質數,則任一整數 a 之p − 1次方減 p 為p之倍數,書之如下:
,且a不為p之倍數
若a不為p之倍數, 則: .
費馬小定理為歐拉定理之殊. 歐拉定理表之如下:
,且(a,n) = 1;
其中φ為歐拉 phi 函數.
[修] 證明
1,2,3,......,p − 1皆互不同餘於彼此模p,a,2a,3a,......,(p − 1)a亦然,故兩者皆為模p之一剩餘系也,凡模質數p之剩餘系所有數相乘,皆同餘於 − 1(威爾遜定理),故,由是可得
,故得
,或書之
也
[修] 參見
- 同餘
- 費馬
- 費馬最後定理
- 歐拉 phi 函數
Categories: 數論 | 定理