Eulerのφ関数
概要
Eulerのφ関数（Euler's totient function）とは、正の整数 $n$ に対し、$1$ 以上 $n$ 以下で $n$ と互いに素な整数の個数 $\varphi(n)$ を与える関数である。$12$ と互いに素なのは $1,5,7,11$ なので $\varphi(12)=4$、素数 $p$ では $\varphi(p)=p-1$ である。$\varphi(n)$ は法 $n$ で逆元をもつ剰余類の個数であり、Euler の定理 $a^{\varphi(n)}\equiv1\pmod n$ の指数になる。互いに素な $m,n$ について $\varphi(mn)=\varphi(m)\varphi(n)$ が成り立ち（$\varphi(4)\neq\varphi(2)^2$）、$\varphi(n)=n\prod_{p\mid n}(1-1/p)$ が従う。
前提知識: 整数, 最大公約数, 互いに素, 素因数分解, 合同式
$1$ から $12$ までの整数のうち、$12$ と共通の約数を $1$ 以外にもたないものを数えてみる。$2,3,4,6,8,9,10,12$ は $2$ か $3$ で割り切れて $12$ と共通の約数をもつので、残るのは $1,5,7,11$ の $4$ 個である。この個数を $\varphi(12)=4$ と書く。これは次のようにも求められる。$12=2^2\cdot3$ なので、$12$ と共通の約数をもつことは $2$ か $3$ で割り切れることと同じであり、$2$ で割り切れない数は全体の $1/2$、そのうち $3$ で割り切れない数はさらに $2/3$ なので、
$$
\varphi(12)=12\cdot\Bigl(1-\frac12\Bigr)\Bigl(1-\frac13\Bigr)=12\cdot\frac12\cdot\frac23=4
$$
となる。この計算がいつも正しいことは thm-euler-phi-function-product で証明する。
このように、正の整数 $n$ に対して「$1$ 以上 $n$ 以下で $n$ と互いに素な整数の個数」を与える関数 $\varphi$ を Euler の $\varphi$ 関数という。分数で言えば、$\frac1{12},\frac2{12},\dots,\frac{12}{12}$ のうち約分できないもの（$\frac1{12},\frac5{12},\frac7{12},\frac{11}{12}$）の個数である。$\varphi(n)$ は、法 $n$ で割り算のできる余り（逆数をもつ余り）の個数でもあり（prop-euler-phi-function-units）、そのため Eulerの定理(整数論) $a^{\varphi(n)}\equiv1\pmod n$ の指数として現れる。
定義
正の整数 $n$ に対し、
$$
\varphi(n):=\#\{k\in\mathbb{Z}\mid 1\le k\le n,\ \gcd(k,n)=1\}
$$
と定める。ここで $\#A$ は有限集合 $A$ の元の個数である。関数 $\varphi$ を Eulerのφ関数（Euler's totient function、Euler 関数、Euler の totient 関数）という。
$n=1$ では $k=1$ が $\gcd(1,1)=1$ を満たすので $\varphi(1)=1$ である。$n\ge2$ では $\gcd(n,n)=n\neq1$ なので、$\varphi(n)$ は $1,2,\dots,n-1$ のうち $n$ と互いに素なものの個数に等しい。「$n$ 未満」で数える定義では $\varphi(1)=0$ となってしまい、後の公式（thm-euler-phi-function-divisor-sum など）が $n=1$ で成り立たなくなる。Gauss は最初「$n$ より小さい」数で定義し、約数和の公式を述べる直前に「$n$ を超えない」数に改めて $\varphi(1)=1$ とした（Gau01 Art. 38–39）。
$\gcd(k,n)$ は $k$ を $n$ の倍数だけずらしても変わらない（$k$ と $n$ の公約数と $k+tn$ と $n$ の公約数は同じである）ので、$n$ と互いに素であるかどうかは $k$ の法 $n$ の剰余類だけで決まる。そこで次の言葉を使う。
$n$ を正の整数とする。$\varphi(n)$ 個の整数 $r_1,\dots,r_{\varphi(n)}$ が、どれも $n$ と互いに素で、どの 2 つも $n$ を法として合同でない（合同式）とき、これを法 $n$ の既約剰余系（reduced residue system）という。
$1\le k\le n$ で $\gcd(k,n)=1$ となる $k$ 全体は既約剰余系である。どの 2 つも合同でない $n$ 個の整数（完全剰余系）の中には、$n$ と互いに素なものがちょうど $\varphi(n)$ 個ある。各整数は $1,\dots,n$ のちょうど 1 つと合同であり、互いに素かどうかは合同な数の間で変わらないからである。
$\gcd(a,n)=1$ なら、Bézoutの等式により $ax+ny=1$ となる整数 $x,y$ があり、$ax\equiv1\pmod n$ である。逆に $ax=1+nk$ なら、$a$ と $n$ の公約数は $ax-nk=1$ を割り切るので $\gcd(a,n)=1$ である。よって $\bar a\in\mathbb{Z}/n\mathbb{Z}$ が単元であることは $\gcd(a,n)=1$ と同値であり、単元の個数は $\bar1,\dots,\bar n$ のうち $\gcd(k,n)=1$ となるものの個数 $\varphi(n)$ に等しい。$\square$
直感
$\varphi(n)$ は「$n$ の素因数を 1 つも含まない数の割合」を $n$ 倍したものと考えられる。$n$ の相異なる素因数を $p_1,\dots,p_r$ とすると、$p_1$ で割り切れない数の割合は $1-1/p_1$ であり、素因数ごとの「割り切れない」という条件は互いに干渉しないので、割合は掛け合わせて $\prod_i(1-1/p_i)$ となる。この「干渉しない」ことを正確に述べたものが乗法性（thm-euler-phi-function-multiplicative）である。
したがって $\varphi(n)/n$ は $n$ の大きさではなく、$n$ がどんな素因数をもつかで決まる。素数 $p$ では $\varphi(p)/p=1-1/p$ は $1$ に近く、$2\cdot3\cdot5\cdot7=210$ のように小さい素因数を多くもつ数では $\varphi(210)/210=\frac12\cdot\frac23\cdot\frac45\cdot\frac67=\frac{48}{210}$ と小さくなる。そのため $\varphi(n)$ は $n$ について単調でなく、上下に大きく揺れる。
例と反例
$n=1,\dots,12$ について定義どおりに数えると次のとおりである。
$$
\begin{array}{c|cccccccccccc}
n&1&2&3&4&5&6&7&8&9&10&11&12\\\hline
\varphi(n)&1&1&2&2&4&2&6&4&6&4&10&4
\end{array}
$$
たとえば $n=10$ では $1,3,7,9$、$n=9$ では $1,2,4,5,7,8$ が $n$ と互いに素である。$\varphi(3)=\varphi(4)=\varphi(6)=2$ のように、異なる $n$ で値が一致することがある。
素数 $p$ では $1,2,\dots,p-1$ はすべて $p$ と互いに素なので $\varphi(p)=p-1$ である。逆に $n\ge2$ で $\varphi(n)=n-1$ なら、$1,\dots,n-1$ がすべて $n$ と互いに素なので、$n$ は $1$ と $n$ 以外に約数をもたず素数である。
素数冪 $p^e$（$e\ge1$）では、$1\le k\le p^e$ が $p^e$ と互いに素でないことは $p\mid k$ と同値である（$p^e$ の $1$ より大きい約数はすべて $p$ で割り切れる）。$p$ の倍数は $p,2p,\dots,p^{e-1}\cdot p$ の $p^{e-1}$ 個なので
$$
\varphi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)
$$
である。たとえば $\varphi(8)=4$、$\varphi(9)=6$、$\varphi(1024)=512$ である。
$\varphi(4)=2$ であるが $\varphi(2)\varphi(2)=1$ である。同様に $\varphi(12)=4$ だが $\varphi(2)\varphi(6)=2$ である。この例は乗法性（thm-euler-phi-function-multiplicative）の仮定「$m$ と $n$ が互いに素」を破り、「すべての $m,n$ について $\varphi(mn)=\varphi(m)\varphi(n)$」という含意を破る。すなわち $\varphi$ は乗法的関数であるが、完全乗法的（互いに素でない場合も積を保つ）ではない。
$\varphi(n)=14$ となる $n$ は存在しない。$n$ の素因数分解を $n=\prod_i p_i^{e_i}$ とすると、thm-euler-phi-function-product により $\varphi(n)=\prod_i p_i^{e_i-1}(p_i-1)$ である。$\varphi(n)=14=2\cdot7$ とすると、素数 $7$ は因子 $p_i^{e_i-1}(p_i-1)$ のどれかを割り切り（Euclidの補題）、しかもその因子は $14$ の約数である。$7\mid p_i^{e_i-1}$ なら $p_i=7$、$e_i\ge2$ で、同じ因子の $p_i-1=6$ が $14$ を割り切ることになり不合理である。$7\mid p_i-1$ なら、$p_i-1$ は $14$ の約数なので $p_i-1\in\{7,14\}$、$p_i\in\{8,15\}$ となり、どちらも素数でない。よって解はない。
$n\ge3$ では $\varphi(n)$ は偶数である（prop-euler-phi-function-even）が、この例はその逆「すべての偶数は $\varphi$ の値になる」という含意を破る。
性質
乗法性
$m,n$ を互いに素な正の整数とすると
$$
\varphi(mn)=\varphi(m)\varphi(n)
$$
である。
まず、整数 $k$ について
$$
\gcd(k,mn)=1\iff\gcd(k,m)=1\ \text{かつ}\ \gcd(k,n)=1
$$
である。(⇒) $k$ と $m$ の公約数は $k$ と $mn$ の公約数なので $\pm1$ に限り、$n$ についても同じである。(⇐) は 互いに素 の記事の命題「互いに素な因子の消去」の 2 である。
$1$ から $mn$ までの整数を、$m$ 列 $n$ 行の表
$$
\begin{array}{cccc}
1&2&\cdots&m\\
m+1&m+2&\cdots&2m\\
\vdots&\vdots&&\vdots\\
(n-1)m+1&(n-1)m+2&\cdots&nm
\end{array}
$$
に並べる。第 $r$ 列（$1\le r\le m$）は $r,\ r+m,\ \dots,\ r+(n-1)m$ である。
$\gcd(r+jm,m)=\gcd(r,m)$ なので、第 $r$ 列の数が $m$ と互いに素かどうかは $r$ だけで決まる。$m$ と互いに素な数を含む列は $\gcd(r,m)=1$ となる $\varphi(m)$ 個の列であり、その列の数はすべて $m$ と互いに素である。
次に、そのような 1 つの列 $r,r+m,\dots,r+(n-1)m$ の $n$ 個の数は、どの 2 つも $n$ を法として合同でない。実際 $r+jm\equiv r+j'm\pmod n$（$0\le j,j'\le n-1$）なら $n\mid m(j-j')$ で、$\gcd(m,n)=1$ なので $n\mid j-j'$（互いに素 の記事の命題「互いに素な因子の消去」の 1）、$|j-j'|< n$ から $j=j'$ である。よってこの列は法 $n$ の完全剰余系であり、そのうち $n$ と互いに素なものはちょうど $\varphi(n)$ 個ある（def-euler-phi-function-reduced-residue-system の後の注意）。
以上から、表の中で $m$ とも $n$ とも互いに素な数、すなわち $mn$ と互いに素な数は $\varphi(m)\varphi(n)$ 個である。$\square$
$m=4$、$n=3$ の表は $1,2,3,4\,/\,5,6,7,8\,/\,9,10,11,12$ で、$4$ と互いに素な列は第 $1$ 列 $1,5,9$ と第 $3$ 列 $3,7,11$ の 2 列、そのそれぞれで $3$ と互いに素なものが $2$ 個（$1,5$ と $7,11$）あり、$\varphi(12)=2\cdot2=4$ となる。この証明は Euler による最初の証明と同じ考え方である（Dic19 Chapter V、原本 p. 113）。環の言葉を使えば、中国剰余定理 による同型 $\mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$ が単元群の同型を引き起こすことからも従う（互いに素 の記事の系「Euler関数の乗法性」、Ste17 の PDF 版 Lemma 2.2.5（p. 30）、Proposition 2.2.7（p. 31））。
素因数分解による公式
$n\ge2$ の素因数分解を $n=p_1^{e_1}\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\prod_{i=1}^{r}\Bigl(1-\frac1{p_i}\Bigr)
$$
である。右辺の積を空積 $1$ と約束すれば、$n=1$（$r=0$）でも成り立つ。
$r$ に関する帰納法で $\varphi(n)=\prod_{i=1}^r\varphi(p_i^{e_i})$ を示す。$r=1$ なら自明である。$r\ge2$ とすると、$p_1^{e_1}\cdots p_{r-1}^{e_{r-1}}$ と $p_r^{e_r}$ は共通の素因数をもたないので互いに素であり（互いに素 の記事の定理「整数が互いに素であることの言い換え」の 4）、thm-euler-phi-function-multiplicative と帰納法の仮定から主張が従う。ex-euler-phi-function-prime により $\varphi(p_i^{e_i})=p_i^{e_i-1}(p_i-1)=p_i^{e_i}(1-1/p_i)$ であり、これらを掛け合わせれば 2 つの等式を得る。$\square$
たとえば $360=2^3\cdot3^2\cdot5$ から $\varphi(360)=4\cdot6\cdot4=96$、$60=2^2\cdot3\cdot5$ から $\varphi(60)=2\cdot2\cdot4=16$ である（後者は Gauss が例に挙げた値である。Gau01 Art. 38）。同じ公式は、$n$ の素因数で割り切れる数を包除原理で除いていく方法でも証明できる。
公式を展開すると、Möbius 関数による表示が得られる。Möbius関数 $\mu$ を、$\mu(1)=1$、$d$ が相異なる $k$ 個の素数の積なら $\mu(d)=(-1)^k$、$d$ が $1$ より大きい平方数で割り切れるなら $\mu(d)=0$ と定める。
任意の正の整数 $n$ について
$$
\varphi(n)=\sum_{d\mid n}\mu(d)\,\frac nd
$$
である。和は $n$ の正の約数 $d$ 全体にわたる。
$n=1$ では両辺とも $1$ である。$n\ge2$ の相異なる素因数を $p_1,\dots,p_r$ とする。$\prod_{i=1}^r(1-1/p_i)$ を展開すると、$\{1,\dots,r\}$ の各部分集合 $S$ について項 $(-1)^{|S|}/\prod_{i\in S}p_i$ が 1 回ずつ現れる。$S\mapsto d=\prod_{i\in S}p_i$ は、部分集合と「$n$ の約数で平方数の因子をもたないもの」との 1 対 1 対応であり、このとき $(-1)^{|S|}=\mu(d)$ である。$n$ の約数で平方数の因子をもつものは $\mu(d)=0$ なので、和に加えても値は変わらない。よって $\prod_i(1-1/p_i)=\sum_{d\mid n}\mu(d)/d$ であり、両辺に $n$ を掛けて thm-euler-phi-function-product から主張を得る。$\square$
約数についての和
任意の正の整数 $n$ について
$$
\sum_{d\mid n}\varphi(d)=n
$$
である。和は $n$ の正の約数 $d$ 全体にわたる。
$n$ 個の分数 $\frac1n,\frac2n,\dots,\frac nn$ を既約分数に直す。$1\le k\le n$ について $g=\gcd(k,n)$ とおくと、$\frac kn=\frac ad$（$a=k/g$、$d=n/g$）で、$d$ は $n$ の約数、$1\le a\le d$、$\gcd(a,d)=1$ である。
逆に、$n$ の約数 $d$ と、$1\le a\le d$、$\gcd(a,d)=1$ を満たす $a$ の組 $(d,a)$ に対し、$k=a\cdot\frac nd$ とおくと $1\le k\le n$ で $\frac kn=\frac ad$ である。既約分数の表し方は一意なので（$\frac ad=\frac{a'}{d'}$ で両方既約なら $ad'=a'd$ から $d\mid d'$ かつ $d'\mid d$ となり、$d=d'$、$a=a'$）、この 2 つの対応は互いに逆である。
したがって $k\in\{1,\dots,n\}$ と組 $(d,a)$ は 1 対 1 に対応し、分母が $d$ になる $k$ の個数は $\varphi(d)$ である。すべての約数 $d$ について足して $n=\sum_{d\mid n}\varphi(d)$ を得る。$\square$
$n=12$ では、$\frac1{12},\dots,\frac{12}{12}$ を約分すると分母は $12$ が $4$ 個、$6$ が $2$ 個（$\frac16,\frac56$）、$4$ が $2$ 個、$3$ が $2$ 個、$2$ が $1$ 個、$1$ が $1$ 個であり、$\varphi(12)+\varphi(6)+\varphi(4)+\varphi(3)+\varphi(2)+\varphi(1)=4+2+2+2+1+1=12$ である。この公式は Gauss が証明した（Gau01 Art. 39。例として $n=30$ で確かめている）。巡回群の言葉では、位数 $n$ の巡回群には位数 $d$ の元がちょうど $\varphi(d)$ 個あり（$d\mid n$）、元を位数で分類して数えたものがこの公式である。実際、位数 $d$ の元は位数 $d$ の巡回群を生成するので、巡回群 の記事の命題「有限巡回群の部分群と約数」によりただ 1 つの部分群 $\langle h\rangle$（$h$ は位数 $d$）の元である。$\langle h\rangle$ の元 $h^k$（$0\le k< d$）の位数が $d$ であることは $\gcd(k,d)=1$ と同値なので、その個数は $\varphi(d)$ である。
偶奇
$n\ge3$ ならば $\varphi(n)$ は偶数である。さらに $n\ge2$ について、$1\le k\le n$ で $n$ と互いに素な $k$ の総和は $\frac12n\varphi(n)$ である。
$n\ge2$ とする。$\gcd(n-k,n)=\gcd(k,n)$ なので、$1\le k\le n-1$ で $n$ と互いに素な $k$ に $n-k$ を対応させると、同じ集合の上の対応になる（$n\ge2$ では $k=n$ は数えられない）。$k=n-k$ となるのは $n=2k$ のときで、そのとき $\gcd(k,n)=k$ なので $k=1$、$n=2$ に限る。よって $n\ge3$ では $n$ と互いに素な数は $\{k,n-k\}$ の組に分かれ、$\varphi(n)$ は偶数である。各組の和は $n$ で、組は $\varphi(n)/2$ 個あるので総和は $\frac12n\varphi(n)$ である。$n=2$ では該当する数は $1$ だけで、総和 $1=\frac12\cdot2\cdot1$ である。$\square$
補足
$p,q$ を相異なる素数とし $n=pq$ とすると、乗法性と ex-euler-phi-function-prime から $\varphi(n)=(p-1)(q-1)$ である。RSA暗号ではこの値を秘密にして鍵を作る（Ste17 の PDF 版 §3.3、p. 56）。この $n=pq$ の形では、$\varphi(n)$ を求めることと $n$ を素因数分解することは同じ手間で互いに移り合う。$p,q$ が分かれば $\varphi(n)$ はすぐ計算でき、逆に $n$ と $\varphi(n)$ が分かれば $p+q=n-\varphi(n)+1$ と $pq=n$ が分かるので、$p,q$ は 2 次方程式 $x^2-(n-\varphi(n)+1)x+n=0$ の 2 つの解として求まる。たとえば $n=91$、$\varphi(91)=72$ なら $x^2-20x+91=0$ の解 $7,13$ が得られる。
- $a$ が $n$ と互いに素なら $a^{\varphi(n)}\equiv1\pmod n$ である（Eulerの定理(整数論)）。$n$ が素数 $p$ のときは $\varphi(p)=p-1$ で、Fermatの小定理 になる。
- 素数 $p$ を法とする原始根は、法 $p$ でちょうど $\varphi(p-1)$ 個ある（原始根 の記事を参照）。
- 1 の原始 $n$ 乗根を根とする円分多項式の次数は $\varphi(n)$ である。$\zeta=e^{2\pi i/n}$ の冪 $\zeta^k$（$1\le k\le n$）のうち原始 $n$ 乗根であるものはちょうど $\gcd(k,n)=1$ を満たすものなので、その個数 $\varphi(n)$ が次数になる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
