Eulerのφ関数（高校数学）

同義語：Eulerの関数（高校数学）オイラー関数（高校数学）Euler's totient function (high school mathematics)

概要

前提知識: 中国剰余定理（高校数学）, 素因数分解の一意性, 整数の割り算と互除法

高校での出発点：互いに素な数を数える

$1$ から $12$ までの整数のうち、$12$ と $1$ 以外の公約数をもたないもの（$12$ と互いに素なもの）はいくつあるだろうか。書き出すと $1,5,7,11$ の $4$ 個である。この個数を $\varphi(12)=4$ と書き、$n$ に対して同じ個数を与える関数 $\varphi$ を Euler の $\varphi$ 関数 という。この記事では、$\varphi(n)$ を素因数分解から計算する公式と、$\varphi$ の 2 つの基本的な性質（互いに素な数の積で掛け算になること、約数について足すと $n$ に戻ること）を証明する。

$12$ と互いに素な数を数える

$12=2^2\cdot3$ と共通の約数をもつ数は、$2$ か $3$ で割り切れる数である。$1$ から $12$ までに、$2$ の倍数は $6$ 個、$3$ の倍数は $4$ 個あり、両方の倍数（$6$ の倍数）$6,12$ は 2 回数えられている。よって $2$ か $3$ で割り切れる数は $6+4-2=8$ 個で、残りは
$$ 12-8=12-6-4+2=4 $$
個である。残るのは $1,5,7,11$ で、書き出した結果と一致する（図 1）。

1 から 12 までの数のうち、2 の倍数（青丸）と 3 の倍数（緑の四角）に印を付けた図。どちらの印もない 1, 5, 7, 11（赤）が 12 と互いに素な数

素数と素数の累乗

$7$ は素数なので、$1$ から $6$ まではどれも $7$ と互いに素で、$7$ だけが互いに素でない。$\varphi(7)=6$ である。
$9=3^2$ と共通の約数をもつのは $3$ の倍数 $3,6,9$ だけなので、$\varphi(9)=9-3=6$ である。$9-1=8$ ではない。

積に分けると掛け算になるか

$\varphi(3)=2$（$1,2$）、$\varphi(5)=4$（$1,2,3,4$）で、$15$ と互いに素な数は $1,2,4,7,8,11,13,14$ の $8$ 個なので $\varphi(15)=8=\varphi(3)\varphi(5)$ である。$12=3\cdot4$ でも $\varphi(3)\varphi(4)=2\cdot2=4=\varphi(12)$ である。ところが $12=2\cdot6$ と分けると $\varphi(2)\varphi(6)=1\cdot2=2$ で、$\varphi(12)=4$ にならない。$3$ と $4$ は互いに素だが、$2$ と $6$ は公約数 $2$ をもつ。

この記事で答える問いは次の 4 つである。

ex-phihs-start-product で、互いに素な数に分けると掛け算になるのはなぜか。→ thm-phihs-multiplicative
$\varphi(n)$ を素因数分解から一度に求める公式は何か。→ thm-phihs-formula
ex-phihs-start-12 の「引いて足し戻す」計算は、公式とどうつながるか。→ ex-phihs-inclusion-exclusion

$\varphi$ を $n$ の約数すべてについて足すと何になるか。→ thm-phihs-divisor-sum

高校の計算	この記事の言葉	大学の言葉
$1$〜$n$ で $n$ と互いに素な数を数える	Euler の $\varphi$ 関数（def-phihs-phi）	単数群 $(\mathbb{Z}/n\mathbb{Z})^\times$ の元の個数
余りの表で互いに素な行と列の交わりを数える	乗法性（thm-phihs-multiplicative）	中国剰余定理による単数群の分解
倍数を引いて足し戻す	包除原理と積の公式（thm-phihs-formula）	Möbius 関数による表示
$\frac k{12}$ を約分して分母で分ける	約数についての和（thm-phihs-divisor-sum）	$\varphi*\mathbf 1=\mathrm{id}$（Dirichlet 積）

