整除と素因数分解：互除法・中国剰余定理・オイラー関数

0. この記事の要点

二つの整数の「共通の約数のうち最大のもの」を、素因数分解をせずに素早く求めるにはどうすればよいでしょうか。また、「3 で割ると 2 余り、5 で割ると 3 余る数」のような条件を同時に満たす数は、いつ、どのくらいあるのでしょうか。この記事は、この二つの素朴な疑問に答える道具を順に作ります。読み終えると、最大公約数の計算とその回数の見積もり、連立する余りの条件の解き方、そして 1 から n までの数のうち n と共通の約数をもたないものの個数の求め方が分かります。

• ユークリッドの互除法は、最大公約数を求めるだけでなく、ベズーの等式 $\gcd(a,b)=ax+by$ の係数 $x,y$ も同時に与えます（拡張互除法）。割り算の回数は、小さい方の数の十進桁数の 5 倍以下です（ラメの定理。互除法が何回で終わるかの上限を与える定理です）。
• 素因数分解の一意性を $p$ 進付値 $v_p(n)$（$n$ が素数 $p$ で何回割り切れるかを表す数）の言葉で言い換えると、整除・最大公約数・最小公倍数がすべて指数の大小比較に翻訳されます。$\gcd(a,b)\cdot\mathrm{lcm}(a,b)=ab$ もその帰結です。
• 中国剰余定理の一般形：連立合同式 $x\equiv a\ (\mathrm{mod}\ m)$, $x\equiv b\ (\mathrm{mod}\ n)$ が解をもつ条件は $\gcd(m,n)\mid a-b$ で、解は $\mathrm{lcm}(m,n)$ を法として一意です。法が互いに素なら、常に解けて一意に定まります。
• 互いに素な法に分解すると、合同式の問題は素数べきを法とする問題に帰着します。$\mathbb{Z}/mn\mathbb{Z}$ と $\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$ の間の全単射がその仕組みです。
• オイラー関数 $\varphi(n)$ は乗法的（互いに素な二数の積での値が、それぞれの値の積になること）で、$\varphi(n)=n\prod_{p\mid n}(1-1/p)$。さらに $\sum_{d\mid n}\varphi(d)=n$ が成り立ちます。この恒等式は、次の記事までに原始根の存在証明に使われます。

この記事で使う事前知識

• 除法の原理: 整数 $a$ を正の整数 $b$ で割ると、商と、$0$ 以上 $b$ 未満の余りがただ一通りに決まる、という性質。→ 素数と素数定理
• ベズーの等式: 最大公約数は、もとの二数の整数倍の和として書ける、という性質。→ 素数と素数定理
• 算術の基本定理: 1 より大きい整数は素数の積に、順序を除いてただ一通りに書ける、という性質。→ 素数と素数定理
• 全単射: 二つの集合の要素が、漏れも重なりもなく一対一に対応する写像。
• フィボナッチ数: $1,1,2,3,5,8,\ldots$ のように、直前の二つの和が次の数になる数列。

1. 動機：二千三百年前のアルゴリズム

ユークリッドの『原論』第 7 巻の冒頭にある、二つの数の最大公約数を求める手順は、現存する最古のアルゴリズムの一つだと言われます。大きい方の数を小さい方で割った余りで、大きい方を置き換える。これを余りが $0$ になるまで繰り返す。それだけの手順で、素因数分解を一切せずに最大公約数が求まります。$10^{100}$ のような数の素因数分解は現実的な時間では不可能と考えられていますが、互除法は数百回の割り算で終わります。

この記事は、整数論の最も基本的な四つの道具を整理します。互除法、素因数分解の一意性、中国剰余定理、オイラー関数です。これらは 素数と素数定理 で得た基本事項（除法の原理、ベズーの等式、算術の基本定理）の上に建ち、次の記事 合同式とフェルマーの小定理 や 原始根と平方剰余の相互法則 の下敷きになります。

記号。 $\mathbb{Z}$ は整数全体、$\mathbb{Z}_{>0}$ は正の整数全体です。整数 $a,b$ について $a\mid b$ は「$b=ak$ となる整数 $k$ がある」ことを表します。$\gcd(a,b)$ は $a,b$ の最大公約数（定義 2.1［素数の魅力と素数定理］）で、$\gcd(a,b)=1$ のとき $a,b$ は互いに素といいます。この記事は次の二つの既出の事実を使います。

• 補題 2.3［素数の魅力と素数定理］（除法の原理）：$b>0$ のとき、$a=bq+r$, $0\le r<b$ となる整数の組 $(q,r)$ がただ一つ存在する。
• 補題 2.4［素数の魅力と素数定理］（ベズーの等式）：$a,b$ が共に $0$ でなければ、$\gcd(a,b)=ax_0+by_0$ となる整数 $x_0,y_0$ が存在する。

2. 最大公約数と最小公倍数

最小公倍数を、最小性だけでなく倍数の構造まで込めて定義し直します。

定義 2.1（最小公倍数）↗

