数論におけるオイラーの定理、ファイ関数とは？

どうも、木村（@kimu3_slime）です。

今回は、数論におけるオイラーの定理、ファイ関数について紹介します。

オイラーの定理とは
簡単なケースで確かめる
オイラーの定理の証明
こちらもおすすめ

オイラーの定理とは

数論に置けるオイラーの定理は、次の主張です。

\(a\)を整数とする。\(n\)を正の整数で、\(a,n\)は互いに素とする。このとき、次の整数の合同が成り立つ。

\[ \begin{aligned}a^{\phi(n)} \equiv 1 \,(\mathrm{mod}\, n)\end{aligned} \]

ここで、\(\phi (n)\)は\(1\)から\(n\)までの整数のうち、\(n\)と互いに素な整数の個数を表す。

これはフェルマーの小定理\(a^{p-1} \equiv 1 \,(\mathrm{mod}\, p)\)の一般化となっています。\(n\)が素数\(p\)のとき、\(p\)と\(1,2,\cdots,p-1,p\)で互いに素なのは\(1,2,\cdots,p-1\)の\(p-1\)個なので、\(\phi(p)=p-1\)です。フェルマーの小定理は、オイラーの定理の特殊なケースと言えます。

ここで登場する数論的関数\(\phi\)は、オイラーの\(\phi\)関数（ファイ関数 Euler’s phi-function）、トーシェント関数（totient function）などと呼ばれています。

簡単なケースで確かめる

まずは簡単なケースで、オイラーの定理が成り立っているのかどうか、確かめてみましょう。

\(a\)を\(n\)と互いに素な整数とします。\(n\)が素数のときはフェルマーの小定理として確かめたので、\(n\)が合成数のときを考えます。

\(n=4\)のとき、\(2\)は\(4\)と互いに素でなく、\(1,3\)が\(4\)と互いに素なので、\(\phi(4)=2\)です。\(a^2 \equiv 1 \,(\mathrm{mod}\, 4)\)は正しいのでしょうか？

\(a\)を\(4\)で割ったあまりを\(r\)として、\(r\)に応じて場合分けして考えます。合同式の性質より、\(a^2 \equiv r^2 \,(\mathrm{mod}\, 4)\)です。\(a,4\)は互いに素なので、割り切れる\(r=0\)ケースはありえません。\(r=1\)のとき、\( r^2\equiv 1 \,(\mathrm{mod}\, 4)\)です。\(r=2\)のときはありえません。\(a\equiv 2 \,(\mathrm{mod}\, 4)\)と仮定すると、\(4\)は\(2\)の倍数なので、\(a\)は\(2\)の倍数となってしまい、\(a,4\)が互いに素であったことに矛盾します。\(r=3\)のとき、\(r^2 \equiv 9 \equiv 1\,(\mathrm{mod}\, 4)\)です。よって、いずれにせよ\(a^2 \equiv 1 \,(\mathrm{mod}\, 4)\)が成り立つことがわかりました。

既に原理はわかってきた感じがしますが、一般的なやり方を模索する必要があります。

\(n=6\)のとき、\(6\)と互いに素なのは\(1,5\)なので、\(\phi(6)=2\)です。\(a\)を\(6\)で割ったあまりを\(r\)として、\(r\)に応じて場合分けして考えます。合同式の性質より、\(a^2 \equiv r^2 \,(\mathrm{mod}\, 6)\)です。\(r=0,2,3,4\)はありえません。それぞれ、\(6,2,3,2\)が公約数となってしまいます。なので、\(r=1,5\)のケースを考えれば良いわけです。\(r=5\)のときは、\(r^2 \equiv 25 \equiv 1 \,(\mathrm{mod}\, 6)\)です。よって、いずれにせよ\(a^2 \equiv 1 \,(\mathrm{mod}\, 6)\)がわかりました。

もう少し整理しましょう。\(r\)の可能性としてありうるのは、\(6\)と互いに素な数\(1,5\)です。そして、\(a\)のあまりが\(1\)のときは\(5a\)のあまりが\(5\)、\(a\)のあまりが\(5\)のときは\(5a\)のあまりが\(25 \equiv 1\)となっています。つまり、\(a,5a\)はそれぞれが\(1,5\)のいずれかに合同です。そこで合同式の積を取れば、\(5a^2 \equiv 5 \,(\mathrm{mod}\, 6)\)です。ここで\(5,6\)は互いに素なので、合同式の性質から、\(a^2 \equiv 1 \,(\mathrm{mod}\, 6)\)が得られるわけですね。

