オイラーの定理(Euler's theorem)
オイラーの名前を冠した定理は沢山ありますが, これもそのうちの一つです.
オイラーのφ関数
オイラーのφ関数 は, 以下の自然数で と互いに素であるものの個数を表します. 例として,(1, 3, 7, 9が10と互いに素)
(1, 5, 7, 11が12と互いに素)
特に, 素数 に対しては, より小さい自然数はすべて と互いに素なので,
となります.
上で紹介しているオイラーの定理の として素数 を与えると, フェルマーの小定理
となることが分かります.
証明
ここで紹介する証明方法は, そのままフェルマーの小定理の証明にもなります. (フェルマーの小定理の証明の証明Ⅲ参照).
と互いに素で 以下の自然数の集合を とし, その要素を小さい順に とします. (たとえば, の場合, で ).
ここで, 新たな集合
を考えます. ここで, 次の補題を証明します. また, 以下の合同式の法はすべて とします.
(補題) の各要素 を で割った余りはすべて異なり, かつそれは の要素となっている.
(証明)まず で割った余りがすべて異なることを示す.は と互いに素なので,
ところが, はともに 以下の自然数なので, となり矛盾. よって の要素を で割った余りはすべて異なる.
次に, を で割った余りが の要素でない, つまり と互いに素でないと仮定すると, も と互いに素でないことになり, 矛盾する. よって割った余りは の要素である.
以上より補題は示された.
補題より, 集合 の各要素を で割った余りは の要素と1対1に対応している(並べ替えになっている)ので, それぞれの要素を全て掛け合わせたものは合同で,
は と互いに素なので,
.