正の整数 $m,n$ の最小公倍数 $\mathrm{lcm}(m,n)$ とは、$m$ と $n$ の正の公倍数のうち最小のものをいう。

補題 2.2（ユークリッドの補題（一般形））✓

$u,v,w$ を整数とし、$\gcd(u,v)=1$ とする。$u\mid vw$ ならば $u\mid w$ である。

証明（補題 2.2）

ベズーの等式（補題 2.4［素数の魅力と素数定理］）により $1=ux+vy$ となる整数 $x,y$ が取れる。両辺に $w$ を掛けて $w=u(wx)+(vw)y$。右辺の第 1 項は $u$ の倍数、第 2 項は仮定 $u\mid vw$ により $u$ の倍数なので、$u\mid w$。

∎

素数 $p$ に対する形（補題 4.1［素数の魅力と素数定理］）は、これで $u=p$ とした特別な場合です（$p\nmid v$ なら $\gcd(p,v)=1$）。次の合同式の記事の ユークリッドの補題 も同じ主張で、そこでは合同式の消去法則に使われます。

補題 2.3（互いに素な商）✓

$m,n$ を整数で少なくとも一方は $0$ でないとし、$g=\gcd(m,n)$ とすると、$\gcd(m/g,\,n/g)=1$ である。

証明（補題 2.3）

ベズーの等式により $g=mx+ny$ と書ける。両辺を $g$ で割って $1=(m/g)x+(n/g)y$。$m/g,n/g$ の正の公約数 $c$ は右辺を割り切り、$c\mid1$ なので $c=1$。

∎

命題 2.4（gcd と lcm の関係）✓

正の整数 $m,n$ について、$g=\gcd(m,n)$、$L=mn/g$ とおく。

1. $L$ は整数で、$m$ と $n$ の公倍数である。
2. $m$ と $n$ の公倍数はすべて $L$ の倍数である。特に $\mathrm{lcm}(m,n)=L$ であり、$\gcd(m,n)\cdot\mathrm{lcm}(m,n)=mn$。

証明（命題 2.4）

(1) $L=m\cdot(n/g)=n\cdot(m/g)$ なので、整数で、$m$ の倍数かつ $n$ の倍数。 (2) $c$ を公倍数とし、$c=mc'$ と書く。$n\mid mc'$ より $(n/g)\mid(m/g)c'$。$\gcd(n/g,m/g)=1$ なので（補題 2.3）、$(n/g)\mid c'$（補題 2.2）。$c'=(n/g)c''$ とおくと $c=mc'=Lc''$。したがって最小の正の公倍数は $L$。

∎

3. ユークリッドの互除法

3.1. アルゴリズムと正しさ

定義 3.1（ユークリッドの互除法）↗

正の整数 $a>b$ に対し、$r_{-1}=a$, $r_0=b$ とおき、$r_i>0$ である限り、除法の原理で

$$r_{i-1}=q_i\,r_i+r_{i+1},\qquad 0\le r_{i+1}<r_i\qquad(i=0,1,2,\ldots)$$

と商 $q_i$ と余り $r_{i+1}$ を定める。余りが初めて $0$ になる、すなわち $r_{n+1}=0$ となる $n$ を段数といい（余りが $0$ になる最後の割り算を含めて、割り算は $n+1$ 回行われる）、この手順をユークリッドの互除法という。

余りは真に減少する非負整数なので、必ず有限回で $0$ になります（整列性）。

定理 3.2（互除法の正しさと拡張）✓

互除法の最後の非零の余り $r_n$ は $\gcd(a,b)$ に等しい。さらに、整数列 $s_i,t_i$ を

$$s_{-1}=1,\ t_{-1}=0,\quad s_0=0,\ t_0=1,\qquad s_{i+1}=s_{i-1}-q_i s_i,\quad t_{i+1}=t_{i-1}-q_i t_i$$

で定めると、すべての $i$ について $r_i=a\,s_i+b\,t_i$ が成り立つ。特に $\gcd(a,b)=a\,s_n+b\,t_n$ である。

証明（定理 3.2）

最後の余り $=\gcd$。一般に $a=bq+r$ のとき $\gcd(a,b)=\gcd(b,r)$ である：$a,b$ の公約数は $r=a-bq$ を割り切り、$b,r$ の公約数は $a=bq+r$ を割り切るので、公約数の集合が一致する。これを繰り返して $\gcd(a,b)=\gcd(r_0,r_1)=\cdots=\gcd(r_n,r_{n+1})=\gcd(r_n,0)=r_n$。

係数。$i=-1$ では $r_{-1}=a=a\cdot1+b\cdot0$、$i=0$ では $r_0=b=a\cdot0+b\cdot1$ で正しい。$i-1,i$ で成り立つとすると、

$$r_{i+1}=r_{i-1}-q_ir_i=(as_{i-1}+bt_{i-1})-q_i(as_i+bt_i)=a\,s_{i+1}+b\,t_{i+1}.$$∎

ベズーの等式の存在証明（最小元を取る）と違い、これは係数を構成する手順を与えます。

例 3.3（252 と 105）

$a=252$, $b=105$ とします。

