FANDOM


費馬小定理是指對於任意質數p及任意正整數a而言,a的p次方減a可為p除盡,或當a與p互質時,a的p-1次方除以p的餘數為1。

費馬小定理的可推廣至對任意互質正整數的a和m上,對任意的a而言,當a與m互質時,a的$ \varphi(m) $次方除以m的餘數為1,其中$ \varphi(m) $是不大於m且與m互質的正整數個數。

證明编辑


此處所給之證明可能不嚴謹,或有所疏漏,還請大家校驗與修正


以下證明對質數的狀況。

若p為質數,則1、2、3‧‧‧p-1等數皆與p互質,且{1,2,3,......,p-1}構成模p的一個完全剩餘系,對於任意與p互質的x而言,x、2x、3x‧‧‧等也與p互質,且{x,2x,3x,......,(p-1)x}亦構成模p的一個完全剩餘系,因此,$ \prod_{i=1}^{p-1} xi \equiv \prod_{i=1}^N i \pmod{m} $,故$ x^{p-1}\prod_{i=1}^N i \equiv \prod_{i=1}^N i \pmod{m} $,而$ (\prod_{i=1}^N i,p) = 1 $,故可做除法將兩邊的$ \prod_{i=1}^N $除去,故得$ x^{p-1} \equiv 1 \pmod{m} $,定理得證。

參見编辑