整数と合同式

この章の目標

• 除法の原理から出発して、最大公約数・ベズーの等式・素因数分解の一意性を証明できる
• 合同式と $\mathbb{Z}/n\mathbb{Z}$ を自在に計算し、中国剰余定理・オイラーの定理を使える
• 法 $p$ の原始根の存在を証明し、ルジャンドル記号と平方剰余の相互法則で平方剰余を判定できる

前提：00-foundations 第4章（同値関係と商集合）、00-foundations 第7章（整数の構成と整列性）

代数学を整数から始めるのには理由がある。整数全体 $\mathbb{Z}$ は「足し算・引き算・掛け算ができるが、割り算は一般にはできない」世界の原型であり、後の章で抽象化される概念――イデアル、単項イデアル整域、剰余環、単元群、巡回群――がすべて具体的な形でここに現れる。この章では群や環の言葉をまだ使わずに議論するが、後で抽象化されるポイントには注意を添えておく。

本章を通じて、次の整列性 (well-ordering principle) を自由に使う：$\mathbb{Z}_{\geq 0}$ の空でない部分集合は最小元をもつ。これは数学的帰納法と同値な、整数の基本性質である（00-foundations 第7章）。

1.1 整除と除法の原理

定義 1.1（整除, divisibility）$a, b \in \mathbb{Z}$ とする。$b = ac$ となる $c \in \mathbb{Z}$ が存在するとき、$a$ は $b$ を割り切る (divide) といい、$a \mid b$ と書く。このとき $a$ を $b$ の約数 (divisor)、$b$ を $a$ の倍数 (multiple) という。割り切らないときは $a \nmid b$ と書く。

例 1.2 $3 \mid 12$、$-3 \mid 12$、$5 \nmid 12$ である。任意の $a$ について $a \mid 0$（$0 = a \cdot 0$）であり、特に $0 \mid 0$ である。一方 $0 \mid b$ となるのは $b = 0$ のときに限る。また $\pm 1$ はすべての整数を割り切る。

命題 1.3（整除の基本性質）$a, b, c \in \mathbb{Z}$ とする。

1. $a \mid b$ かつ $b \mid c$ ならば $a \mid c$。
2. $a \mid b$ かつ $a \mid c$ ならば、任意の $x, y \in \mathbb{Z}$ について $a \mid bx + cy$。
3. $a \mid b$ かつ $b \neq 0$ ならば $\lvert a \rvert \leq \lvert b \rvert$。
4. $a \mid b$ かつ $b \mid a$ ならば $a = \pm b$。

証明. (1) $b = as$, $c = bt$ ならば $c = a(st)$。(2) $b = as$, $c = at$ ならば $bx + cy = a(sx + ty)$。(3) $b = ac$ で $b \neq 0$ なら $c \neq 0$ だから $\lvert c \rvert \geq 1$ であり、$\lvert b \rvert = \lvert a \rvert \lvert c \rvert \geq \lvert a \rvert$。(4) $a = 0$ なら $b = 0$ で成り立つ。$a \neq 0$ なら $b \neq 0$ でもあり、(3) より $\lvert a \rvert \leq \lvert b \rvert \leq \lvert a \rvert$、よって $\lvert a \rvert = \lvert b \rvert$。$\square$

割り算の「商と余り」を保証するのが次の定理であり、本章のほぼすべての議論の出発点になる。

定理 1.4（除法の原理, division algorithm）$a \in \mathbb{Z}$, $b \in \mathbb{N}$ とする。このとき

$$a = bq + r, \qquad 0 \leq r < b$$

をみたす整数 $q, r$ がただ一組存在する。$q$ を商 (quotient)、$r$ を余り (remainder) という。

証明. 存在：$S = \lbrace a - bk \mid k \in \mathbb{Z} \rbrace \cap \mathbb{Z}_{\geq 0}$ とおく。$k = -\lvert a \rvert$ とすると $a - bk = a + b\lvert a \rvert \geq a + \lvert a \rvert \geq 0$ だから $S \neq \emptyset$ である。整列性により $S$ の最小元 $r = a - bq$ がとれる。$r \geq 0$ であり、もし $r \geq b$ ならば $r - b = a - b(q+1) \in S$ で $r - b < r$ となり最小性に反する。よって $0 \leq r < b$。