$$252=2\cdot105+42,\qquad105=2\cdot42+21,\qquad42=2\cdot21+0.$$

$n=2$（非零の余りは $42,21$）で、$\gcd(252,105)=21$。係数は $(q_0,q_1,q_2)=(2,2,2)$ から、$s_1=1-2\cdot0=1$, $t_1=0-2\cdot1=-2$（確かに $r_1=42=252-2\cdot105$）、$s_2=0-2\cdot1=-2$, $t_2=1-2\cdot(-2)=5$。よって

$$21=252\cdot(-2)+105\cdot5=-504+525.$$

互除法は長方形の分割とも読めます。縦 $105$、横 $252$ の長方形から、できるだけ大きい正方形を切り出し続けると、最後に残る正方形の一辺が最大公約数 $21$ です。

252 × 105 の長方形から、一辺 105 の正方形を 2 つ、残りの 42 × 105 から一辺 42 の正方形を 2 つ、残りの 42 × 21 から一辺 21 の正方形を 2 つ切り出す。最後の正方形の一辺が gcd。

3.2. 計算量：ラメの定理

互除法はどれだけ速いのでしょうか。割り算の回数を、フィボナッチ数 $F_1=F_2=1$, $F_{k+2}=F_{k+1}+F_k$ で評価できます。

定理 3.4（ラメの定理）✓

$a>b\ge1$ に対する互除法の段数を $n$ とすると、$b\ge F_{n+2}$（かつ $a\ge F_{n+3}$）。したがって $b<10^d$ ならば $n<5d$、すなわち割り算の回数 $n+1$ は $5d$ 以下である。

証明の方針：互除法が長く続くためには、余りがゆっくり減らなければなりません。ゆっくり減る最悪の場合を、末尾から逆にたどってフィボナッチ数で下から押さえます。後半は、フィボナッチ数が 5 つ進むごとに 10 倍を超えて大きくなること（$k\ge2$ で $F_{k+5}>10F_k$）を使って、桁数との関係に直します。

証明（定理 3.4）

$r_n\ge1$ で、$r_n\mid r_{n-1}$ かつ $r_{n-1}>r_n$ なので $r_{n-1}\ge2r_n\ge2$。各 $i\ge0$ で $q_i\ge1$ だから（$r_{i-1}>r_i$ なので商は $0$ にならない）$r_{i-1}=q_ir_i+r_{i+1}\ge r_i+r_{i+1}$。これを下から使う。$r_n\ge1=F_2$, $r_{n-1}\ge2=F_3$, $r_{n-2}\ge r_{n-1}+r_n\ge F_3+F_2=F_4$, ……と帰納的に $r_{n-j}\ge F_{j+2}$。$j=n$ で $b=r_0\ge F_{n+2}$、$j=n+1$ で $a=r_{-1}\ge F_{n+3}$。

後半。まず任意の $k\ge2$ で $F_{k+5}>10F_k$ を示す。$F_{k+5}=5F_{k+1}+3F_k$（展開すれば確かめられる）で、$k\ge2$ なら $F_{k+1}\ge\tfrac32F_k$（$k=2$ は $F_3=2F_2$。以降は $F_{k+1}\le2F_k$ より $F_{k+2}=F_{k+1}+F_k\ge F_{k+1}+\tfrac12F_{k+1}$）だから $F_{k+5}\ge\tfrac{15}{2}F_k+3F_k=10.5F_k$。ここから帰納法で $F_{5d+2}>10^d$（$d=1$: $F_7=13>10$）。$b<10^d$ とすると $F_{n+2}\le b<10^d<F_{5d+2}$。$F_k$ は広義単調増加なので $n+2<5d+2$、すなわち $n<5d$。

∎

等号に近い最悪の入力は、隣り合うフィボナッチ数 $(F_{n+3},F_{n+2})$ です。このとき最後の商を除いて商はすべて $1$ で、割り算の回数が最大になります。

4. 一次不定方程式

ベズーの等式の最も直接的な応用です。

命題 4.1（一次不定方程式）✓

$a,b$ を共に $0$ でない整数、$c$ を整数、$g=\gcd(a,b)$ とする。方程式 $ax+by=c$ が整数解をもつための必要十分条件は $g\mid c$ である。このとき一つの解 $(x_0,y_0)$ を用いて、解全体は

$$(x,y)=\Bigl(x_0+\frac{b}{g}k,\ y_0-\frac{a}{g}k\Bigr)\qquad(k\in\mathbb{Z})$$

で尽くされる。

証明（命題 4.1）

解があれば $g\mid a$, $g\mid b$ より $g\mid ax+by=c$。逆に $g\mid c$ とし、$c=gc'$ とする。ベズーの等式 $g=au+bv$ から $(x_0,y_0)=(uc',vc')$ が解になる。

