オイラー関数 φ(n) の公式とオイラーの定理｜包除原理による証明・a^φ(n)≡1 の証明・下2けたの例題【大学数学・東大京大レベル】

オイラー関数とオイラーの定理

正の整数 $n$ に対して、$1$ から $n$ までの整数のうち $n$ と互いに素なもの（最大公約数が1のもの）の個数を $\varphi(n)$ と書き、オイラー関数（オイラーのファイ関数）といいます。$\varphi(1)=1$ とします。

$n=p$（素数）のときは $\varphi(p)=p-1$ なので、オイラーの定理はフェルマーの小定理 $a^{p-1}\equiv1\pmod p$ になります。オイラーの定理は、フェルマーの小定理を素数でない $n$ に広げたものです。

証明

φ(n) の公式（包除原理）

$1$ から $n$ までのうち、$n$ と互いに素でない数は、$n$ の素因数 $p_1,\cdots,p_r$ のどれかでわり切れる数です。$1$ から $n$ までに $p_i$ の倍数は $\dfrac{n}{p_i}$ 個、$p_ip_j$ の倍数は $\dfrac{n}{p_ip_j}$ 個、…あります。包除原理より、どれでもわり切れない数の個数は

$$\varphi(n)=n-\sum_{i}\frac{n}{p_i}+\sum_{i<j}\frac{n}{p_ip_j}-\sum_{i<j<k}\frac{n}{p_ip_jp_k}+\cdots$$

右辺は、$n\left(1-\dfrac{1}{p_1}\right)\cdots\left(1-\dfrac{1}{p_r}\right)$ を展開した式とまったく同じです。たとえば $n=30$ なら

$$\varphi(30)=30-(15+10+6)+(5+3+2)-1=8=30\cdot\frac12\cdot\frac23\cdot\frac45$$

素数のべき $p^e$ なら、互いに素でないのは $p$ の倍数 $p^{e-1}$ 個だけなので $\varphi(p^e)=p^e-p^{e-1}$ です。

オイラーの定理

$1$ から $n$ までで $n$ と互いに素な数を $r_1,r_2,\cdots,r_m$（$m=\varphi(n)$）とします。$a$ と $n$ は互いに素とします。

1. $ar_1,ar_2,\cdots,ar_m$ は、どれも $n$ と互いに素です（$a$ も $r_i$ も $n$ と共通の素因数をもたない）。
2. これらを $n$ でわった余りはすべて異なります。もし $ar_i\equiv ar_j\pmod n$ なら、$n$ が $a(r_i-r_j)$ をわり切り、$a$ と $n$ は互いに素なので $n$ が $r_i-r_j$ をわり切ります。$|r_i-r_j|<n$ なので $r_i=r_j$。
3. よって、$ar_1,\cdots,ar_m$ の余りは、$r_1,\cdots,r_m$ を並べかえたものです。全部かけると

$$a^m\,r_1r_2\cdots r_m\equiv r_1r_2\cdots r_m\pmod n$$

$r_1r_2\cdots r_m$ は $n$ と互いに素なので、両辺をこれでわってよく、$a^{\varphi(n)}\equiv1\pmod n$ が示せました。

大学受験（数学A 整数の性質）での使い方

高校の範囲をこえる内容と入試での使い方

• 範囲外の内容：高校の数学Aの整数では、約数・倍数、ユークリッドの互除法、1次不定方程式などを学びます。オイラー関数 $\varphi(n)$ とオイラーの定理は教科書の範囲外です（合同式も発展として扱われることが多い内容です）。
• 答案で使うなら証明してから：証明は上のように短いので、記述式で使うときは「並べかえ」の議論を書いてから使うのが安全です。下2けた程度なら、$3^1,3^2,\cdots$ の余りを順に調べて「1にもどる周期」を見つける方法でも答案になります。
• 見当づけ・検算に強い：「$a^N$ をわった余り」「下何けた」の問題で、まず $\varphi(n)$ で周期の見当をつけ、答案では実際の周期を確かめて書く、という使い方がおすすめです。
• インターネットで使われるRSA暗号のしくみは、オイラーの定理が土台です。難関大の入試でも、整数のべき乗の余りの問題で背景になっていることがあります。

よくある間違い

• $a$ と $n$ が互いに素でないのに使う：$\varphi(10)=4$ ですが、$2^4=16\equiv6\pmod{10}$ で1になりません。
• $\varphi(mn)=\varphi(m)\varphi(n)$ をいつでも使う：成り立つのは $m,\ n$ が互いに素のときだけ。$\varphi(4)=2$ ですが $\varphi(2)\varphi(2)=1$ です。
• 素因数の個数を引くだけにする：$\varphi(12)$ は $12-2$ ではありません。$12\cdot\dfrac12\cdot\dfrac23=4$（1, 5, 7, 11）です。

練習問題

1. 大学受験 $\varphi(100)$ を求めなさい。
   答えと解説を見る

   $100=2^2\cdot5^2$ なので $100\cdot\dfrac12\cdot\dfrac45=40$
2. 大学受験 $7^{100}$ を $15$ でわった余りを求めなさい。
   答えと解説を見る

   $\varphi(15)=15\cdot\dfrac23\cdot\dfrac45=8$。$100=8\cdot12+4$ なので $7^{100}\equiv7^4=2401\equiv1\pmod{15}$。答え $1$
3. 大学受験 $\varphi(n)=\dfrac n2$ となる正の整数 $n$ をすべて求めなさい。
   答えと解説を見る

   $\left(1-\dfrac1{p_1}\right)\cdots\left(1-\dfrac1{p_r}\right)=\dfrac12$。$n$ が奇数だと、分母をはらって $2(p_1-1)\cdots(p_r-1)=p_1\cdots p_r$ となり、左辺は偶数・右辺は奇数で矛盾（$n=1$ も $\varphi(1)=1$ で不適）。$n$ が偶数なら $1-\dfrac12$ だけで $\dfrac12$ なので、ほかの素因数はない。答え $n=2^k$（$k\ge1$）

関連する公式

• フェルマーの小定理
• 合同式（mod の計算）
• 集合の要素の個数（包除原理）
• 最大公約数・最小公倍数
• ユークリッドの互除法
• 中国剰余定理

よくある質問

あわせて読みたい

• 合格大作戦 算数・数学公式辞典（公式一覧）