一意性：$a = bq + r = bq' + r'$（$0 \leq r, r' < b$）とすると $b(q - q') = r' - r$ だから $b \mid r' - r$ である。$\lvert r' - r \rvert < b$ なので命題 1.3 (3) より $r' - r = 0$、したがって $q = q'$ でもある。$\square$

注意 1.5 商 $q$ は $\lfloor a/b \rfloor$（$a/b$ 以下の最大の整数）に等しい。負の数の割り算では余りを $0$ 以上にとるのが約束であり、たとえば $-17 = 5 \cdot (-4) + 3$ である（$-17 = 5 \cdot (-3) - 2$ ではない）。$b < 0$ の場合も $0 \leq r < \lvert b \rvert$ として同様の主張が成り立つ。

1.2 最大公約数とユークリッドの互除法

定義 1.6（最大公約数, greatest common divisor）$a, b \in \mathbb{Z}$ の少なくとも一方が $0$ でないとき、$a, b$ の公約数（両方を割り切る整数）のうち最大のものを $a, b$ の最大公約数といい、$\gcd(a, b)$ と書く。$\gcd(0, 0) := 0$ と約束する。$\gcd(a, b) = 1$ のとき $a, b$ は互いに素 (coprime, relatively prime) であるという。

公約数は有限個（$0$ でない方の絶対値以下）で $1$ を含むから、最大公約数は存在して正である。次の定理は、最大公約数が「$a$ と $b$ の整数係数の一次結合全体」によって特徴づけられることを示す。この見方は第6章で単項イデアル整域として一般化される。

定理 1.7（ベズーの等式, Bézout's identity）$a, b \in \mathbb{Z}$ の少なくとも一方は $0$ でないとし、$d = \gcd(a, b)$ とおく。

1. $ax + by = d$ をみたす $x, y \in \mathbb{Z}$ が存在する。
2. $\lbrace ax + by \mid x, y \in \mathbb{Z} \rbrace = \lbrace dk \mid k \in \mathbb{Z} \rbrace$ である。
3. $a, b$ の任意の公約数 $c$ は $d$ を割り切る。

証明. $I = \lbrace ax + by \mid x, y \in \mathbb{Z} \rbrace$ とおく。$a^2 + b^2 > 0$ は $I$ の正の元だから、整列性により $I$ の正の元の最小値 $d_0$ がとれる。

まず $I = \lbrace d_0 k \mid k \in \mathbb{Z} \rbrace$ を示す。$I$ は和と整数倍で閉じているから $d_0$ の倍数は $I$ に属する。逆に $n \in I$ を $n = d_0 q + r$（$0 \leq r < d_0$）と割ると、$r = n - d_0 q \in I$ であり、$d_0$ の最小性から $r = 0$ でなければならない。よって $n$ は $d_0$ の倍数である。

$a = a \cdot 1 + b \cdot 0 \in I$、$b \in I$ だから、$d_0$ は $a, b$ の公約数であり、$d_0 \leq d$ である。一方、$a, b$ の任意の公約数 $c$ は命題 1.3 (2) により $I$ のすべての元、特に $d_0$ を割り切る。$c = d$ とすると $d \mid d_0$ だから $d \leq d_0$。以上より $d = d_0$ であり、(1)〜(3) がすべて示された。$\square$

系 1.8 $\gcd(a, b) = 1$ であるための必要十分条件は、$ax + by = 1$ となる整数 $x, y$ が存在することである。

証明. 必要性は定理 1.7 (1)。逆に $ax + by = 1$ なら、公約数 $c$ は $1$ を割り切るので $c = \pm 1$ である。$\square$

命題 1.9 $a \mid bc$ かつ $\gcd(a, b) = 1$ ならば $a \mid c$ である。

証明. $ax + by = 1$ とすると $c = acx + bcy$。右辺の 2 項はともに $a$ で割り切れる（第 2 項は $a \mid bc$ による）。$\square$

実際に最大公約数を計算するには、次の補題を繰り返し使う。

補題 1.10 $a = bq + r$ ならば $\gcd(a, b) = \gcd(b, r)$ である。

証明. $c \mid a, c \mid b$ ならば $c \mid a - bq = r$。逆に $c \mid b, c \mid r$ ならば $c \mid bq + r = a$。よって $(a, b)$ の公約数全体と $(b, r)$ の公約数全体は一致する。$\square$