$(x,y)$ を別の解とすると $a(x-x_0)=-b(y-y_0)$。$g$ で割って $(a/g)(x-x_0)=-(b/g)(y-y_0)$。$\gcd(a/g,b/g)=1$ なので（補題 2.3）、$(b/g)\mid(a/g)(x-x_0)$ に 補題 2.2 を使って $(b/g)\mid(x-x_0)$。$x-x_0=(b/g)k$ と書けば、$y-y_0=-(a/g)k$ が従う。逆にこの形の組が解であることは代入で確かめられる。

∎

例 4.2（252x + 105y = 63）

$g=21$, $63=21\cdot3$ なので解がある。例 3.3 の $21=252\cdot(-2)+105\cdot5$ を $3$ 倍して $(x_0,y_0)=(-6,15)$。一般解は $(x,y)=(-6+5k,\ 15-12k)$（$b/g=5$, $a/g=12$）。$k=1$ で $(-1,3)$：$-252+315=63$ ✓。

5. 素因数分解の一意性と付値

素数と素数定理 で証明した算術の基本定理は、「$1$ より大きい整数は素数の積に書け、その表し方は順序を除いて一意」というものでした（定理 4.2［素数の魅力と素数定理］）。ここでは、一意性を計算に使いやすい形に言い換えます。

定義 5.1（素数 p に関する付値）↗

素数 $p$ と正の整数 $n$ について、$p^e\mid n$ を満たす最大の整数 $e\ge0$ を $v_p(n)$ と書く。

定理 5.2（素因数分解の指数による表示）✓

正の整数 $n$ について、$v_p(n)$ は有限で、$v_p(n)\ne0$ となる素数 $p$ は有限個であり、

$$n=\prod_{p}p^{v_p(n)}$$

が成り立つ。さらに、素数べきの積として $n=\prod_pp^{e_p}$（$e_p\ge0$ で有限個を除いて $0$）と書く方法は、指数の組 $(e_p)_p=(v_p(n))_p$ のただ一つに限る。

証明の中の「空積」は、一つも因数がない積のことで、値は $1$ と約束します。したがって $n=1$ は、どの素数の指数も $0$ の表示に当たります。

証明（定理 5.2）

$n=1$ は空積。素数での指数の有限性は、$p^e\mid n$ なら $p^e\le n$ より $e<n$ から従う。まず、$n=\prod_pp^{e_p}$ という任意の表示（$e_p\ge0$、有限個を除いて $0$）について $e_p=v_p(n)$ を示す。$p^{e_p}\mid n$ は明らか。$p^{e_p+1}\mid n$ とすると、$n=p^{e_p}\prod_{q\ne p}q^{e_q}$ から $p\mid\prod_{q\ne p}q^{e_q}$。ユークリッドの補題（補題 4.1［素数の魅力と素数定理］）を繰り返すと、$p$ はある素数 $q\ne p$ を割り切るが、素数 $q$ の正の約数は $1$ と $q$ だけなので $p=q$ となり矛盾する。よって $e_p=v_p(n)$。

一方、$n>1$ には 定理 4.2［素数の魅力と素数定理］ により素数の積としての表示が存在する。同じ素数をまとめれば上の形の表示になるので、$n=\prod_pp^{v_p(n)}$ が成り立ち、$v_p(n)\ne0$ となる $p$ は表示に現れる素数に限るから有限個である。表示が $(v_p(n))_p$ に限ることは、前段で示したとおり。

∎

付値は積を和に変えます。

命題 5.3（付値の規則と gcd・lcm）✓

正の整数 $a,b$ と素数 $p$ について次が成り立つ。

1. $v_p(ab)=v_p(a)+v_p(b)$。
2. $a\mid b\iff$ すべての素数 $p$ で $v_p(a)\le v_p(b)$。
3. $v_p(\gcd(a,b))=\min(v_p(a),v_p(b))$、$v_p(\mathrm{lcm}(a,b))=\max(v_p(a),v_p(b))$。
4. 特に $\gcd(a,b)\,\mathrm{lcm}(a,b)=ab$（命題 2.4 の別証明）。

証明（命題 5.3）

(1) $a=\prod p^{v_p(a)}$, $b=\prod p^{v_p(b)}$ の積は $\prod p^{v_p(a)+v_p(b)}$ で、定理 5.2 の一意性により $v_p(ab)=v_p(a)+v_p(b)$。 (2) ($\Rightarrow$) $b=ak$ なら (1) より $v_p(b)=v_p(a)+v_p(k)\ge v_p(a)$。($\Leftarrow$) $k=\prod p^{v_p(b)-v_p(a)}$ は正の整数で $b=ak$。 (3) $c$ が $a,b$ の公約数であることは、(2) により「すべての $p$ で $v_p(c)\le\min(v_p(a),v_p(b))$」と同値。$\prod p^{\min}$ が最大の公約数。lcm も同様に $\max$。 (4) $\min(x,y)+\max(x,y)=x+y$。

∎

例 5.4（付値による gcd と lcm）

$a=252=2^2\cdot3^2\cdot7$, $b=105=3\cdot5\cdot7$ のとき、素数 $2,3,5,7$ での指数は $a:(2,2,0,1)$, $b:(0,1,1,1)$。min は $(0,1,0,1)$ で $\gcd=3\cdot7=21$、max は $(2,2,1,1)$ で $\mathrm{lcm}=4\cdot9\cdot5\cdot7=1260$。確かに $21\cdot1260=26460=252\cdot105$。