$\varphi(n)$ の定義と、Euler の定理 $a^{\varphi(n)}\equiv1\pmod n$（$\gcd(a,n)=1$）は冪の余りの周期と元の位数でも扱っている。この記事は $\varphi(n)$ そのものの計算と性質を主題とする。大学向けの用語解説は Eulerのφ関数である。

定義と小さな値

Euler の $\varphi$ 関数

正の整数 $n$ に対し、$1$ 以上 $n$ 以下の整数 $k$ のうち $\gcd(k,n)=1$ となるものの個数を $\varphi(n)$ と書く。$\varphi$ を Euler の $\varphi$ 関数（Euler 関数）という。$\gcd(k,n)=1$ のとき $k$ と $n$ は 互いに素 であるという。

$n=1$ では、$k=1$ が $\gcd(1,1)=1$ をみたすので $\varphi(1)=1$ である。$n\ge2$ では $k=n$ は $\gcd(n,n)=n\ne1$ なので数えられず、$1$ 以上 $n-1$ 以下の数だけを数えればよい。

$\varphi(n)$ の表（$n\le16$）

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$
$\varphi(n)$	$1$	$1$	$2$	$2$	$4$	$2$	$6$	$4$	$6$	$4$	$10$	$4$	$12$	$6$	$8$	$8$

たとえば $\varphi(10)=4$ は $1,3,7,9$、$\varphi(16)=8$ は $1$ から $15$ までの奇数 $8$ 個である。

n = 1 から 40 までの φ(n) の棒グラフ。赤は n が素数で φ(n) = n−1 となり破線 y = n−1 に届く。青は素数でない n で、n が 2 以上なら破線より下にある（n = 1 だけは φ(1) = 1 で破線より上）
図 2 のように、$\varphi(n)$ は $n$ とともに単調に増えるのではなく、上下に激しく動く。$n\ge2$ で破線 $y=n-1$ に届くのは $n$ が素数のときだけである（$n\ge2$ が素数でなければ、$1< k< n$ の約数 $k$ があって $\gcd(k,n)=k\ne1$ なので $\varphi(n)\le n-2$）。$n=1$ だけは $\varphi(1)=1$ で、破線（$y=0$）より上に出る。

素数の累乗

素数の累乗での値

$p$ を素数、$k$ を正の整数とすると
$$ \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)=p^k\Bigl(1-\frac1p\Bigr) $$
である。特に $\varphi(p)=p-1$ である。

$p$ の倍数を数えて引く

方針：$p^k$ と互いに素でない数は、$p$ の倍数に限ることを示し、$p$ の倍数を数えて引く。
段 1（互いに素でない数は $p$ の倍数）。$p^k$ の正の約数は $1,p,p^2,\dots,p^k$ だけである（素因数分解の一意性）。$\gcd(j,p^k)$ は $p^k$ の約数なので、$1$ でなければ $p,p^2,\dots$ のどれかであり、どれも $p$ の倍数だから $j$ は $p$ の倍数である。逆に $j$ が $p$ の倍数なら $p$ は $j$ と $p^k$ の公約数なので、$\gcd(j,p^k)\ne1$ である。
段 2（数える）。$1$ から $p^k$ までの $p$ の倍数は $p,2p,\dots,p^{k-1}\cdot p$ の $p^{k-1}$ 個である。よって $\varphi(p^k)=p^k-p^{k-1}$ で、$p^{k-1}$ でくくると残りの形になる。$\square$

素数の累乗の値

$\varphi(8)=8-4=4$（$1,3,5,7$）、$\varphi(27)=27-9=18$、$\varphi(125)=125-25=100$、$\varphi(2027)=2026$（$2027$ は素数）である。

主定理 1：互いに素な数の積では掛け算になる

準備：互いに素かどうかは余りで決まる

互いに素であることの言いかえ

$m,n$ を正の整数、$x$ を整数とする。

