Fussy's Diary

先週から喉が痛く、今度は咳が止まらなくなりました。この時期になるといつもこうなるのですが、風邪というわけでもないんですよね。

以前、フェルマーの小定理の証明法を紹介したので、今度はこれを一般化したオイラーの定理を証明してみます。

-----------------------------------------------------------------------------
オイラーの定理

m を正の整数、a を m と互いに素な整数とするとき、

a^φ(m) ≡ 1 ( mod m )

が成り立つ。但し、φ(m) はオイラーの φ 関数で、1 から m の間で m と互いに素な数の個数
-----------------------------------------------------------------------------

(証明)

フェルマーの小定理の証明では、a が素数 p と互いに素ならば

a, 2a, 3a, ... ( p - 1 )a

を p で割った p - 1 個の剰余が、適当に順番を入れ替えることで重複なく

1, 2, 3, ... p - 1

と等しくなることを利用しました。これは、p が素数でなくても成り立つことは、証明の内容から容易に理解できます。さらに、a と b が互いに素なとき、a を b で割った剰余を r とすると、r と b も互いに素となります。もし、r と b に共通の因数があるとしたとき、その因数を k として r = kr', b = kb', a = qb + r とすれば、

a = qkb' + kr' より a = k( qb' + r' )

となるので、a が k を因数として持つことになり最初の仮定に反します。そこで、任意の(合成数も含めた)正数 m に対し、互いに素な数 a を選び、1 から m の中で m と互いに素な数だけを抽出し、先頭から順に連番 i を付けて b_i で表します。b_i は必ず 1 であり、その要素数はオイラーのΦ関数 φ(m) で表すことができます。このとき、

b₁a, b₂a, b₃a, ... b_φ(m)a

を m で割った φ(m) 個の剰余は重複がなく、しかも全て m と互いに素なので、適当に順番を入れ替えることで

b₁, b₂, b₃, ... b_φ(m)

と等しくなります。よって、

Π_i{1→φ(m)}( b_ia ) ≡ Π_i{1→φ(m)}( b_i ) ( mod m )

が成り立ち ( Π_i{1→φ(m)}(...) は ... の全要素の 1 から φ(m) までの積を表します )、左辺は a^φ(m)・Π_i{1→φ(m)}( b_i ) であり、Π_i{1→φ(m)}( b_i ) は m と互いに素なので

a^φ(m) ≡ 1 ( mod m )

となって、オイラーの定理が証明されました (証明終)

素数 p に対して φ(p) = p - 1 なので、オイラーの定理を素数に限定すればフェルマーの小定理と等しくなります。