命題 5.5（約数の個数）✓

$n=\prod_{i=1}^kp_i^{e_i}$ ならば、$n$ の正の約数の個数は $\prod_{i=1}^k(e_i+1)$ である。

証明（命題 5.5）

命題 5.3(2) により、正の約数 $d$ は $0\le v_{p_i}(d)\le e_i$ と、その他の素数での指数が $0$ であること（$d\mid n$ なので $d$ の素因数は $p_i$ に限る）で決まり、定理 5.2 により指数の組と約数が一対一に対応する。各 $i$ の選び方は $e_i+1$ 通り。

∎

6. 中国剰余定理

6.1. 二つの法

整数 $a,b$ と正の整数 $n$ について、$n\mid a-b$ を $a\equiv b\pmod n$ と書きます（合同の基本は 合同式とフェルマーの小定理 で詳しく扱います）。ここでは定義だけを使います。

定理 6.1（中国剰余定理（一般形））✓

$m,n$ を正の整数、$g=\gcd(m,n)$ とし、$a,b$ を整数とする。連立合同式

$$x\equiv a\pmod m,\qquad x\equiv b\pmod n$$

が整数解をもつための必要十分条件は $g\mid a-b$ である。このとき、解の全体は $\mathrm{lcm}(m,n)$ を法とするただ一つの剰余類をなす。特に $g=1$ なら、任意の $a,b$ に対して解が存在し、$mn$ を法として一意である。

証明の方針：解は $x=a+(m\text{ の倍数})$ の形で探します。$x\equiv a\pmod m$ はこれで自動的に満たされるので、残る条件 $x\equiv b\pmod n$ を満たすよう倍数の部分を調整します。ここで $g=um+vn$ という式が、その調整に使えます。なお、解の全体が一つの剰余類（$\mathrm{lcm}(m,n)$ で割った余りが等しい整数の集まり）になることも示します。

証明（定理 6.1）

必要性。解 $x$ があれば $m\mid x-a$, $n\mid x-b$ で、$g\mid m$, $g\mid n$ だから $g\mid x-a$, $g\mid x-b$。差をとって $g\mid a-b$。

十分性。$g\mid b-a$ とし、$b-a=gk$ と書く。ベズーの等式 $g=um+vn$ をとり、$x=a+m\,u\,k$ とおく。$x\equiv a\pmod m$ は明らか。さらに

$$x-b=(a-b)+muk=-gk+muk=k(mu-g)=-k\,vn$$

で、$n$ の倍数。よって $x\equiv b\pmod n$。

一意性。$x,x'$ を二つの解とすると $m\mid x-x'$ かつ $n\mid x-x'$ なので、命題 2.4 により $\mathrm{lcm}(m,n)\mid x-x'$。逆に $x$ が解で $x'\equiv x\pmod{\mathrm{lcm}(m,n)}$ なら $x'$ も解。

∎

例 6.2（法が互いに素でない場合）

$x\equiv2\pmod{12}$, $x\equiv8\pmod{18}$。$\gcd(12,18)=6$ で $8-2=6$ は $6$ で割り切れるので解がある。$\mathrm{lcm}=36$。$x\equiv2\pmod{12}$ の候補 $2,14,26$ のうち、$18$ で割った余りが $8$ なのは $x=26$ ($26=18+8$)。解は $x\equiv26\pmod{36}$。一方 $x\equiv1\pmod{12}$, $x\equiv2\pmod{18}$ は $\gcd=6\nmid1$ なので解がない：$x$ は偶数であるはずなのに $x\equiv1\pmod{12}$ は奇数を要求する。

6.2. 多数の法と構成

系 6.3（互いに素な法の連立合同式）✓

$m_1,\ldots,m_k$ を、どの二つも互いに素な正の整数、$M=m_1\cdots m_k$ とする。任意の整数 $a_1,\ldots,a_k$ に対して、連立合同式 $x\equiv a_i\pmod{m_i}$（$i=1,\ldots,k$）は $M$ を法としてただ一つの解をもつ。解は

$$x\equiv\sum_{i=1}^ka_i\,M_i\,y_i\pmod M,\qquad M_i=\frac{M}{m_i},\quad M_iy_i\equiv1\pmod{m_i}$$

で与えられる。

証明（系 6.3）

$\gcd(M_i,m_i)=1$ である：素数 $p$ が $m_i$ と $M_i=\prod_{j\ne i}m_j$ を割り切るとすると、ユークリッドの補題によりある $m_j$ ($j\ne i$) を割り切り、$\gcd(m_i,m_j)=1$ に反する。したがってベズーの等式 $1=M_ix+m_iz$ から $y_i=x$ が存在する。$x_0=\sum_ia_iM_iy_i$ とおくと、$j\ne i$ なら $m_j\mid M_i$ なので $a_iM_iy_i\equiv0\pmod{m_j}$、よって $x_0\equiv a_jM_jy_j\equiv a_j\pmod{m_j}$。解の存在が示せた。一意性：二つの解の差はすべての $m_i$ で割り切れ、互いに素な数の公倍数なので、命題 2.4 を繰り返して $M$ で割り切れる（互いに素なら $\mathrm{lcm}$ は積）。

