オイラー関数 φ とその乗法性 | 初等整数論

1 オイラー関数

定義 1.1 (オイラー関数). 正の整数 $n$ に対して、 $1$ 以上 $n$ 以下の整数のうち、 $n$ と互いに素なものの個数を $\varphi(n)$ と書く。関数 $\varphi$ をオイラー関数 (Euler totient function) という。

例 1.2. $\gcd(1,1)=1$ なので、 $\varphi(1)=1$ である。 $1$ 以上 $6$ 以下で $6$ と互いに素な整数は $1,5$ なので、 $\varphi(6)=2$ である。

2 素数べきでの値

命題 2.1. $p$ を素数、 $k$ を正の整数とすると、

\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)

が成り立つ。特に、 $\varphi(p)=p-1$ である。

証明.§A4.2 定理 2.2により、 $p^k$ の素因数は $p$ だけである。したがって、整数が $p^k$ と互いに素でないことと、その整数が $p$ の倍数であることは同値である。 $1$ 以上 $p^k$ 以下の $p$ の倍数は $p,2p,\ldots,p^{k-1}p$ の $p^{k-1}$ 個なので、

\varphi(p^k)=p^k-p^{k-1}

となる。 $k=1$ とすると、 $\varphi(p)=p-1$ を得る。▨

3 互いに素な二数についての乗法性

命題 3.1. $m,n$ を互いに素な正の整数とすると、

\varphi(mn)=\varphi(m)\varphi(n)

が成り立つ。

証明. $m=1$ または $n=1$ の場合は、 $\varphi(1)=1$ から等式が従う。以下では $m,n\ge2$ とする。§A4.6 補題 2.1により、法 $mn$ の剰余類と、法 $m$ の剰余類と法 $n$ の剰余類の組は一対一に対応する。整数 $x$ が $mn$ と互いに素であることは、 $x$ が $m,n$ の両方と互いに素であることと同値である。実際、§A4.2 定理 2.2により、 $mn$ の素因数は $m$ の素因数と $n$ の素因数を合わせたものである。また、 $x\equiv r\pmod m$ ならば $x,r$ と $m$ の公約数は一致するので、 $m$ と互いに素かどうかは剰余類によって定まる。法 $n$ でも同じことが成り立つ。

したがって、 $mn$ と互いに素な剰余類は、 $m$ と互いに素な剰余類と $n$ と互いに素な剰余類の組に一対一に対応する。それぞれの個数を数えると、 $\varphi(mn)=\varphi(m)\varphi(n)$ となる。▨

注意 3.2. $m,n$ を正の整数、 $x$ を整数とする。 $x$ が $mn$ と互いに素であることと、 $x$ が $m,n$ の両方と互いに素であることの同値性には、 $m,n$ が互いに素であるという仮定は要らない。乗法性の証明では、剰余類と二つの剰余類の組との一対一対応に、その仮定を用いている。

4 素因数分解による計算公式

命題 4.1. $n\ge2$ を整数とし、相異なる素数 $p_1,\ldots,p_r$ と正の整数 $k_1,\ldots,k_r$ によって $n=p_1^{k_1}\cdots p_r^{k_r}$ と素因数分解する。このとき

\varphi(n)=\prod_{i=1}^r p_i^{k_i-1}(p_i-1) =n\prod_{p\mid n}\left(1-\frac1p\right)

が成り立つ。最後の積は、 $n$ の相異なる素因数 $p$ にわたる積である。

証明. 相異なる素数のべきは互いに素なので、命題 3.1を繰り返し用いると

\varphi(n)=\prod_{i=1}^r\varphi(p_i^{k_i})

を得る。命題 2.1によって各因子を $p_i^{k_i-1}(p_i-1)=p_i^{k_i}(1-1/p_i)$ と書くと、二つの表示が従う。▨

例 4.2. $360=2^3\cdot3^2\cdot5$ なので、命題 4.1より

\varphi(360)=360\cdot\frac12\cdot\frac23\cdot\frac45=96

である。

例 4.3. $7^{100}$ を $360$ で割った余りを求める。 $\gcd(7,360)=1$ かつ $\varphi(360)=96$ なので、§A4.7 定理 2.2より $7^{96}\equiv1\pmod{360}$ である。 $100=96+4$ より

7^{100}\equiv7^4=2401=6\cdot360+241\equiv241\pmod{360}

であり、求める余りは $241$ である。

問題 4.4. $\varphi(n)=8$ を満たす正の整数 $n$ をすべて求めよ。

解答.