$x$ を $m$ で割った余りを $r$ とすると、$\gcd(x,m)=\gcd(r,m)$ である。
$\gcd(x,mn)=1$ であることと、「$\gcd(x,m)=1$ かつ $\gcd(x,n)=1$」であることは同値である。

公約数と素因数で調べる

要点：余りで割っても公約数は変わらず、$mn$ の素因数は $m$ か $n$ を割る。

詳しい証明を開く

段 1（1 の証明）。$x=mq+r$ とする。$x$ と $m$ の公約数は $r=x-mq$ も割り、$r$ と $m$ の公約数は $x=mq+r$ も割る。よって $x,m$ の公約数と $r,m$ の公約数は同じで、最大公約数も等しい（整数の割り算と互除法の補題「割り算で公約数は変わらない」と同じ理由）。

段 2（2 の「$\Rightarrow$」）。$\gcd(x,mn)=1$ とする。$x$ と $m$ の公約数は $x$ と $mn$ の公約数でもあるので $1$ を割り、$\gcd(x,m)=1$ である。$n$ についても同じである。

段 3（2 の「$\Leftarrow$」）。$\gcd(x,m)=\gcd(x,n)=1$ とし、$\gcd(x,mn)\ne1$ と仮定する。$\gcd(x,mn)$ の素因数 $p$ を 1 つとると、$p$ は $x$ と $mn$ を割る。素数 $p$ が積 $mn$ を割るので $p$ は $m$ か $n$ を割る（Euclid の補題、整数の割り算と互除法）。$p$ が $m$ を割るなら $p$ は $x$ と $m$ の公約数で、$\gcd(x,m)=1$ に反する。$n$ でも同じである。よって $\gcd(x,mn)=1$ である。$\square$

余りで判定する

$\gcd(47,12)$：$47=12\cdot3+11$ なので $\gcd(47,12)=\gcd(11,12)=1$ である。
$x=35$、$m=3$、$n=4$：$\gcd(35,3)=1$、$\gcd(35,4)=1$ なので、$\gcd(35,12)=1$ である。$x=10$ なら $\gcd(10,4)=2$ なので、$\gcd(10,12)\ne1$ である（実際 $2$）。

主定理 1 と証明

$\varphi$ の乗法性

$m,n$ が互いに素な正の整数なら
$$ \varphi(mn)=\varphi(m)\,\varphi(n) $$
である。

余りの表で、互いに素な行と列の交わりを数える

方針：$0$ から $mn-1$ までの数を、中国剰余定理（高校数学）のように「$m$ で割った余り」と「$n$ で割った余り」の組で表に並べる。$mn$ と互いに素な数は、$m$ と互いに素な行と $n$ と互いに素な列の交わりにちょうど入ることを示す（図 3）。
段 1（$m=1$ または $n=1$）。$m=1$ なら $mn=n$ で、$\varphi(1)=1$ なので等式は成り立つ。$n=1$ でも同じである。以下 $m,n\ge2$ とする。
段 2（数える範囲を $0$ から $mn-1$ にする）。$\varphi(mn)$ は $1$ から $mn$ までの数を数えるが、$mn$ と $0$ はどちらも $\gcd(\cdot,mn)=mn\ne1$ なので数えられない。よって $\varphi(mn)$ は、$0$ から $mn-1$ までで $mn$ と互いに素な数の個数に等しい。同じく $\varphi(m)$ は $0$ から $m-1$ まで、$\varphi(n)$ は $0$ から $n-1$ までで数えてよい。
段 3（組との対応）。$0\le x\le mn-1$ の $x$ に、$m$ で割った余り $a$ と $n$ で割った余り $b$ の組 $(a,b)$ を対応させる。$m,n$ は互いに素なので、中国剰余定理（中国剰余定理（高校数学）の主定理）により、この対応で $0$ から $mn-1$ までの数と、組 $(a,b)$（$0\le a\le m-1$、$0\le b\le n-1$）とは 1 対 1 に対応する。
段 4（互いに素な数の行き先）。lem-phihs-coprime の 2 により、$\gcd(x,mn)=1$ は「$\gcd(x,m)=1$ かつ $\gcd(x,n)=1$」と同値である。1 により、$\gcd(x,m)=\gcd(a,m)$、$\gcd(x,n)=\gcd(b,n)$ である。よって
$$ \gcd(x,mn)=1\iff\gcd(a,m)=1\ \text{かつ}\ \gcd(b,n)=1 $$
である。
段 5（数える）。段 3・4 により、$0$ から $mn-1$ までで $mn$ と互いに素な数は、「$\gcd(a,m)=1$ をみたす $a$」と「$\gcd(b,n)=1$ をみたす $b$」の組と 1 対 1 に対応する。$a$ は $\varphi(m)$ 通り、$b$ は $\varphi(n)$ 通り（段 2）なので、組は $\varphi(m)\varphi(n)$ 個ある。よって $\varphi(mn)=\varphi(m)\varphi(n)$ である。$\square$