∎

例 6.4（孫子算経の問題）

「$3$ で割ると $2$ 余り、$5$ で割ると $3$ 余り、$7$ で割ると $2$ 余る数は何か」($M=105$)。$M_1=35$, $M_2=21$, $M_3=15$。$35y_1\equiv1\ (3)$ から $y_1=2$（$70=69+1$）、$21y_2\equiv1\ (5)$ から $y_2=1$、$15y_3\equiv1\ (7)$ から $y_3=1$。$x\equiv2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1=140+63+30=233\equiv233-210=23\pmod{105}$。検算：$23=3\cdot7+2=5\cdot4+3=7\cdot3+2$ ✓。

6.3. 分解の道具として

中国剰余定理の最も重要な使い方は、「法を互いに素な因子に分けて別々に解き、あとで貼り合わせる」ことです。

系 6.5（剰余の分解）✓

$m,n$ を互いに素な正の整数とする。写像

$$\Theta:\{0,1,\ldots,mn-1\}\longrightarrow\{0,\ldots,m-1\}\times\{0,\ldots,n-1\},\quad x\longmapsto(x\bmod m,\ x\bmod n)$$

は全単射である。さらに $\Theta(x+y)=\Theta(x)\oplus\Theta(y)$, $\Theta(xy)=\Theta(x)\odot\Theta(y)$（成分ごとに $m,n$ を法とする和・積）が成り立つ。

証明（系 6.5）

全射性は 定理 6.1 の存在（$g=1$）、単射性は一意性（二つの $x$ が同じ像をもてば $mn$ を法として合同で、範囲が $mn$ 個の連続する整数なので等しい）。和と積についての性質は、剰余を取る操作が和と積と両立すること（$a\equiv a',b\equiv b'$ ならば $a+b\equiv a'+b'$, $ab\equiv a'b'$）から従う。

∎

定理の中の $\oplus$, $\odot$ は、第 1 成分は $m$ を法として、第 2 成分は $n$ を法として、それぞれ足す・掛ける操作を表します。つまり、$mn$ を法とする計算は、$m$ を法とする計算と $n$ を法とする計算に分けて行えます。

例えば $m=3$, $n=5$ のとき、$0$ から $14$ までの 15 個の数は、$3$ で割った余りと $5$ で割った余りの組によって、次の表の 15 個の升目に重なりなくちょうど一つずつ入ります。

m = 3, n = 5 のとき、0 から 14 の各数を (3 で割った余り, 5 で割った余り) の升目に置いた表。15 個の数が 15 個の升目を過不足なく埋める。

これを環の言葉で述べると、$\mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}$（環同型）です（定理 4.8［合同式とフェルマーの小定理］ と 演習 8.2［イデアルと剰余環］ も参照）。

命題 6.6（合同方程式の解の個数の乗法性）✓

$f$ を整数係数の多項式、$m,n$ を互いに素な正の整数とし、$N(k)$ を合同方程式 $f(x)\equiv0\pmod k$ の $\{0,\ldots,k-1\}$ における解の個数とする。このとき $N(mn)=N(m)N(n)$。

証明（命題 6.6）

$f(x)\equiv0\pmod{mn}$ は、$m\mid f(x)$ かつ $n\mid f(x)$（互いに素なので 命題 2.4 より同値）。$f$ の整数係数性から $f(x)\bmod m$ は $x\bmod m$ だけで決まる。系 6.5 により、$x$ と $(x\bmod m,x\bmod n)$ は一対一に対応し、$x$ が解であることは $x\bmod m$ が $\bmod\ m$ の解かつ $x\bmod n$ が $\bmod\ n$ の解であることと同値。解の個数は $N(m)\cdot N(n)$。

∎

例 6.7（x² ≡ 1 (mod 15)）

$N(3)=2$（$x\equiv\pm1$）、$N(5)=2$（$x\equiv\pm1$）なので $N(15)=4$。四通りの組 $(x\bmod3,x\bmod5)=(\pm1,\pm1)$ を貼り合わせて、$x=1,4,11,14$。確かめると $4^2=16$, $11^2=121=8\cdot15+1$, $14^2=196=13\cdot15+1$。素数でない法では、$x^2\equiv1$ の解が $\pm1$ だけとは限りません。

7. オイラー関数

定義 7.1（オイラー関数）↗

正の整数 $n$ に対し、$\varphi(n)=\#\{\,k\in\{1,\ldots,n\}\mid\gcd(k,n)=1\,\}$ をオイラー関数という。

$\varphi(1)=1$, $\varphi(p)=p-1$（素数 $p$）, $\varphi(12)=4$（$1,5,7,11$）。この関数は $\mathbb{Z}/n\mathbb{Z}$ の可逆元の個数でもあります（定義 4.6［合同式とフェルマーの小定理］）。

