3

フェルマーの小定理とその証明

87
1
$$$$
フェルマーの小定理

素数 $p$ に対し,$a$$p$の倍数でない自然数とすると,

$a^{p-1} \equiv 1 ~(\mbox{mod}~~ p) $

が成り立つ.

定理中に現れた式は合同式というもので,両辺を$p$で割った時の余りは等しいことを示す.

なるべく高校生でもわかるように

$1 \le k \le p-1$ を満たす自然数$k$を用意する.次に,以下のような合同式を考え,自然数$r_k$$1 \le r_k \le p-1$) を考える.

$k \cdot a \equiv r_k ~(\mbox{mod}~~ p).$ (1)

つまり$r_k$$k \cdot a$$p$で割った余りである.余りが $0$ にならないのは,$p$ が素数であり,$a$$p$ が互いに素だからである.式(1)を $1 \le k \le p-1$の範囲で全て掛け算する.

$(p-1)! \cdot a^{p-1} \equiv \Pi_{k=1}^{p-1} r_k ~(\mbox{mod}~~ p).$ (2)

ここでもしある $i, j$ を選び $i \ne j$ だとする.この時に $r_i = r_j$ が成り立つと,式(1)を $i, j$ の場合について選んで引き算することで,

$(i-j) a \equiv (r_i -r_j)~(\mbox{mod}~~ p),$

となる.$a, p$は互いに素で,$1 \le i, j \le p$ であるから,$|i-j| < p$であり,$i-j$$p$ が互いに素である.よって左辺は$p$で割り切れないから右辺も割り切れない.このことから,

$r_i - r_j \ne 0 ,$

が示される.つまり $r_k ~(1 \le k \le p-1)$ には $1$ から $p-1$ までの自然数が1個ずつ含まれる.このことを用いると,

$(p-1)! = \Pi_{k=1}^{p-1} r_k$ ,

となる.これらは $p$ で割り切れないので,合同式 (2) の両辺に割り算が適用でき,

$a^{p-1} \equiv 1 ~(\mbox{mod}~~ p) $

が示される.

投稿日:2020113

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

sakura
8
1381

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中