0 から 11 までを、3 で割った余り（行）と 4 で割った余り（列）で決まるマスに置いた表。3 と互いに素な行 1, 2 と、4 と互いに素な列 1, 3 の交わりの 4 マス（赤）に、12 と互いに素な 1, 5, 7, 11 が入る
同じ考え方の証明は Cri24 Fact 9.5.2 にもあり、そこでは $1$ から $mn$ までを $m$ 列の表に並べて、$m$ と互いに素な列の中で $n$ と互いに素な数を数えている。図 3 は $m=3$、$n=4$ の場合である。赤いマスは $2\times2=4$ 個で、$\varphi(12)=\varphi(3)\varphi(4)=4$ となる。薄い色のマスは、行か列の一方だけが互いに素なマスで、たとえば $4$ は $3$ と互いに素だが $4$ と互いに素でないので、$12$ と互いに素にならない。

乗法性で計算する

$\varphi(15)=\varphi(3)\varphi(5)=2\cdot4=8$（ex-phihs-start-product）。
$\varphi(36)=\varphi(4)\varphi(9)=2\cdot6=12$。$4$ と $9$ は互いに素である。
$\varphi(100)=\varphi(4)\varphi(25)=2\cdot20=40$。$1$ から $100$ までで、$2$ でも $5$ でも割り切れない数が $40$ 個ある。

素因数分解による公式

$\varphi(n)$ の公式

$n\ge2$ を $n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$（$p_1,\dots,p_r$ は相異なる素数、$e_i\ge1$）と素因数分解すると
$$ \varphi(n)=\prod_{i=1}^r p_i^{e_i-1}(p_i-1)=n\Bigl(1-\frac1{p_1}\Bigr)\Bigl(1-\frac1{p_2}\Bigr)\cdots\Bigl(1-\frac1{p_r}\Bigr) $$
である。右辺の積は $n$ を割る素数だけにわたり、指数 $e_i$ にはよらない形になっている。

素数の累乗に分けて掛ける

方針：異なる素数の累乗どうしは互いに素なので、thm-phihs-multiplicative を繰り返して素数の累乗の場合（prop-phihs-prime-power）に帰着する。
段 1（分ける）。$r=1$ なら prop-phihs-prime-power そのものである。$r\ge2$ のとき、$p_1^{e_1}\cdots p_{r-1}^{e_{r-1}}$ と $p_r^{e_r}$ は共通の素因数をもたないので互いに素である（公約数が $1$ でなければ、その素因数が両方を割るが、素因数分解の一意性により $p_r$ は左の数を割らない）。thm-phihs-multiplicative により
$$ \varphi(n)=\varphi(p_1^{e_1}\cdots p_{r-1}^{e_{r-1}})\,\varphi(p_r^{e_r}) $$
である。これを $r-1$ 回繰り返すと $\varphi(n)=\varphi(p_1^{e_1})\cdots\varphi(p_r^{e_r})$ となる。
段 2（素数の累乗の値を入れる）。prop-phihs-prime-power により $\varphi(p_i^{e_i})=p_i^{e_i-1}(p_i-1)=p_i^{e_i}\Bigl(1-\dfrac1{p_i}\Bigr)$ である。掛け合わせると、$p_1^{e_1}\cdots p_r^{e_r}=n$ なので右辺の形になる。$\square$