$\varphi(1)=1$ なので $n>1$ である。命題 4.1より、 $n$ の素因数 $p$ に対して $p-1$ は $\varphi(n)=8$ を割り切る。 $8$ の正の約数は $1,2,4,8$ なので、 $p$ の候補は $2,3,5,9$ である。 $p$ は素数だから、 $p=2,3,5$ に限られる。

$3$ または $5$ の指数が $2$ 以上なら、同じ公式により $\varphi(n)$ がそれぞれ $3$ または $5$ の倍数となり、 $\varphi(n)=8$ に反する。したがって

n=2^a3^b5^c,\qquad a\ge0,\quad b,c\in\{0,1\}

と書くことができる。 $a=0$ または $a=1$ のときは $\varphi(2^a)=1$ なので、乗法性により $\varphi(n)=2^{b+2c}$ である。 $b+2c=3$ を満たすのは $b=c=1$ の場合だけであり、 $n=15,30$ を得る。

$a\ge2$ のときは $\varphi(n)=2^{a-1+b+2c}$ なので、 $a-1+b+2c=3$ となる。 $(b,c)=(0,0),(1,0),(0,1)$ の場合は、それぞれ $a=4,3,2$ となり、 $n=16,24,20$ を得る。 $(b,c)=(1,1)$ の場合は $a=1$ となるので、 $a\ge2$ に反する。五つの整数はいずれも公式により $\varphi(n)=8$ を満たす。よって解は

n=15,16,20,24,30

である。▨

5 約数にわたるオイラー関数の和

命題 5.1. 正の整数 $n$ に対して、

\sum_{d\mid n}\varphi(d)=n

が成り立つ。和は $n$ の正の約数 $d$ にわたる和である。

証明. $1\le k\le n$ を満たす整数 $k$ に対し、 $g=\gcd(k,n)$ とおく。 $k/n$ を約分した既約分数は $(k/g)/(n/g)$ であり、その分母 $d=n/g$ は $n$ の正の約数である。

逆に、 $n$ の正の約数 $d$ と、 $1\le u\le d$ かつ $\gcd(u,d)=1$ を満たす整数 $u$ を取る。 $k=(n/d)u$ とおくと $1\le k\le n$ であり、 $\gcd(k,n)=n/d$ なので、 $k/n$ を約分すると $u/d$ を得る。したがって、約分後の分母が $d$ である分数はちょうど $\varphi(d)$ 個である。もとの $n$ 個の分数を約分後の分母によって分けて数えると、 $\sum_{d\mid n}\varphi(d)=n$ となる。▨

例 5.2. $6$ の正の約数は $1,2,3,6$ なので、

\varphi(1)+\varphi(2)+\varphi(3)+\varphi(6)=1+1+2+2=6

となる。

6 例題

レベル1 — オイラー関数

次のオイラー関数の値を求めよ。

解法の型 $\varphi(n)=n\left(1-\dfrac1p\right)\left(1-\dfrac1q\right)$ （ $n$ の異なる素因数 $p,q$ について）

例 6.1.

\varphi(18)

答 $6$

注意 $18=2\cdot3^{2}$ なので $\varphi(18)=18\left(1-\dfrac1{2}\right)\left(1-\dfrac1{3}\right)=6$

例 6.2.

\varphi(99)

答 $60$

注意 $99=3^{2}\cdot11$ なので $\varphi(99)=99\left(1-\dfrac1{3}\right)\left(1-\dfrac1{11}\right)=60$

例 6.3.

\varphi(21)

答 $12$

注意 $21=7\cdot3$ なので $\varphi(21)=21\left(1-\dfrac1{7}\right)\left(1-\dfrac1{3}\right)=12$

例 6.4.

\varphi(55)

答 $40$

注意 $55=5\cdot11$ なので $\varphi(55)=55\left(1-\dfrac1{5}\right)\left(1-\dfrac1{11}\right)=40$

例 6.5.

\varphi(33)

答 $20$

注意 $33=11\cdot3$ なので $\varphi(33)=33\left(1-\dfrac1{11}\right)\left(1-\dfrac1{3}\right)=20$

例 6.6.

\varphi(63)

答 $36$

注意 $63=7\cdot3^{2}$ なので $\varphi(63)=63\left(1-\dfrac1{7}\right)\left(1-\dfrac1{3}\right)=36$

例 6.7.

\varphi(363)

答 $220$

注意 $363=11^{2}\cdot3$ なので $\varphi(363)=363\left(1-\dfrac1{11}\right)\left(1-\dfrac1{3}\right)=220$

例 6.8.

\varphi(20)

答 $8$

注意 $20=5\cdot2^{2}$ なので $\varphi(20)=20\left(1-\dfrac1{5}\right)\left(1-\dfrac1{2}\right)=8$