ユークリッドの互除法 (Euclidean algorithm) とは、$r_{-1} = a$, $r_0 = b$（$b > 0$）から始めて $r_{k-1} = r_k q_{k+1} + r_{k+1}$（$0 \leq r_{k+1} < r_k$）と割り算を繰り返す手続きである。余りは真に減少する非負整数だから有限回で $0$ に到達し、補題 1.10 により最後の $0$ でない余りが $\gcd(a, b)$ になる。

例 1.11 $\gcd(252, 198)$ を求める。

よって $\gcd(252, 198) = 18$。式を下から逆にたどると

となり、ベズーの等式の係数 $x = 4$, $y = -5$ が得られる。係数は次の表のように前向きに計算してもよい（拡張ユークリッド互除法）。各行は $r = 252x + 198y$ をみたし、新しい行は「2 行前 − 商 × 1 行前」で作る。

係数は一意ではない：$x = 4 + 11t$, $y = -5 - 14t$（$t \in \mathbb{Z}$）もすべて解である（$252/18 = 14$, $198/18 = 11$）。

注意 1.12 $a, b \neq 0$ の公倍数のうち正で最小のものを最小公倍数 (least common multiple) といい $\operatorname{lcm}(a, b)$ と書く。$\gcd(a, b) \operatorname{lcm}(a, b) = \lvert ab \rvert$ が成り立ち（問題 1.1 の解答の後の注意を参照）、$a, b$ の公倍数全体は $\operatorname{lcm}(a, b)$ の倍数全体に一致する。第5章の言葉では、$a\mathbb{Z} + b\mathbb{Z} = \gcd(a, b)\mathbb{Z}$、$a\mathbb{Z} \cap b\mathbb{Z} = \operatorname{lcm}(a, b)\mathbb{Z}$ というイデアルの等式である。

1.3 素数と素因数分解の一意性

定義 1.13（素数, prime number）$2$ 以上の整数 $p$ で、正の約数が $1$ と $p$ だけであるものを素数という。$2$ 以上の整数で素数でないものを合成数 (composite number) という。

素数の本質的な性質は、定義そのものよりも次の補題にある。第6章では、定義 1.13 に対応する性質（既約元）と補題 1.14 に対応する性質（素元）が一般の環では一致しないことを見る。

補題 1.14（ユークリッドの補題, Euclid's lemma）$p$ を素数とする。$p \mid ab$ ならば $p \mid a$ または $p \mid b$ である。

証明. $p \nmid a$ とする。$\gcd(p, a)$ は $p$ の正の約数なので $1$ か $p$ であり、$p \nmid a$ より $\gcd(p, a) = 1$。命題 1.9 より $p \mid b$。$\square$

帰納法により、$p \mid a_1 a_2 \cdots a_n$ ならばある $i$ で $p \mid a_i$ となる。

定理 1.15（算術の基本定理, fundamental theorem of arithmetic）$2$ 以上の任意の整数は素数の積として表され、その表し方は積の順序を除いて一意的である。

証明. 存在：$n \geq 2$ についての完全帰納法による。$n$ が素数ならそれ自身が表示である。合成数なら $n = ab$（$1 < a, b < n$）と書け、帰納法の仮定により $a, b$ はそれぞれ素数の積だから $n$ もそうである。

一意性：$p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$（$p_i, q_j$ は素数）のとき、$r = s$ かつ並べ替えれば $p_i = q_i$ となることを $r$ についての帰納法で示す。$p_1 \mid q_1 \cdots q_s$ だから補題 1.14 によりある $j$ で $p_1 \mid q_j$ であり、$q_j$ は素数で $p_1 > 1$ だから $p_1 = q_j$。番号を付け替えて $j = 1$ としてよい。両辺を $p_1$ で割ると $p_2 \cdots p_r = q_2 \cdots q_s$。$r = 1$ のときは左辺が $1$ になるので右辺も空積、すなわち $s = 1$ である（素数は $1$ より大きいから）。$r \geq 2$ のときは左辺が $1$ より大きいので右辺も空積ではなく、$s \geq 2$ である。よって両辺はそれぞれ $r - 1$ 個、$s - 1$ 個（ともに $1$ 個以上）の素数の積であり、帰納法の仮定から $r - 1 = s - 1$ かつ並べ替えれば $p_i = q_i$（$i \geq 2$）が従う。$\square$