公式で求める

$\varphi(12)=12\Bigl(1-\dfrac12\Bigr)\Bigl(1-\dfrac13\Bigr)=12\cdot\dfrac12\cdot\dfrac23=4$。
$360=2^3\cdot3^2\cdot5$ なので $\varphi(360)=360\cdot\dfrac12\cdot\dfrac23\cdot\dfrac45=96$。素数の累乗ごとに計算しても $\varphi(8)\varphi(9)\varphi(5)=4\cdot6\cdot4=96$ である。
$2026=2\cdot1013$（$1013$ は素数）なので $\varphi(2026)=1\cdot1012=1012$。
$1000=2^3\cdot5^3$ なので $\varphi(1000)=1000\cdot\dfrac12\cdot\dfrac45=400$。$\varphi(10)=10\cdot\dfrac12\cdot\dfrac45=4$ と比べると、$\dfrac{\varphi(n)}n$ は同じ $\dfrac25$ である。$\dfrac{\varphi(n)}n$ は $n$ を割る素数の種類だけで決まる。

包除原理で見る

ex-phihs-start-12 の「引いて足し戻す」計算は、thm-phihs-formula の積を展開したものになっている。

包除原理による計算

$n$ を割る素数が $p,q$ の 2 つのとき、$1$ から $n$ までで $p$ の倍数は $\dfrac np$ 個、$q$ の倍数は $\dfrac nq$ 個、両方の倍数（$pq$ の倍数）は $\dfrac n{pq}$ 個ある。$n$ と互いに素な数は、$p$ の倍数でも $q$ の倍数でもない数なので、包除原理（集合の要素の個数と包除原理）により
$$ \varphi(n)=\underbrace{n}_{\text{全体}}-\underbrace{\frac np}_{p\text{ の倍数}}-\underbrace{\frac nq}_{q\text{ の倍数}}+\underbrace{\frac n{pq}}_{\text{両方の倍数}}=n\Bigl(1-\frac1p\Bigr)\Bigl(1-\frac1q\Bigr) $$
である。最後の等号は右辺を展開すれば確かめられる。$n=12$、$p=2$、$q=3$ では $12-6-4+2=4$ である。
素数が 3 つなら、3 つの倍数を引き、2 つずつの公倍数を足し、3 つの公倍数を引く。$360$ では
$$ 360-\frac{360}2-\frac{360}3-\frac{360}5+\frac{360}6+\frac{360}{10}+\frac{360}{15}-\frac{360}{30}=360-180-120-72+60+36+24-12=96 $$
で、ex-phihs-formula の (2) と一致する。一般の $r$ 個の素数でも、$n\bigl(1-\frac1{p_1}\bigr)\cdots\bigl(1-\frac1{p_r}\bigr)$ を展開した $2^r$ 個の項が、包除原理の各項にちょうど対応する。

主定理 2：約数についての和

$12$ の約数は $1,2,3,4,6,12$ で、$\varphi$ の値は $1,1,2,2,2,4$、その和は $12$ である。これは偶然ではない。

約数についての和

正の整数 $n$ について
$$ \sum_{d\mid n}\varphi(d)=n $$
である。ここで $\sum_{d\mid n}$ は、$n$ の正の約数 $d$ すべてにわたる和を表す。

分数 $\frac kn$ を約分して分母で分ける

