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},定理得證。

參見编辑

您使用了广告屏蔽软件!


Wikia通过广告运营为用户提供免费的服务。我们对用户通过嵌入广告屏蔽软件访问网站进行了使用调整。

如果您使用了广告屏蔽软件,将无法使用我们的服务。请您移除广告屏蔽软件,以确保页面正常加载。