補題 7.2（積と互いに素）✓

$m,n$ を正の整数、$x$ を整数とすると、$\gcd(x,mn)=1\iff\gcd(x,m)=1$ かつ $\gcd(x,n)=1$。また $\gcd(x,n)=\gcd(x\bmod n,\,n)$ である。

証明（補題 7.2）

$\gcd(x,mn)>1$ とすると、素数 $p$ が $x$ と $mn$ を割り切る。ユークリッドの補題で $p\mid m$ または $p\mid n$ となり、$\gcd(x,m)>1$ または $\gcd(x,n)>1$。逆は明らか。後半は、$x=nq+r$ のとき $x$ と $n$ の公約数の集合が $r$ と $n$ の公約数の集合に一致すること（定理 3.2 の証明の最初の段落）による。

∎

定理 7.3（オイラー関数の乗法性と公式）✓

1. $m,n$ が互いに素ならば $\varphi(mn)=\varphi(m)\varphi(n)$。
2. 素数 $p$ と $k\ge1$ について $\varphi(p^k)=p^k-p^{k-1}$。
3. $n=\prod_{i=1}^kp_i^{e_i}$（$p_i$ は相異なる素数、$e_i\ge1$）ならば $\varphi(n)=\prod_{i=1}^kp_i^{e_i-1}(p_i-1)=n\prod_{i=1}^k\Bigl(1-\dfrac1{p_i}\Bigr)$。

証明（定理 7.3）

(1) 系 6.5 の $\Theta$ を考える。$x\in\{0,\ldots,mn-1\}$ について、補題 7.2 により $\gcd(x,mn)=1\iff\gcd(x\bmod m,m)=1$ かつ $\gcd(x\bmod n,n)=1$。つまり $\Theta$ は $\gcd(x,mn)=1$ を満たす $x$ の集合を、$\{u\mid\gcd(u,m)=1\}\times\{v\mid\gcd(v,n)=1\}$ へ全単射で写す（$\{0,\ldots,mn-1\}$ と $\{1,\ldots,mn\}$ は $0\leftrightarrow mn$ を除いて同じで、$\gcd(0,mn)=mn>1$, $\gcd(mn,mn)>1$ なので数え方に影響しない。$m=n=1$ のときは自明）。個数を比べて $\varphi(mn)=\varphi(m)\varphi(n)$。 (2) $1,\ldots,p^k$ のうち $p^k$ と互いに素でないものは $p$ の倍数で、その個数は $p^{k-1}$。 (3) (1)(2) と 定理 5.2 から従う（互いに素な素数べきへの分解を使い、$k$ に関する帰納法）。$p_i^{e_i-1}(p_i-1)=p_i^{e_i}(1-1/p_i)$。

∎

例 7.4（φ の計算）

$\varphi(360)$：$360=2^3\cdot3^2\cdot5$ なので $360\cdot\frac12\cdot\frac23\cdot\frac45=96$。$\varphi(1001)$：$1001=7\cdot11\cdot13$ で $6\cdot10\cdot12=720$。

定理 7.5（約数についての和）✓

正の整数 $n$ について $\displaystyle\sum_{d\mid n}\varphi(d)=n$（和は $n$ の正の約数 $d$ 全体）。

証明（定理 7.5）

$\{1,\ldots,n\}$ を、$\gcd(k,n)$ の値で分類する。$\gcd(k,n)$ は $n$ の約数だから、$d\mid n$ ごとに $S_d=\{k\in\{1,\ldots,n\}\mid\gcd(k,n)=n/d\}$ とおくと、$S_d$ ($d\mid n$) は $\{1,\ldots,n\}$ の分割になる。$k\in S_d$ は $k=(n/d)j$ ($1\le j\le d$) と書け、$\gcd(k,n)=(n/d)\gcd(j,d)$ だから、条件 $\gcd(k,n)=n/d$ は $\gcd(j,d)=1$ と同値。よって $k\mapsto j$ は $S_d$ から $\{j\in\{1,\ldots,d\}\mid\gcd(j,d)=1\}$ への全単射で、$|S_d|=\varphi(d)$。両辺の個数を比べて $n=\sum_{d\mid n}|S_d|=\sum_{d\mid n}\varphi(d)$。

∎

例 7.6（n = 12 での確認）

$12$ の約数は $1,2,3,4,6,12$ で $\varphi=1,1,2,2,2,4$。和は $12$ ✓。$S_{12}=\{1,5,7,11\}$（$\gcd=1$）、$S_6=\{2,10\}$（$\gcd=2$）、$S_4=\{3,9\}$、$S_3=\{4,8\}$、$S_2=\{6\}$、$S_1=\{12\}$。

注意 7.7（オイラーの定理への接続）

$\gcd(a,n)=1$ なら $a^{\varphi(n)}\equiv1\pmod n$（定理 5.3［合同式とフェルマーの小定理］）。この定理の証明は、$\mathbb{Z}/n\mathbb{Z}$ の可逆元が $\varphi(n)$ 個あることとラグランジュの定理に基づいています。定理 7.5 は次々の記事で、位数 $d$ の元の個数を数えるのに使われます。