方針：$n$ 個の分数 $\dfrac1n,\dfrac2n,\dots,\dfrac nn$ を約分し、約分したあとの分母 $d$ ごとに分ける。分母が $d$ のものがちょうど $\varphi(d)$ 個あることを示せば、全部で $n$ 個なので和が $n$ になる。
段 1（約分した形）。$1\le k\le n$ の分数 $\dfrac kn$ を約分して $\dfrac ad$（$a,d$ は正の整数で $\gcd(a,d)=1$）にする。$d$ は $n$ を $\gcd(k,n)$ で割った数なので $n$ の約数であり、$\dfrac ad=\dfrac kn\le1$ なので $1\le a\le d$ である。
段 2（どの形もちょうど 1 回現れる）。逆に、$n$ の約数 $d$ と、$1\le a\le d$、$\gcd(a,d)=1$ をみたす $a$ をとる。$k:=a\cdot\dfrac nd$ とおくと、$k$ は $1$ 以上 $n$ 以下の整数で $\dfrac kn=\dfrac ad$ である。$\dfrac ad$ は約分しきった形なので、$\dfrac kn$ を約分すると $\dfrac ad$ になる（約分しきった形は 1 通りに決まる）。また $\dfrac kn=\dfrac{k'}n$ なら $k=k'$ なので、同じ $\dfrac ad$ になる $k$ は 1 つだけである。
段 3（数える）。段 1・2 により、$\dfrac1n,\dots,\dfrac nn$ の $n$ 個の分数は、組 $(d,a)$（$d\mid n$、$1\le a\le d$、$\gcd(a,d)=1$）と 1 対 1 に対応する。$d$ を決めると $a$ は $\varphi(d)$ 通りなので、組の個数は $\sum_{d\mid n}\varphi(d)$ である。これが $n$ に等しい。$\square$

1/12 から 12/12 までの 12 個の分数を約分し、約分したあとの分母 1, 2, 3, 4, 6, 12 ごとに並べた表。分母 d の列にはちょうど φ(d) 個の分数が入り、合計は 12
Cri24 Fact 9.5.4 は、$0$ から $n-1$ までの $n$ 個の数を $n$ との最大公約数で分けるという、この証明と同じ数え方で示している。段 2 の「約分しきった形は 1 通りに決まる」は、$\dfrac ad=\dfrac{a'}{d'}$（どちらも約分しきった形、分母は正）なら $ad'=a'd$ で、$d$ が $a'd$ を割り $\gcd(a,d)=1$ から $d$ が $d'$ を割る（互いに素な数による割り算）、同じく $d'$ が $d$ を割るので $d=d'$、$a=a'$ となることによる。

$n=12$ と $n=36$

$n=12$ では、図 4 のとおり、分母 $1,2,3,4,6,12$ の列にそれぞれ $1,1,2,2,2,4$ 個の分数が入り、$1+1+2+2+2+4=12$ である。たとえば $\dfrac9{12}=\dfrac34$ は分母 $4$ の列に入り、分母 $4$ の列の分子 $1,3$ は $4$ と互いに素な数である。
$n=36$ の約数は $1,2,3,4,6,9,12,18,36$ で、$\varphi$ の値は $1,1,2,2,2,6,4,6,12$、和は $36$ である。

そのほかの性質と使い方

$n\ge3$ なら $\varphi(n)$ は偶数

$n\ge3$ なら $\varphi(n)$ は偶数である。

$k$ と $n-k$ を組にする

方針：$n$ と互いに素な数 $k$ を、$n-k$ と組にする。
段 1。$1\le k\le n-1$ で $\gcd(k,n)=1$ なら、$\gcd(n-k,n)=\gcd(k,n)=1$ である（$n-k$ と $n$ の公約数は $k=n-(n-k)$ を割り、逆も同じ）。よって $n$ と互いに素な数は、$k$ と $n-k$ の組に分けられる。
段 2。組が 1 つの数だけからなるのは $k=n-k$、つまり $n=2k$ のときである。このとき $\gcd(k,n)=\gcd(k,2k)=k$ で、これが $1$ になるのは $k=1$、$n=2$ のときだけである。$n\ge3$ ではこれは起こらないので、どの組も 2 つの数からなり、$\varphi(n)$ は偶数である。$\square$

組の例

$n=12$ では $1\leftrightarrow11$、$5\leftrightarrow7$ の 2 組で $\varphi(12)=4$。$n=9$ では $1\leftrightarrow8$、$2\leftrightarrow7$、$4\leftrightarrow5$ の 3 組で $\varphi(9)=6$。$n=2$ では $1$ が自分自身と組になり、$\varphi(2)=1$ は奇数である。

$\varphi(n)$ のいちばん大切な使い道は、累乗の余りの計算である。$\gcd(a,n)=1$ なら $a^{\varphi(n)}\equiv1\pmod n$ が成り立つ（Euler の定理。証明は冪の余りの周期と元の位数の系「Euler の定理の主張」）。

Euler の定理で余りを求める

$3^{2026}$ を $20$ で割った余りを求める。$20=2^2\cdot5$ なので $\varphi(20)=20\cdot\dfrac12\cdot\dfrac45=8$ で、$\gcd(3,20)=1$ なので $3^8\equiv1\pmod{20}$ である。$2026=8\cdot253+2$ なので
$$ 3^{2026}=(3^8)^{253}\cdot3^2\equiv1\cdot9=9\pmod{20} $$
である。実際は $3^4=81\equiv1\pmod{20}$ で、$1$ に戻る最小の指数（位数）$4$ は $\varphi(20)=8$ を割っている。

約数の個数・約数の総和との比較

$\varphi$ と同じく、約数の個数 $d(n)$ と約数の総和 $\sigma(n)$ も、互いに素な数の積で掛け算になる（約数の個数と約数の総和）。3 つを並べる。

	$\varphi(n)$	$d(n)$	$\sigma(n)$
定義	$1$〜$n$ で $n$ と互いに素な数の個数	正の約数の個数	正の約数の和
$p^k$ での値	$p^k-p^{k-1}$	$k+1$	$1+p+\dots+p^k$
$n=12$	$4$	$6$	$28$
互いに素なら掛け算	○（thm-phihs-multiplicative）	○	○
約数について足すと	$\sum_{d\mid n}\varphi(d)=n$	—	—
乗法性の証明の道具	中国剰余定理	約数と指数の組の対応	約数と指数の組の対応

例と反例

外す条件	反例	成り立たなくなること
$m,n$ が互いに素	$\varphi(4)=2$、$\varphi(2)^2=1$（ex-phihs-counter-coprime）	$\varphi(mn)=\varphi(m)\varphi(n)$
素数（指数が $1$）	$\varphi(9)=6$、$9-1=8$（ex-phihs-counter-power）	$\varphi(n)=n-1$
$n\ge3$	$\varphi(2)=1$（ex-phihs-even）	$\varphi(n)$ は偶数

反例：互いに素でない積

$\varphi(4)=2$（$1,3$）だが $\varphi(2)\varphi(2)=1\cdot1=1$ である。$\varphi(24)=8$ だが $\varphi(6)\varphi(4)=2\cdot2=4$ である。prf-phihs-multiplicative の段 3 で中国剰余定理を使うところで、$m,n$ が互いに素であることが要る。$m=n=2$ では、$0,1,2,3$ の余りの組は $(0,0),(1,1),(0,0),(1,1)$ で、1 対 1 に対応しない。
互いに素でないときの正しい関係は、$g=\gcd(m,n)$ として
$$ \varphi(mn)=\varphi(m)\,\varphi(n)\cdot\frac g{\varphi(g)} $$
である。thm-phihs-formula で $\dfrac{\varphi(mn)}{mn}$ は $mn$ を割る素数 $p$ についての $1-\dfrac1p$ の積であり、$\dfrac{\varphi(m)}m\cdot\dfrac{\varphi(n)}n$ では $m$ と $n$ の両方を割る素数（$g$ を割る素数）の分だけ $1-\dfrac1p$ が 2 回掛かっている。その余分が $\dfrac{\varphi(g)}g$ なので、割って戻すとこの式になる。$m=6$、$n=4$ では $g=2$ で、$2\cdot2\cdot\dfrac21=8=\varphi(24)$ である。

反例：$\varphi(p^k)$ を $p^k-1$ とする誤り

$\varphi(p)=p-1$ から類推して $\varphi(p^k)=p^k-1$ とするのは、$k\ge2$ では誤りである。$\varphi(9)=6$ だが $9-1=8$、$\varphi(8)=4$ だが $8-1=7$ である。$1$ から $p^k-1$ までには、$p^k$ と公約数 $p$ をもつ $p$ の倍数が $p^{k-1}-1$ 個あり（$9$ なら $3,6$ の $2$ 個）、それを引く必要がある（prf-phihs-prime-power の段 2）。$\varphi(n)=n-1$ となるのは $n$ が素数のときに限る（図 2 の赤い棒）。

大学数学で見る：単数群と Möbius 関数

単数群の位数としての $\varphi(n)$

$n\ge2$ のとき、法 $n$ で逆元をもつ余り（$\gcd(k,n)=1$ となる $k$）の全体は、掛け算について閉じていて群になる。これを $(\mathbb{Z}/n\mathbb{Z})^\times$ と書き、法 $n$ の 単数群 という（合同式の割り算と逆元の注意「単元と体」）。$\varphi(n)$ はこの群の元の個数（位数）であり、Euler の定理は「有限群の元の位数は群の位数を割る」という Lagrange の定理の特別な場合である。thm-phihs-multiplicative の証明は、中国剰余定理の対応が単数群どうしの 1 対 1 の対応
$$ (\mathbb{Z}/mn\mathbb{Z})^\times\cong(\mathbb{Z}/m\mathbb{Z})^\times\times(\mathbb{Z}/n\mathbb{Z})^\times $$
を与えることを使っていた（Ste17 Lemma 2.2.5・Proposition 2.2.7、Cla25 Theorem 8.4・Corollary 8.5）。

Möbius 関数による表示と、約数についての和との関係を開く

$\mu(1)=1$、$n$ が相異なる $r$ 個の素数の積なら $\mu(n)=(-1)^r$、同じ素数で 2 回以上割り切れるなら $\mu(n)=0$ と定めた関数を Möbius 関数という（Möbius関数）。ex-phihs-inclusion-exclusion の包除原理の式は

$$\varphi(n)=\sum_{d\mid n}\mu(d)\,\frac nd$$

とまとめて書ける。$n=12$ では約数 $1,2,3,4,6,12$ の $\mu$ が $1,-1,-1,0,1,0$ なので、$12-6-4+2=4$ である。一方 thm-phihs-divisor-sum は「$\varphi$ を約数について足すと $n$ に戻る」ことを言っている。「約数について足す」操作の逆が「$\mu$ を掛けて約数について足す」操作であるというのが Möbius の反転公式で（Möbiusの反転公式）、上の 2 つの式はちょうどこの反転で互いに移り合う（本記事では証明しない）。Cla25 Chapter 8 §4.1 は、この反転を使って中国剰余定理によらずに乗法性を示している。

さらに先へ

$\varphi(n)$ は、2 つの大きな素数 $p,q$ の積 $n=pq$ について $\varphi(n)=(p-1)(q-1)$ となる。$n$ だけを公開し、$p,q$ を知らないと $\varphi(n)$ が計算しにくいことを利用するのが RSA 暗号である。高校数学の言葉での解説は RSA暗号（高校数学）、大学向けは RSA暗号で扱う。
$\varphi(n)$ は $n$ 以下の分母をもつ既約分数の個数とも関係する。$0<\dfrac ab\le1$、$b\le N$ の既約分数の個数は $\varphi(1)+\varphi(2)+\dots+\varphi(N)$ である（prf-phihs-divisor-sum と同じ数え方）。$N=6$ では $1+1+2+2+4+2=12$ 個である。
どんな偶数も $\varphi(n)$ の値になるわけではない。たとえば $\varphi(n)=14$ となる $n$ はない（Eulerのφ関数の反例「値にならない偶数」）。
$1$ の原始 $n$ 乗根（$n$ 乗して初めて $1$ になる複素数）の個数も $\varphi(n)$ である。これは 1の冪根で数を振り分けるの話題につながる。