各 $n \geq 2$ は $n = p_1^{e_1} \cdots p_k^{e_k}$（$p_1 < \cdots < p_k$ は素数、$e_i \geq 1$）と一意に書ける。これを $n$ の素因数分解 (prime factorization) という。$a = \prod p^{e_p}$, $b = \prod p^{f_p}$ ならば $\gcd(a, b) = \prod p^{\min(e_p, f_p)}$、$\operatorname{lcm}(a, b) = \prod p^{\max(e_p, f_p)}$ である。

定理 1.16（ユークリッド）素数は無限に存在する。

証明. 素数が $p_1, \dots, p_k$ だけだとすると、$N = p_1 \cdots p_k + 1 \geq 2$ の素因数 $p$ はある $p_i$ に等しい。すると $p \mid N - p_1 \cdots p_k = 1$ となり矛盾。$\square$

例 1.17（一意性は自明ではない）$H = \lbrace 1, 5, 9, 13, 17, 21, \dots \rbrace = \lbrace 4k + 1 \mid k \in \mathbb{Z}_{\geq 0} \rbrace$ は掛け算で閉じている。$H$ の中だけで考えて、$1$ より大きく $H$ の $1$ でない $2$ 元の積に書けない元を「$H$-素数」と呼ぶ。$9 = 3 \cdot 3$, $21 = 3 \cdot 7$, $49 = 7 \cdot 7$ はいずれも $H$-素数である（$3, 7 \notin H$ だから）。ところが

であり、$H$ の中では「素因数分解」が一意でない。定理 1.15 の証明で本質的だったのは補題 1.14 であり、その根拠はベズーの等式、つまり「足し算と引き算もできる」ことだった。$H$ は足し算で閉じていないため、この論法が使えない。第6章では、足し算も掛け算もできる環 $\mathbb{Z}[\sqrt{-5}]$ でさえ一意性が壊れることを見る。

1.4 合同式と $\mathbb{Z}/n\mathbb{Z}$

「$7$ 時間後は何時か」「今日から $100$ 日後は何曜日か」という計算は、ある数で割った余りだけに注目する計算である。これを定式化したのが合同式である。

定義 1.18（合同, congruence）$n \in \mathbb{N}$ とする。$n \mid a - b$ のとき、$a$ と $b$ は $n$ を法として合同 (congruent modulo $n$) であるといい、$a \equiv b \pmod{n}$ と書く。

$a \equiv b \pmod{n}$ は「$a$ と $b$ を $n$ で割った余りが等しい」ことと同値である。

命題 1.19 法 $n$ の合同は同値関係であり、さらに和と積と両立する：$a \equiv a'$, $b \equiv b' \pmod{n}$ ならば

$$a + b \equiv a' + b', \qquad ab \equiv a'b' \pmod{n}$$

証明. 反射律・対称律は明らか。推移律は $n \mid a - b$, $n \mid b - c$ ならば $n \mid (a - b) + (b - c) = a - c$ による。和については $(a + b) - (a' + b') = (a - a') + (b - b')$、積については

の右辺がともに $n$ の倍数であることから従う。$\square$

定義 1.20（剰余類と $\mathbb{Z}/n\mathbb{Z}$）法 $n$ の合同による $a$ の同値類 $\overline{a} = a + n\mathbb{Z} = \lbrace a + nk \mid k \in \mathbb{Z} \rbrace$ を $a$ の剰余類 (residue class) といい、剰余類全体の集合を $\mathbb{Z}/n\mathbb{Z}$ と書く。除法の原理により

$$\mathbb{Z}/n\mathbb{Z} = \lbrace \overline{0}, \overline{1}, \dots, \overline{n-1} \rbrace$$

であり、これらは相異なる（ちょうど $n$ 個の元がある）。演算を $\overline{a} + \overline{b} := \overline{a + b}$、$\overline{a} \cdot \overline{b} := \overline{ab}$ で定める。

演算が代表元のとり方によらずに定まる（well-defined である）ことは、命題 1.19 そのものである。$\mathbb{Z}$ の和・積の結合法則・交換法則・分配法則は代表元の計算からそのまま $\mathbb{Z}/n\mathbb{Z}$ に遺伝し、$\overline{0}$ が和の単位元、$\overline{1}$ が積の単位元、$\overline{-a}$ が $\overline{a}$ の和に関する逆元となる。第5章の言葉では、$\mathbb{Z}/n\mathbb{Z}$ は可換環である。

例 1.21 $\mathbb{Z}/6\mathbb{Z}$ の積の表は次のとおり（上線を省略して代表元で書く）。

$\overline{2} \cdot \overline{3} = \overline{0}$ のように、$0$ でない元の積が $0$ になりうる。また $1$ が現れる行は $1$ と $5$ の行だけであり、掛けて $\overline{1}$ にできる相手をもつのは $\overline{1}, \overline{5}$ だけである。

定義 1.22（単元）$\overline{a} \in \mathbb{Z}/n\mathbb{Z}$ に対し $\overline{a}\ \overline{b} = \overline{1}$ となる $\overline{b}$ が存在するとき、$\overline{a}$ を単元（可逆元, unit）といい、$\overline{b}$ を $\overline{a}$ の逆元とよぶ。単元全体を $(\mathbb{Z}/n\mathbb{Z})^\times$ と書き、既約剰余類群 (group of units modulo $n$) という。

$(\mathbb{Z}/n\mathbb{Z})^\times$ は積で閉じており（$\overline{a}, \overline{b}$ の逆元が $\overline{a'}, \overline{b'}$ なら $\overline{ab}$ の逆元は $\overline{a'b'}$）、第2章で見るように群をなす。

定理 1.23 $\overline{a} \in (\mathbb{Z}/n\mathbb{Z})^\times \iff \gcd(a, n) = 1$。

証明. $\overline{a}\ \overline{b} = \overline{1}$ となる $b$ が存在する $\iff$ $ab + nk = 1$ となる $b, k \in \mathbb{Z}$ が存在する $\iff$ $\gcd(a, n) = 1$（系 1.8）。$\square$

系 1.24 $\mathbb{Z}/n\mathbb{Z}$ の $\overline{0}$ でないすべての元が単元であるための必要十分条件は、$n$ が素数であることである。

証明. $n$ が素数なら $1 \leq a \leq n - 1$ に対して $\gcd(a, n) = 1$ である。$n = 1$ のときは $\mathbb{Z}/1\mathbb{Z} = \lbrace \overline{0} \rbrace$ で $\overline{1} = \overline{0}$ となり、ここでは条件をみたさないと約束する（第5章で体の定義に $1 \neq 0$ を含める）。$n$ が合成数で $n = ab$（$1 < a < n$）なら $\gcd(a, n) = a > 1$ で $\overline{a} \neq \overline{0}$ は単元でない。$\square$

$p$ が素数のとき、$\mathbb{Z}/p\mathbb{Z}$ は四則演算（$0$ 以外での割り算を含む）が自由にできる体であり、$\mathbb{F}_p$ と書く（第5章・第8章）。

例 1.25（逆元の計算）$17$ の法 $43$ での逆元を求める。互除法 $43 = 2 \cdot 17 + 9$, $17 = 1 \cdot 9 + 8$, $9 = 1 \cdot 8 + 1$ を逆にたどると

よって $17 \cdot (-5) \equiv 1 \pmod{43}$ であり、逆元は $\overline{-5} = \overline{38}$ である。

命題 1.26（一次合同式）$d = \gcd(a, n)$ とする。合同式 $ax \equiv b \pmod{n}$ が解をもつための必要十分条件は $d \mid b$ であり、このとき解は法 $n$ でちょうど $d$ 個ある。

証明. 解 $x$ があれば $b = ax - nk$ と書けるので $d \mid b$。逆に $d \mid b$ とし、$a = da'$, $n = dn'$, $b = db'$ と書く。$n \mid ax - b \iff dn' \mid d(a'x - b') \iff n' \mid a'x - b'$ だから、元の合同式は $a'x \equiv b' \pmod{n'}$ と同値である。$\gcd(a', n') = 1$ なので $a'$ は法 $n'$ で逆元をもち、解は法 $n'$ でただ一つ $x \equiv x_0$ である。法 $n$ で見れば $x_0, x_0 + n', \dots, x_0 + (d-1)n'$ の $d$ 個になる。$\square$

例 1.27 $12x \equiv 18 \pmod{30}$ は $\gcd(12, 30) = 6 \mid 18$ より解をもつ。$6$ で割って $2x \equiv 3 \pmod{5}$、$2$ の逆元は $3$ だから $x \equiv 9 \equiv 4 \pmod{5}$。法 $30$ では $x \equiv 4, 9, 14, 19, 24, 29$ の $6$ 個である。一方 $12x \equiv 20 \pmod{30}$ は $6 \nmid 20$ だから解をもたない。

1.5 中国剰余定理

複数の法についての合同式を同時にみたす数を求める問題は古くから考えられてきた（古代中国の算書『孫子算経』にこの種の問題が見られるのが名前の由来である）。

定理 1.28（中国剰余定理, Chinese remainder theorem）$n_1, \dots, n_k \in \mathbb{N}$ はどの 2 つも互いに素であるとし、$N = n_1 n_2 \cdots n_k$ とおく。任意の整数 $a_1, \dots, a_k$ に対し、連立合同式

$$x \equiv a_1 \pmod{n_1}, \quad \dots, \quad x \equiv a_k \pmod{n_k}$$

は解をもち、解は法 $N$ でただ一つである。言い換えると、写像

$$\Phi\colon \mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}, \qquad x + N\mathbb{Z} \mapsto (x + n_1\mathbb{Z}, \dots, x + n_k\mathbb{Z})$$

は全単射であり、成分ごとの和と積を保つ。

証明. $n_i \mid N$ だから $x \equiv y \pmod{N}$ ならば $x \equiv y \pmod{n_i}$ であり、$\Phi$ は well-defined である。和と積を保つことは定義から明らか。

単射性：$\Phi(x) = \Phi(y)$ とすると、すべての $i$ で $n_i \mid x - y$。一般に $\gcd(m, n) = 1$, $m \mid c$, $n \mid c$ ならば $mn \mid c$ である（$c = mc'$ とすると $n \mid mc'$ で、命題 1.9 より $n \mid c'$）。$n_1 \cdots n_{i-1}$ と $n_i$ は互いに素である（共通の素因数 $p$ があれば補題 1.14 より $p$ はある $n_j$（$j < i$）と $n_i$ を割り切り、仮定に反する）から、$i$ についての帰納法で $n_1 \cdots n_i \mid x - y$ が示され、特に $N \mid x - y$。

全射性：両辺はともに $N$ 個の元からなる有限集合なので、単射ならば全射である。$\square$

解は具体的にも作れる。$N_i = N/n_i$ とおくと $\gcd(N_i, n_i) = 1$ だから $N_i M_i \equiv 1 \pmod{n_i}$ となる $M_i$ がある。$j \neq i$ なら $n_j \mid N_i$ なので、

は $x \equiv a_i N_i M_i \equiv a_i \pmod{n_i}$ をみたす。

例 1.29 $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$ を解く。$N = 105$、$N_1 = 35 \equiv 2 \pmod 3$ なので $M_1 = 2$、$N_2 = 21 \equiv 1 \pmod 5$ なので $M_2 = 1$、$N_3 = 15 \equiv 1 \pmod 7$ なので $M_3 = 1$。

実際 $23 = 3 \cdot 7 + 2 = 5 \cdot 4 + 3 = 7 \cdot 3 + 2$ である。

系 1.30 定理 1.28 の全単射 $\Phi$ は、単元どうしを全単射に対応させる：

実際、$\Phi$ は積と $\overline{1}$ を保つ全単射だから、$\overline{x}$ が逆元をもつことと、$\Phi(\overline{x})$ が成分ごとの積について逆元をもつこと、すなわち各成分が単元であることとが同値になる。

1.6 オイラー関数とフェルマー・オイラーの定理

定義 1.31（オイラー関数, Euler's totient function）$n \in \mathbb{N}$ に対し、$1 \leq a \leq n$ で $\gcd(a, n) = 1$ となる $a$ の個数を $\varphi(n)$ と書く。定理 1.23 により $\varphi(n) = \lvert (\mathbb{Z}/n\mathbb{Z})^\times \rvert$ である。

命題 1.32