8. 演習

演習 8.1易

$\gcd(1071,462)$ を互除法で求め、$1071x+462y=\gcd(1071,462)$ の整数解 $(x,y)$ を一組求めよ。

解答

$1071=2\cdot462+147$, $462=3\cdot147+21$, $147=7\cdot21+0$。$\gcd=21$。逆にたどって $21=462-3\cdot147=462-3(1071-2\cdot462)=7\cdot462-3\cdot1071$。よって $(x,y)=(-3,7)$（確認：$-3213+3234=21$）。

演習 8.2標準

連立合同式 $x\equiv1\pmod 4$, $x\equiv2\pmod 9$, $x\equiv3\pmod{25}$ を解け（$\bmod\ 900$）。

解答

法 $4,9,25$ はどの二つも互いに素で $M=900$。$M_1=225$, $M_2=100$, $M_3=36$。$225y_1\equiv1\ (4)$：$225\equiv1$ なので $y_1=1$。$100y_2\equiv1\ (9)$：$100\equiv1$ なので $y_2=1$。$36y_3\equiv1\ (25)$：$36\equiv11$, $11\cdot16=176=7\cdot25+1$ なので $y_3=16$。$x\equiv1\cdot225\cdot1+2\cdot100\cdot1+3\cdot36\cdot16=225+200+1728=2153\equiv2153-1800=353\pmod{900}$。検算：$353=4\cdot88+1$, $353=9\cdot39+2$, $353=25\cdot14+3$ ✓。

演習 8.3標準

$\varphi(n)=12$ を満たす正の整数 $n$ をすべて求めよ。

解答

素数 $p\mid n$ について、$\varphi(n)$ の素因数分解表示の因子 $p^{e-1}(p-1)$ が $\varphi(n)=12$ を割る（定理 7.3 の積の各因子は正の整数）。よって $p-1\mid12$ から $p\in\{2,3,5,7,13\}$、$p^{e-1}\mid12$ から指数は $2^a$ ($a\le3$)、$3^b$ ($b\le2$)、$5,7,13$ は $1$ 乗まで。互いに素な部分の $\varphi$ の積が $12$ になる組を探す。値は $\varphi(2^a)\in\{1,1,2,4\}$（$a=0,1,2,3$）、$\varphi(3^b)\in\{1,2,6\}$（$b=0,1,2$）、$\varphi(5)=4$、$\varphi(7)=6$、$\varphi(13)=12$。

• $13\mid n$ のとき：他の部分の $\varphi$ の積は $1$。$a\in\{0,1\}$, $b=0$ で $n=13,26$。
• $7\mid n$, $13\nmid n$ のとき：他の部分の積は $2$。$5\mid n$ なら因子 $4$ が入って不可。$\varphi(2^a)\varphi(3^b)=2$ を解くと $(\varphi(2^a),\varphi(3^b))=(1,2)$ で $a\in\{0,1\}$, $b=1$、または $(2,1)$ で $a=2$, $b=0$。$n=7\cdot3=21$, $7\cdot6=42$, $7\cdot4=28$。
• $7,13\nmid n$ のとき：$5\mid n$ なら残りの積は $3$ だが、$\{1,2,4\}\times\{1,2,6\}$ の積に $3$ はない。$5\nmid n$ なら $\varphi(2^a)\varphi(3^b)=12$ で、解は $(2,6)$ すなわち $a=2$, $b=2$ のみ。$n=36$。

答：$n=13,21,26,28,36,42$。

演習 8.4標準

正の整数 $a,b,c$ について $\gcd(a,\mathrm{lcm}(b,c))=\mathrm{lcm}(\gcd(a,b),\gcd(a,c))$ を、付値を使って示せ。

解答

各素数 $p$ で $x=v_p(a)$, $y=v_p(b)$, $z=v_p(c)$ とおく。命題 5.3(3) より左辺の指数は $\min(x,\max(y,z))$、右辺の指数は $\max(\min(x,y),\min(x,z))$。$y\le z$ の場合は $\min(x,z)$ と $\max(\min(x,y),\min(x,z))=\min(x,z)$（$\min(x,y)\le\min(x,z)$ なので）で一致し、$y>z$ の場合も対称。すべての $p$ で指数が一致するので、定理 5.2 の一意性により両辺は等しい。

参考文献

• 高木貞治『初等整数論講義』第 2 版、共立出版、1971 — 第 1 章（整除、最大公約数）、第 2 章（合同式、中国剰余定理）。
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — 第 2 章（基本定理）、第 5 章（オイラー関数）。
• K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer GTM 84, 1990 — 第 1 章、第 2 章。
• D. E. Knuth, The Art of Computer Programming, Vol. 2, 3rd ed., Addison-Wesley, 1997 — 4.5.2 節（ユークリッドの互除法の解析。ラメの定理）。
• G. Lamé, “Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers”, Comptes Rendus de l’Académie des Sciences 19 (1844), 867–870.