オイラーの定理

フェルマーの小定理・オイラーの関数からの続き

大人を過ぎてから初めて目にした概念はなかなか覚えられない。フェルマーの小定理がそれだ。鈴木貫太郎の大学入試数学チャンネルもなくなってしまったので，なおさらだ。

フェルマーの小定理は，素数を$p$とし，$p$とたがいに素な整数を $a$（gcd($a, p$)=1）として，$a^{p-1} \equiv 1 \quad ({\rm mod}\ p)$ 。あれれ，gcd($a, p$)=1 をはずせば，$a^p \equiv a \quad ({\rm mod}\ p)$）でもいいのか。

証明は次のとおり。

整数 $a, x$，素数$p$とする。二項定理で$(x+1)^p$を展開すると，

$(x+1)^p = x^p + C_1^p x^{p-1} 1^1 + C_2^p x^{p-2} 1^2 + \cdots + C_{p-1}^p x^1 1^{p-1} + 1^p$

ところで，上式の$C_k^{p-k}=\dfrac{p!}{k! (p-k)!}$であり，分母の$k<p, \ p-k < p\ $には分子の$\ p \ $を割り切る数は含まれていない。したがって，$(x+1)^p \equiv x^p+1 \quad ({\rm mod} \ p)$ である。

これから，$a^p \equiv (1+(a-1))^p \equiv 1 + (a-1)^p \quad ({\rm mod}\ p )$

$a^p \equiv 1+ (a-1)^p \equiv 1+ 1 + (a-2)^p \equiv \cdots \equiv  a + 0^p  \quad ({\rm mod} \ p )$

$a$と$p$は互いに素なので，両辺を$a$で割って，$a^{p-1} \equiv 1 \quad ({\rm mod} \ p)$

オイラーの定理は，フェルマーの小定理のべきの素数部分を拡張したものに相当する。

正の整数$m$に対して，集合$\ r(m) = \{a\ |\ 1 \le a \le m, \ {\rm gcd} (a, m) = 1\}$ を考え，その要素数をオイラー数 $\varphi(m)= \#r(m)$  とよんでいる。そこで，$r(m) = \{r_1, r_2, \cdots, r_{\varphi(m)} \}$。なお，$p$に対して，$\varphi(p) = p -1$。

集合 $r(m)$のすべての要素に$a$をかけて，${\rm mod}\  m$ をとれば，その集合 $ar(m) = \{ a r_1, a r_2, \cdots, a r_{\varphi(m)} \}$ は $r(m) = \{r_1, r_2, \cdots, r_{\varphi(m)} \}$と等しくなる。そこで，これらの要素の積を考えると，$a^{\varphi(m)} \Pi_{i=1}^{\varphi(m)} r_i \equiv \Pi_{i=1}^{\varphi(m)} r_i \quad ({\rm mod }\ m )$ なので，

オイラーの定理，$a^{\varphi(m)} \equiv 1 \quad  ({\rm mod }\ m )\ $ が得られる。

（注）なお，$ar(m) = \{ a r_1, a r_2, \cdots, a r_{\varphi(m)} \} \quad ({\mod \ m }) \equiv \{ r'_1, r'_2, \cdots, r'_{\varphi(m)} \} \ $の要素$\ r'_i \ $はすべて，$a, m$と互いに素であり，同じものは含まれない。

(1) $p, q$を素数として，$m=p q\ $である場合，$\varphi(m) = \varphi(p) \varphi(q)$ となる。

$\varphi(m)\ $は，$\{1,2, \cdots, m \}$から，$p$の倍数と$q$の倍数を除いたものになるので，それぞれ，$q$個，$p$個あるが，$p q$は両方で重なっている。そこで，$p, q$の倍数でないものの個数は，$\varphi(m) = pq -p - q +1 = (p-1) (q-1) = \varphi(p) \varphi(q)$ となる。3個以上の場合も同様。

(2) $p$ を素数，$k$を正整数として，$m = p^k\ $である場合，$\varphi(m) = p^k - p^{k-1} \ $ となる。これは，$\{ 1, 2, \cdots , p^k \}$ の中で，$\{ 1 p, 2 p, \cdots , p^{k-1} p\}$ は$m$と互いに素でないので，その個数を引けばよいからだ。

(3) これらを組み合わせると，$m = p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n}\ $ として，$\varphi(m) = m (1-1/p_1) (1-1/p_2) \cdots (1-1/p_n)$ となる。

図：オイラーのファイ関数のグラフ（Wikipediaから引用）

［１］オイラー関数の定義・性質４つとその証明（数学の景色）

［２］オイラーのファイ関数のイメージ（高校数学の物語）