1. $\gcd(m, n) = 1$ ならば $\varphi(mn) = \varphi(m)\varphi(n)$。
2. 素数 $p$ と $e \geq 1$ について $\varphi(p^e) = p^e - p^{e-1}$。
3. $\varphi(n) = n \displaystyle\prod_{p \mid n} \left(1 - \frac{1}{p}\right)$（積は $n$ の素因数 $p$ にわたる）。

証明. (1) 系 1.30 の全単射で元の個数を比べる。(2) $1, \dots, p^e$ のうち $p^e$ と互いに素でないのは $p$ の倍数 $p, 2p, \dots, p^{e-1} \cdot p$ の $p^{e-1}$ 個である。(3) $n = \prod p^{e_p}$ として (1), (2) を使うと $\varphi(n) = \prod p^{e_p}(1 - 1/p)$。$\square$

たとえば $\varphi(72) = 72 \cdot \frac{1}{2} \cdot \frac{2}{3} = 24$、$\varphi(100) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40$ である。

命題 1.33（ガウス）任意の $n \in \mathbb{N}$ について $\displaystyle\sum_{d \mid n} \varphi(d) = n$（和は $n$ の正の約数 $d$ にわたる）。

証明. $\lbrace 1, 2, \dots, n \rbrace$ を $\gcd(a, n)$ の値で分類する。$\gcd(a, n) = e$ となる $a$ は、$a = eb$ と書くと $1 \leq b \leq n/e$ かつ $\gcd(b, n/e) = 1$ をみたすものにちょうど対応するので、$\varphi(n/e)$ 個ある。よって $n = \sum_{e \mid n} \varphi(n/e)$ であり、$d = n/e$ も $n$ の約数全体を動くから結論を得る。$\square$

たとえば $n = 12$ では $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$ である。

定理 1.34（オイラーの定理, Euler's theorem）$\gcd(a, n) = 1$ ならば $a^{\varphi(n)} \equiv 1 \pmod{n}$。

証明. $r_1, \dots, r_m$（$m = \varphi(n)$）を、$1$ 以上 $n$ 以下で $n$ と互いに素な整数全体とする。$ar_1, \dots, ar_m$ はいずれも $n$ と互いに素であり、法 $n$ で相異なる（$ar_i \equiv ar_j$ なら $a$ の逆元を掛けて $r_i \equiv r_j$）。よって $\overline{ar_1}, \dots, \overline{ar_m}$ は $\overline{r_1}, \dots, \overline{r_m}$ の並べ替えであり、

$r_1 \cdots r_m$ は法 $n$ で逆元をもつので、これを両辺に掛けて $a^m \equiv 1$ を得る。$\square$

第2章では、この定理がラグランジュの定理（群の元の位数は群の位数を割り切る）の特別な場合であることを見る。

系 1.35（フェルマーの小定理, Fermat's little theorem）$p$ を素数とする。$p \nmid a$ ならば $a^{p-1} \equiv 1 \pmod{p}$ であり、任意の整数 $a$ について $a^p \equiv a \pmod{p}$ である。

証明. $\varphi(p) = p - 1$ だから前半は定理 1.34 から従う。後半は、$p \nmid a$ なら前半に $a$ を掛け、$p \mid a$ なら両辺とも $0$ である。$\square$

例 1.36 $2^{1000}$ を $13$ で割った余りは、$2^{12} \equiv 1$ と $1000 = 12 \cdot 83 + 4$ より $2^{1000} \equiv 2^4 = 16 \equiv 3 \pmod{13}$。同様に $3^{100} \equiv 3^{100 - 6 \cdot 16} = 3^4 = 81 \equiv 4 \pmod 7$。

注意 1.37 フェルマーの小定理の逆は成り立たない。$561 = 3 \cdot 11 \cdot 17$ は合成数だが、$\gcd(a, 561) = 1$ なるすべての $a$ で $a^{560} \equiv 1 \pmod{561}$ となる。実際 $2, 10, 16$ はいずれも $560$ を割り切るので、フェルマーの小定理から $a^{560} \equiv 1$ が法 $3$, $11$, $17$ のそれぞれで成り立ち、中国剰余定理（の単射性の部分）により法 $561$ でも成り立つ。このような合成数をカーマイケル数 (Carmichael number) という。