オイラーの定理(整数論)

この記事の所要時間: 346

オイラーの定理(Euler’s theorem)

自然数 \(a, n\) に対して, \(a\) と \(n\) が互いに素であるとき, 次の式が成り立つ.

\[a^{\phi(n)}\equiv 1\pmod{n}\]

但し, \(\phi(n)\)はオイラーの\(\phi\)関数.

オイラーの名前を冠した定理は沢山ありますが, これもそのうちの一つです.

オイラーのφ関数

オイラーのφ関数 \(\phi(n)\)は, \(n\) 以下の自然数で \(n\) と互いに素であるものの個数を表します. 例として,

\(\phi(10)=4\) (1, 3, 7, 9が10と互いに素)

\(\phi(12)=4\) (1, 5, 7, 11が12と互いに素)

特に, 素数 \(p\) に対しては, \(p\) より小さい自然数はすべて \(p\) と互いに素なので,

\[\phi(p)=p-1\]

となります.

上で紹介しているオイラーの定理の \(n\) として素数 \(p\) を与えると, フェルマーの小定理

\[a^{p-1}\equiv 1\pmod{p}\]

となることが分かります.

証明

ここで紹介する証明方法は, そのままフェルマーの小定理の証明にもなります. (フェルマーの小定理の証明の証明Ⅱ参照).

\(n\) と互いに素で \(n\) 以下の自然数の集合を \(P\) とし, その要素を小さい順に \(p_1, p_2, \ldots, p_{\phi(n)}\) とします. (たとえば, \(n=10\) の場合, \(P=\{1, 3, 7, 9\}\) で \(p_1=1, p_2=3, p_3=7, p_4=9\)).

ここで, 新たな集合

\[Q=\{ap_1, ap_2, \ldots, ap_{\phi(n)}\}\]

を考えます. ここで, 次の補題を証明します. また, 以下の合同式の法はすべて \(n\) とします.

(補題) \(Q\) の各要素 \(ap_1, ap_2, \ldots, ap_{\phi(n)}\) を \(n\) で割った余りはすべて異なり, かつそれは \(P\) の要素となっている.

(証明)まず \(n\) で割った余りがすべて異なることを示す.

背理法で, \(1\leqq\alpha<\beta\leqq\phi(n)\) をみたすある自然数 \(\alpha, \beta\) に対して \(ap_\alpha\equiv ap_\beta\) と仮定すると,

\[a(p_\alpha-p_\beta)\equiv 0\]

\(a\) は \(n\) と互いに素なので,

\[p_\alpha-p_\beta\equiv 0\]

ところが, \(p_\alpha, p_\beta\) はともに \(n\) 以下の自然数なので, \(p_\alpha=p_\beta\) となり矛盾. よって \(Q\) の要素を \(n\) で割った余りはすべて異なる.

次に, \(ap_i\) を \(n\) で割った余りが \(P\) の要素でない, つまり \(n\) と互いに素でないと仮定すると, \(ap_i\) も \(n\) と互いに素でないことになり, 矛盾する. よって割った余りは \(P\) の要素である.

以上より補題は示された.

補題より, 集合 \(Q\) の各要素を \(n\) で割った余りは \(P\) の要素と1対1に対応している(並べ替えになっている)ので, それぞれの要素を全て掛け合わせたものは合同で,

\[(ap_1)(ap_2)\cdots(ap_{\phi(n)})\equiv p_1p_2\cdots p_{\phi(n)}\]

\[a^{\phi(n)}p_1p_2\cdots p_{\phi(n)}\equiv p_1p_2\cdots p_{\phi(n)}\]

\(p_1, p_2, \cdots, p_{\phi(n)}\) は \(n\) と互いに素なので,

\(a^{\phi(n)}\equiv 1 \pmod{n}\).

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください