フェルマーの小定理とは

/代数学

フェルマーの小定理

フェルマーの小定理とは、素数の性質についての定理であり、実用面でもRSA暗号に応用されています。$p$ を素数、$m$ を $p$ と互いに素な整数とすると、以下が成り立ちます。

$$m^{p-1}\pmod{p}=1  -①$$

フェルマーの小定理を導く

$p$ を素数、$a,b$ を整数とし、次の二項定理により、

$$(a+b)^p=\sum_{k=0}^p\frac{p!}{k!(p-k)!}a^kb^{p-k}  -②$$

$$=a^p+pa^{p-1}b+\frac{1}{2}p(p-1)a^{p-2}b^2+\dots+pab^{p-1}+b^p$$

②の係数は常に自然数となりますが、分子の $p$ は素数で割り切れないため、②の最初と最後の係数以外は常に $p$ の倍数となります。従って、以下が成り立ちます。

$$(a+b)^p\equiv(a^p+b^p)\pmod{p}  -③$$

これを一般化すると、

$$(a_1+a_2+\cdots+a_m)^p\equiv(a_1^p+a_2^p+\cdots+a_m^p)\pmod{p}$$

ここで、$a_1=\cdots=a_m=1$ とすると、

$$m^p\equiv m\pmod{p}$$

両辺を $m$ で割ると①が得られます。

フェルマーの小定理の対偶

互いに素な2つの整数 $m,p$ について、

$$m^{p-1}\pmod{p}\ne1$$

が成り立つならば、$p$ は合成数である。

対偶を導く

$p$ が合成数の場合、③が成り立たないことを示します。②より、

$$(a+b)^p=a^p+\cdots+\frac{p!}{k!(p-k)!}a^kb^{p-k}+\dots+b^p$$

ここで、$p=mn$($m\le n$)とすると、$k=m$ の係数は以下になります。

$$\frac{p!}{m!(p-m)!}=\frac{p(p-1)\cdots(p-m+1)}{1\cdot2\cdots m}$$

右辺の分子は、$m$ 個の連続した自然数の掛算になりますが、先頭の $p$ 以外に $m$ で割り切れる自然数はありません。しかし、この右辺は自然数になる(割り切れる)ため、$p$ は $m$ で割る必要があります。そうすると、この項は $p$ の倍数でなくなるため、結果、③が成り立たなくなります。

 

数学
解析学、代数学、幾何学、統計学、論理・基礎論、情報・暗号、機械学習、金融・ゲーム理論、高校数学
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論

 

タイトルとURLをコピーしました