これが通用するか、\(n=9\)のときで試してみます。\(9\)と互いに素なのは\(1,2,4,5,7,8\)なので、\(\phi (9)=6\)です。

\(a,2a,4a,5a,7a,8a\)はいずれも互いに合同ではありません。いずれかが合同であるとすると、\(a\)と\(9\)が\(2\)以上の公約数を持つことになり、\(a,n\)が互いに素であることに反します。

そして、\(a\)で割ったあまりを\(r\)としましょう。\(r\)が\(0,3,6\)のときは、\(a,n\)が互いに素であったことに矛盾するのでありあえません。\(r\)は\(1,2,4,5,7,8\)のいずれかです。

\(a\equiv r\)で、\(a\not \equiv 2a\)なので、\(2a \not \equiv r\)です。これを繰り返すことで、\(a,2a,4a,5a,7a,8a\)はそれぞれが\(1,2,4,5,7,8\)のいずれかに合同であることがわかります。それらの合同式の積を取れば、\(2\cdot4\cdot5\cdot7\cdot8a^{\phi(9)}\equiv 2\cdot4\cdot5\cdot7\cdot8\,(\mathrm{mod}\, 9)\)です。\(2\cdot4\cdot5\cdot7\cdot8,9\)は互いに素なので、合同式の性質から、\(a^{\phi(9)}\equiv 1\,(\mathrm{mod}\, 9)\)が得られました。

オイラーの定理の証明

これで一般的な方法で証明できそうです。

\(a\)を\(n\)と互いに素な整数とします。\(n\)と互いに素な正の整数は\(\phi(n)\)個あるわけですが、それを\(a_1,a_2,\dots,a_{\phi(n)}\)と表します。\(1\)は常に互いに素なので、\(a_1=1\)としておきましょう。

\(a_1a,a_2a,\dots,a_{\phi(n)}a\)はいずれも互いに合同ではありません。いずれかが合同であるとすると、\(a\)と\(n\)が\(2\)以上の公約数を持つことになり、\(a,n\)が互いに素であることに反します。

\(a\)を\(n\)で割ったあまりを\(r\)、\(0 \leq r \leq n-1\)とすると、\(a\equiv r \,(\mathrm{mod}\, n)\)です。そして、\(r\)が\(n\)の約数となる可能性はありません。仮に約数であるとすると、\(a,n\)が\(2\)以上の公約数を持つことになり、\(a,n\)が互いに素であることに反します。したがって、\(r\)は\(n\)と互いに素になるしかなく、\(a_1,a_2,\dots,a_{\phi(n)}\)のいずれかに等しいです。

\(a\equiv r \,(\mathrm{mod}\, n)\)と、\(a=a_1a,a_2a,\dots,a_{\phi(n)}a\)が互いに合同でないことより、\(a_2,\dots,a_{\phi(n)}a\)は\(r\)に合同ではありません。これを繰り返せば、\(a_1a,a_2a,\dots,a_{\phi(n)}a\)は、\(a_1,a_2,\dots,a_{\phi(n)}\)のいずれかに合同です。

よって、合同式の積を取れば、\(a_1a_2\dots a_{\phi(n)} a^{\phi(n)}\equiv a_1a_2\dots a_{\phi(n)} \,(\mathrm{mod}\, n)\)です。\(a_1a_2\dots a_{\phi(n)},n\)は互いに素なので、合同式の性質より割ることができて、\( a^{\phi(n)}\equiv 1 \,(\mathrm{mod}\, n)\)が得られました。

以上、数論におけるオイラーの定理、ファイ関数とは何か、具体例や証明を紹介してきました。

フェルマーの小定理の一般化として、オイラーの定理は、なにかのべきで表される数\(a^k\)のあまりを求めるのに役立ちます。

例えば\(a=10\)で\(n=27\)とすれば、\(27,10\)は互いに素です。\(\phi(27)=\phi(3^3)=3^3(1-\frac{1}{3})=18\)と計算できることが知られており、オイラーの定理より\(10^{18} \equiv 1 \,(\mathrm{mod}\, 27)\)です。したがって、\(10^{18}-1= 27k\)で、\(\frac{10^{18}-1}{9}= 3k\)です。左辺は\(1\)が続く数であり、\(3 \mid 111111111111111111\)がわかります。\(5\)の倍数でない奇数は、各桁に1が並ぶある数を割り切ることを同様にして示せます。ここで用いたオイラーのファイ関数の性質・計算方法は、別の記事で紹介するかもしれません。

互いに素な数だけを考えるという発想があると、フェルマーの小定理に似た単純な形の式が導かれる、というのは見事なものですね。

木村すらいむ（@kimu3_slime）でした。ではでは。