例 6.9.

\varphi(35)

答 $24$

注意 $35=5\cdot7$ なので $\varphi(35)=35\left(1-\dfrac1{5}\right)\left(1-\dfrac1{7}\right)=24$

例 6.10.

\varphi(6)

答 $2$

注意 $6=2\cdot3$ なので $\varphi(6)=6\left(1-\dfrac1{2}\right)\left(1-\dfrac1{3}\right)=2$

7 演習

レベル1 — オイラー関数

次のオイラー関数の値を求めよ。

解法の型 $\varphi(n)=n\left(1-\dfrac1p\right)\left(1-\dfrac1q\right)$ （ $n$ の異なる素因数 $p,q$ について）

問題 7.1.

\varphi(12)

解答.

答 $4$

注意 $12=3\cdot2^{2}$ なので $\varphi(12)=12\left(1-\dfrac1{3}\right)\left(1-\dfrac1{2}\right)=4$ ▨

問題 7.2.

\varphi(22)

解答.

答 $10$

注意 $22=2\cdot11$ なので $\varphi(22)=22\left(1-\dfrac1{2}\right)\left(1-\dfrac1{11}\right)=10$ ▨

問題 7.3.

\varphi(484)

解答.

答 $220$

注意 $484=11^{2}\cdot2^{2}$ なので $\varphi(484)=484\left(1-\dfrac1{11}\right)\left(1-\dfrac1{2}\right)=220$ ▨

問題 7.4.

\varphi(242)

解答.

答 $110$

注意 $242=11^{2}\cdot2$ なので $\varphi(242)=242\left(1-\dfrac1{11}\right)\left(1-\dfrac1{2}\right)=110$ ▨

問題 7.5.

\varphi(20)

解答.

答 $8$

注意 $20=5\cdot2^{2}$ なので $\varphi(20)=20\left(1-\dfrac1{5}\right)\left(1-\dfrac1{2}\right)=8$ ▨

問題 7.6.

\varphi(36)

解答.

答 $12$

注意 $36=2^{2}\cdot3^{2}$ なので $\varphi(36)=36\left(1-\dfrac1{2}\right)\left(1-\dfrac1{3}\right)=12$ ▨

問題 7.7.

\varphi(14)

解答.

答 $6$

注意 $14=2\cdot7$ なので $\varphi(14)=14\left(1-\dfrac1{2}\right)\left(1-\dfrac1{7}\right)=6$ ▨

問題 7.8.

\varphi(175)

解答.

答 $120$

注意 $175=7\cdot5^{2}$ なので $\varphi(175)=175\left(1-\dfrac1{7}\right)\left(1-\dfrac1{5}\right)=120$ ▨

問題 7.9.

\varphi(55)

解答.

答 $40$

注意 $55=5\cdot11$ なので $\varphi(55)=55\left(1-\dfrac1{5}\right)\left(1-\dfrac1{11}\right)=40$ ▨

問題 7.10.

\varphi(10)

解答.

答 $4$

注意 $10=5\cdot2$ なので $\varphi(10)=10\left(1-\dfrac1{5}\right)\left(1-\dfrac1{2}\right)=4$ ▨

問題 7.11.

\varphi(33)

解答.

答 $20$

注意 $33=3\cdot11$ なので $\varphi(33)=33\left(1-\dfrac1{3}\right)\left(1-\dfrac1{11}\right)=20$ ▨

問題 7.12.

\varphi(63)

解答.

答 $36$

注意 $63=7\cdot3^{2}$ なので $\varphi(63)=63\left(1-\dfrac1{7}\right)\left(1-\dfrac1{3}\right)=36$ ▨

問題 7.13.

\varphi(245)

解答.

答 $168$

注意 $245=7^{2}\cdot5$ なので $\varphi(245)=245\left(1-\dfrac1{7}\right)\left(1-\dfrac1{5}\right)=168$ ▨

問題 7.14.

\varphi(18)

解答.

答 $6$

注意 $18=3^{2}\cdot2$ なので $\varphi(18)=18\left(1-\dfrac1{3}\right)\left(1-\dfrac1{2}\right)=6$ ▨

問題 7.15.

\varphi(441)

解答.

答 $252$

注意 $441=3^{2}\cdot7^{2}$ なので $\varphi(441)=441\left(1-\dfrac1{3}\right)\left(1-\dfrac1{7}\right)=252$ ▨

§A4.8オイラー関数 φ とその乗法性

1 オイラー関数

2 素数べきでの値

3 互いに素な二数についての乗法性

4 素因数分解による計算公式

5 約数にわたるオイラー関数の和

6 例題

7 演習

前提記事