数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

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


スポンサードリンク

オイラーの定理(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}.