整数の性質 I：約数・互除法・n 進法・連分数

0. この記事の要点

「6 は、自分以外の約数 1, 2, 3 を足すとちょうど 6 になる」「3 円玉と 5 円玉だけでは、7 円だけはどうしても払えない」。こうした整数の身近な不思議を、なぜそうなるのかまで言葉で確かめるのがこの記事です。読み終えると、約数の足し算、硬貨で払えない金額、$n$ 進法の書き換え、階乗に含まれる素数の個数などを、計算だけでなく理由つきで説明できるようになります。以下の箇条書きは全体の見取り図なので、知らない言葉があっても、先に進んで各節で出会ったときに戻って読めば十分です。

• 高校の整数問題で使う道具（互除法・素因数分解の一意性・不定方程式）は、大学の初等整数論の記事で証明されています。この記事はそれらを <Ref> で指し、高校の整数の問題が実際に使う形（約数の総和・完全数・硬貨の問題・n 進法・階乗の素因数・連分数・Farey 数列・単位分数）を証明します。
• 約数の総和 $\sigma(n)=\prod_p\dfrac{p^{e+1}-1}{p-1}$ は、素因数分解の指数のベクトルを数えるだけで出ます。そこから、偶数の完全数は $2^{p-1}(2^p-1)$（$2^p-1$ が素数）の形に限るという Euclid–Euler の定理が従います。
• 互いに素な $a,b$ について、$ax+by$（$x,y\ge0$）の形に書けない最大の整数は $ab-a-b$ です。
• $n$ 進法の表示は、除法の原理を繰り返すだけで存在し、一意です。$n!$ の素因数 $p$ の個数は $\sum_{i\ge1}\lfloor n/p^i\rfloor$（Legendre の公式）です。
• 有理数は有限連分数に一意に書け、その手順は互除法そのものです。$\sqrt2$ の連分数からは $p^2-2q^2=\pm1$ を満たす整数の列が出ます。
• Farey 数列の隣り合う分数は $bc-ad=1$ を満たし、Ford の円は隣り合う分数のところで接します。

この記事で使う事前知識

• 数学的帰納法: 「最初の場合が成り立ち、ある場合が成り立てば次の場合も成り立つ」ことから、すべての場合を示す方法。→ 証明の技術：数学的帰納法と背理法
• 背理法: 示したいことの否定を仮定して矛盾を出す方法。→ 証明の技術：数学的帰納法と背理法
• 約数・倍数・素因数分解: $a$ が $b$ で割り切れるとき $b$ を $a$ の約数といい、正の整数は素数の積に（順序を除いて）ただ 1 通りに書けます。
• 互除法: 割り算の余りを使って、2 つの整数の最大公約数を求める手順。
• 合同式: $a$ と $b$ を $m$ で割った余りが等しいことを $a\equiv b\pmod m$ と書く記法。
• 床関数: 実数 $t$ 以下の最大の整数を $\lfloor t\rfloor$ と書く記法。

1. 動機

高校の整数の問題は、数学の他の分野と比べて道具が少ないのに、解くたびに発想が要ります。それは、道具（割り算・素因数分解・余り）の正確な形があいまいなまま、問題ごとにその場しのぎで使っているからです。

この記事では、「割り切れる」「素因数の指数」「余り」を厳密に使って、よく出る結果を最初から組み立てます。互除法・Bézout の等式・素因数分解の一意性はすでに証明されているので、これらは再証明せずに使います。使った箇所を毎回 <Ref> で示します。

2. 約数と約数の総和

記号: 正の整数 $n$ の素数 $p$ についての付値 $v_p(n)$（$p^e\mid n$ となる最大の $e\ge0$。$n$ を割り切る $p$ の個数のこと）は 定義 5.1［整除と素因数分解］。$n=\prod_pp^{v_p(n)}$（定理 5.2［整除と素因数分解］）。

定義 2.1（約数の総和）↗

正の整数 $n$ の正の約数全体の和を $\sigma(n)$ と書く。$\sigma(n)=2n$ となる $n$ を完全数という。

命題 2.2（約数の総和の公式）✓

正の整数 $n=p_1^{e_1}\cdots p_k^{e_k}$（$p_i$ は相異なる素数、$e_i\ge1$）について

$$\sigma(n)=\prod_{i=1}^k\bigl(1+p_i+p_i^2+\cdots+p_i^{e_i}\bigr)=\prod_{i=1}^k\frac{p_i^{e_i+1}-1}{p_i-1}.$$

とくに、互いに素な $m,n$ について $\sigma(mn)=\sigma(m)\sigma(n)$（乗法性）である。

次の証明のねらいは、約数を 1 つずつ足す代わりに、素因数ごとの和を掛け合わせるだけで済むことを示すことです。たとえば $12=2^2\cdot3$ の約数は $1,2,4,3,6,12$ の 6 個で、和は $28$ です。一方 $(1+2+4)(1+3)=7\cdot4=28$ と一致します。右辺を展開すると、2 のべきと 3 のべきの組み合わせがちょうど 12 の約数 1 つずつに対応する、というのが証明の中身です。

証明（命題 2.2）

正の整数 $d$ について、$d\mid n$ であることと、すべての素数 $p$ で $v_p(d)\le v_p(n)$ であることは同値（命題 5.3［整除と素因数分解］ の 2.）。$d$ は指数の組 $(v_p(d))_p$ から $d=\prod p^{v_p(d)}$ と復元できる（定理 5.2［整除と素因数分解］）。したがって $n$ の正の約数と、組 $(a_1,\dots,a_k)$（$0\le a_i\le e_i$）は $d=\prod p_i^{a_i}$ によって 1 対 1 に対応する。ゆえに

$$\sigma(n)=\sum_{0\le a_i\le e_i}\prod_ip_i^{a_i}=\prod_{i=1}^k\Bigl(\sum_{a=0}^{e_i}p_i^a\Bigr)$$

（右辺を分配法則で展開したものが左辺）。$1+p+\cdots+p^e=\dfrac{p^{e+1}-1}{p-1}$ は、両辺に $p-1$ を掛けて隣り合う項が打ち消し合うことから分かる。乗法性は、$m,n$ が互いに素なら $m$ と $n$ に共通の素因数がなく、$mn$ の素因数分解が $m$ の分解と $n$ の分解の並べたものになって、上の積が $\sigma(m)\sigma(n)$ に分かれることから従う。

∎

例 2.3（360 の約数の総和）

$360=2^3\cdot3^2\cdot5$ なので $\sigma(360)=(1+2+4+8)(1+3+9)(1+5)=15\cdot13\cdot6=1170$。約数の個数 $(3+1)(2+1)(1+1)=24$ は 命題 5.5［整除と素因数分解］ と同じ数え方です。

命題 2.4（Mersenne 数が素数になる条件）✓

$n\ge2$ について $2^n-1$ が素数ならば、$n$ は素数である。

証明（命題 2.4）

$n=ab$（$a,b\ge2$）と書けたと仮定する。$x=2^a$ とおくと $x^b-1=(x-1)(x^{b-1}+x^{b-2}+\cdots+1)$（右辺を展開して打ち消し合う）。よって $2^a-1$ は $2^n-1$ の約数で、$1<2^a-1<2^n-1$（$a\ge2$、$b\ge2$）。$2^n-1$ は素数でないことになり、仮定に反する。

∎

定理 2.5（Euclid–Euler の定理（偶数の完全数））✓

偶数 $n$ が完全数であるための必要十分条件は、$n=2^{p-1}(2^p-1)$ と書け、$2^p-1$ が素数となる整数 $p\ge2$ が存在することである。

この定理は「この形の数は完全数である」（十分性）と「偶数の完全数はこの形に限る」（必要性）の 2 つを言っています。十分性は 命題 2.2 に当てはめる計算だけです。必要性は、偶数の完全数を $2^k$ と奇数 $m$ の積に分け、$\sigma(n)=2n$ という条件から $m$ の約数が $1$ と $m$ だけ（つまり $m$ が素数）に絞られる、という流れで進みます。たとえば $6=2\cdot3$ では $k=1$、$m=3$ です。

証明（定理 2.5）

(十分性) $M=2^p-1$ が素数であるとし、$n=2^{p-1}M$ とする。$M$ は奇数なので $2^{p-1}$ と互いに素で、命題 2.2 から $\sigma(n)=\sigma(2^{p-1})\sigma(M)=(2^p-1)(1+M)=M\cdot2^p=2n$。 (必要性) $n$ が偶数の完全数とし、$n=2^km$（$k\ge1$、$m$ は奇数）と書く。命題 2.2 より $\sigma(n)=(2^{k+1}-1)\sigma(m)$。これが $2n=2^{k+1}m$ に等しい。$2^{k+1}-1$ は $2^{k+1}$ と互いに素（連続する 2 つの整数 $2^{k+1}-1,2^{k+1}$ の共通因子は $1$ だけ）で、$2^{k+1}-1$ は $2^{k+1}m$ を割るから、補題 2.2［整除と素因数分解］ により $2^{k+1}-1\mid m$。$m=(2^{k+1}-1)c$（$c$ は正の整数）と書くと、$\sigma(m)=2^{k+1}c=m+c$。ところで $m$ の約数には $m$ 自身と $c$ がある。$c\ne m$（$2^{k+1}-1\ge3>1$）なので、これは相異なる約数で、$\sigma(m)\ge m+c$、さらに $1$ も約数で、$c=1$ でなければ $1\ne c$、$1\ne m$ より $\sigma(m)\ge m+c+1$ となって $\sigma(m)=m+c$ に反する。ゆえに $c=1$、$m=2^{k+1}-1$ で、$m$ の約数は $\sigma(m)=m+1$ から $1$ と $m$ だけ、すなわち $m$ は素数（$m\ge3$）。$p=k+1\ge2$ とおけば $n=2^{p-1}(2^p-1)$。

∎

例 2.6（完全数）

$p=2,3,5,7$ では $2^p-1=3,7,31,127$ がすべて素数で、$n=6,28,496,8128$ が完全数です（$28=1+2+4+7+14$）。$p=11$ では $2^{11}-1=2047=23\cdot89$ で素数でないので、$2^{10}\cdot2047$ は完全数ではありません。命題 2.4 は $p$ が素数であることを要請しますが、逆（$p$ が素数なら $2^p-1$ が素数）は $p=11$ で成り立ちません。奇数の完全数が存在するかどうかは未解決です。

3. 1 次不定方程式と硬貨の問題

$a,b$ を正の整数で互いに素とします。$ax+by=c$ の整数解の存在と一般解は、すでに 命題 4.1［整除と素因数分解］（$\gcd(a,b)\mid c$ が条件で、解は $(x_0+bk,\ y_0-ak)$ の形）と 定理 2.2［合同式とフェルマーの小定理］ で証明されています。高校の問題で本当に問われるのは、負でない整数解の存在と個数です。

補題 3.1（床関数の入れ子）✓

実数 $x$ と正の整数 $b$ について $\bigl\lfloor\lfloor x\rfloor/b\bigr\rfloor=\lfloor x/b\rfloor$ である。ここで $\lfloor t\rfloor$ は $t$ 以下の最大の整数。

証明（補題 3.1）

$L=\lfloor x\rfloor$、$q=\lfloor L/b\rfloor$ とおくと $qb\le L\le x<L+1\le qb+b$（$L+1\le(q+1)b$ は $L<(q+1)b$ から）。$b$ で割って $q\le x/b<q+1$、すなわち $\lfloor x/b\rfloor=q$。

∎

定理 3.2（非負整数解の個数）✓

$a,b$ を互いに素な正の整数、$c\ge0$ を整数とする。方程式 $ax+by=c$ の非負整数解 $(x,y)$（$x\ge0$、$y\ge0$）の個数は $\lfloor c/(ab)\rfloor$ または $\lfloor c/(ab)\rfloor+1$ である。

証明では、解になれる $x$ が $b$ ごとに 1 つずつ現れること（$b$ で割った余りが決まっているため）と、$y\ge0$ から $x$ の上限が決まることを使い、「$0$ から上限までの整数のうち、決まった余りのものを数える」問題に言い換えます。長さ $b$ の区間にはどの余りもちょうど 1 回現れるので、区間をいくつ並べられるかを数えれば個数が分かります。

証明（定理 3.2）

まず $x\ge0$ に対し、$y=(c-ax)/b$ が整数となるのは $ax\equiv c\pmod b$ のときで、$a$ は $b$ と互いに素なので 定理 2.2［合同式とフェルマーの小定理］ から $ax\equiv c$ を満たす $x$ は法 $b$ でただ 1 つの剰余類 $x\equiv x_0\pmod b$（$0\le x_0<b$）をなす（$ua+vb=1$ をとると $x\equiv uc$）。$y\ge0$ は $ax\le c$、すなわち $0\le x\le L=\lfloor c/a\rfloor$ と同値である。ゆえに解の個数は、$[0,L]$ の整数で $x_0$ と法 $b$ で合同なものの個数 $N$。$q=\lfloor L/b\rfloor$、$L=qb+s$（$0\le s<b$）と書く。$[0,qb-1]$ は連続する $qb$ 個の整数で、各剰余類をちょうど $q$ 個含む。残りの $[qb,qb+s]$ は $s+1\le b$ 個の連続する整数で、法 $b$ の相異なる剰余類にあるから、$x_0$ の剰余類の元を高々 1 個含む。よって $N=q$ または $q+1$。補題 3.1 より $q=\lfloor c/(ab)\rfloor$。

∎

定理 3.3（2 種類の硬貨で払えない最大の金額）✓

$a,b$ を互いに素な正の整数とする。$ax+by$（$x,y$ は $0$ 以上の整数）の形に表せない整数のうち最大のものは $ab-a-b$ である（$a=1$ のときは、負の整数がすべて表せず、最大の $-1$ が $ab-a-b$ に一致する）。

証明（定理 3.3）

$c>ab-a-b$ が表せることを示す。$a$ は $b$ と互いに素なので、定理 2.2［合同式とフェルマーの小定理］ により $ax_0\equiv c\pmod b$ となる $x_0\in\{0,1,\dots,b-1\}$ がある。$y_0=(c-ax_0)/b$ は整数で、$c-ax_0\ge(ab-a-b+1)-a(b-1)=1-b>-b$ だから $y_0>-1$、すなわち $y_0\ge0$。よって $c=ax_0+by_0$ と表せる。 $c=ab-a-b$ が表せないことを示す。$ab-a-b=ax+by$（$x,y\ge0$）なら $a(x+1)+b(y+1)=ab$。$b\mid a(x+1)$ で $\gcd(a,b)=1$ なので、補題 2.2［整除と素因数分解］ から $b\mid x+1$、$x+1\ge b$。同様に $a\mid y+1$、$y+1\ge a$。すると $a(x+1)+b(y+1)\ge ab+ab>ab$ となり矛盾する。

∎

例 3.4（3 円と 5 円の硬貨）

$a=3$、$b=5$ のとき、$3x+5y$ で表せない最大の整数は $15-3-5=7$。実際、$0,3,5,6,8,9,10,\dots$ が表せて、$1,2,4,7$ が表せません（8 以上はすべて表せる）。非負解の個数は 定理 3.2 によると $3x+5y=40$ で $\lfloor40/15\rfloor=2$ または $3$ で、実際 $(x,y)=(0,8),(5,5),(10,2)$ の 3 個です。

4. n 進法

定理 4.1（n 進表示の存在と一意性）✓

$b\ge2$ を整数とする。正の整数 $N$ は

$$N=d_kb^k+d_{k-1}b^{k-1}+\cdots+d_1b+d_0,\qquad0\le d_i\le b-1,\quad d_k\ne0$$

の形に、ただ 1 通りに書ける。

証明（定理 4.1）

(存在) $N$ についての完全帰納法（定理 4.3［証明の技術］）。$N<b$ なら $k=0$、$d_0=N$。$N\ge b$ とする。定理 2.1［合同式とフェルマーの小定理］ で $N=qb+r$（$0\le r<b$）。$q\ge1$ で $q<N$ なので帰納法の仮定から $q=\sum_{i=0}^{k-1}d_{i+1}b^i$（最高位の係数は $0$ でない）と書け、$N=\sum_{i=0}^{k-1}d_{i+1}b^{i+1}+r$。 (一意性) $N$ の 2 通りの表示があるとする。$d_kb^k\ge b^k$ なので、$N<b$ なら $k\ge1$ の表示はありえず（$N\ge b^k\ge b$ となってしまう）、$N<b$ のときの表示は $k=0$、$d_0=N$ のただ 1 通り。$N\ge b$ とする。このとき 2 通りとも $k\ge1$ で、$N\equiv d_0\pmod b$、$0\le d_0<b$ なので、$d_0$ は $N$ を $b$ で割った余りであり（定理 2.1［合同式とフェルマーの小定理］ の一意性）、両方の表示で一致する。残りの部分 $(N-d_0)/b=d_kb^{k-1}+\cdots+d_1$ は最高位の係数が $0$ でない正の整数 $(N-d_0)/b$ の表示で、$N$ より小さいから、完全帰納法の仮定により 2 通りの表示で一致する。

∎

例 4.2（進法の変換と筆算の繰り上がり）

$2024$ を 7 進法で表す。$2024=7\cdot289+1$、$289=7\cdot41+2$、$41=7\cdot5+6$、$5=7\cdot0+5$ で、下から順に $1,2,6,5$ が出るので $2024=5621_{(7)}$（$5\cdot343+6\cdot49+2\cdot7+1=2024$）。この「割って余りを集める」手順が 定理 4.1 の存在の証明そのものです。10 進法の筆算の繰り上がりは、桁ごとの和が $b=10$ 以上になったとき $d=qb+r$ と書き直して $q$ を上の桁に足す操作で、これも除法の原理です。

5. 倍数の個数と Legendre の公式

命題 5.1（倍数の個数）✓

正の整数 $n,d$ について、$1,2,\dots,n$ のうち $d$ の倍数の個数は $\lfloor n/d\rfloor$ である。

証明（命題 5.1）

$d$ の倍数は $d,2d,\dots$ で、$jd\le n$ は $j\le n/d$、すなわち $j\le\lfloor n/d\rfloor$ と同値（$j$ は整数）。

∎

定理 5.2（Legendre の公式）✓

素数 $p$ と正の整数 $n$ について

$$v_p(n!)=\sum_{i=1}^\infty\Bigl\lfloor\frac n{p^i}\Bigr\rfloor$$

である（$p^i>n$ の項は $0$ なので実際は有限和）。

証明（定理 5.2）

命題 5.3［整除と素因数分解］ の 1. を繰り返して $v_p(n!)=\sum_{m=1}^nv_p(m)$。各 $m$ について $v_p(m)=\#\{i\ge1:p^i\mid m\}$（$p^i\mid m$ は $i\le v_p(m)$ と同値）なので、和の順序を入れ替えて $v_p(n!)=\sum_{i\ge1}\#\{m\le n:p^i\mid m\}=\sum_{i\ge1}\lfloor n/p^i\rfloor$（命題 5.1）。

∎

例 5.3（100! の末尾の 0）

末尾に並ぶ 0 の個数は $\min(v_2(100!),v_5(100!))$ です。$v_5(100!)=\lfloor100/5\rfloor+\lfloor100/25\rfloor=20+4=24$、$v_2(100!)=50+25+12+6+3+1=97$ なので、$0$ は $24$ 個。

6. 連分数

$a_0$ を整数、$a_1,\dots,a_n$ を正の整数とし、

$$[a_0;a_1,\dots,a_n]=a_0+\cfrac{1}{a_1+\cfrac{1}{\ddots+\cfrac1{a_n}}}$$

と定めます（正確には $[a_0]=a_0$、$[a_0;a_1,\dots,a_n]=a_0+\dfrac1{[a_1;a_2,\dots,a_n]}$ と再帰的に定義）。これを有限連分数といいます。

補題 6.1（連分数の末尾の大きさ）✓

$n\ge1$ で $a_n\ge2$ ならば、$y=[a_1;a_2,\dots,a_n]$ は $y>1$ を満たす。

証明（補題 6.1）

$n=1$ なら $y=a_1\ge2$。$n\ge2$ なら $y=a_1+1/[a_2;\dots,a_n]$ で、$[a_2;\dots,a_n]>0$（正の整数と正の数 $1/\cdot$ の和なので帰納的に正）だから $y>a_1\ge1$。

∎

定理 6.2（有理数と有限連分数）✓

1. 有限連分数は有理数である。
2. 任意の有理数 $x$ は $x=[a_0;a_1,\dots,a_n]$（$a_0\in\mathbb{Z}$、$a_i\ge1$、$n\ge1$ なら $a_n\ge2$）の形に、ただ 1 通りに書ける。$x=u/v$（$u\ge0$、$v\ge1$）のとき、$a_i$ は $u$ と $v$ の互除法の商（定義 3.1［整除と素因数分解］）に一致する。

証明（定理 6.2）

1. $n$ についての帰納法。$[a_0]$ は整数。$[a_0;a_1,\dots,a_n]=a_0+1/y$、$y=[a_1;\dots,a_n]$ は帰納法の仮定により有理数で、正なので $1/y$ も有理数。
2. (存在) $x_0=x=u_0/v_0$（$v_0\ge1$）から出発し、$a_i=\lfloor x_i\rfloor$ とする。$x_i$ が整数でなければ $x_i-a_i=r_i/v_i$（$0<r_i<v_i$）で、$x_{i+1}=1/(x_i-a_i)=v_i/r_i$ と定める（分母は $v_{i+1}=r_i<v_i$）。分母は正の整数の真に減少する列なので有限回で $x_n$ が整数になり、手順は止まる。$x_i=a_i+1/x_{i+1}$ をたどって $x=[a_0;a_1,\dots,a_n]$。この手順は $(u_i,v_i)\to(v_i,r_i)$ の互除法で、$a_i$ はその商。$n\ge1$ では $x_n=1/(x_{n-1}-a_{n-1})>1$ が整数なので $a_n\ge2$。 (一意性) $x=[a_0;\dots,a_n]=[b_0;\dots,b_m]$ を条件を満たす 2 つの表示とする。$n\ge1$ なら、補題 6.1 より $0<x-a_0=1/y<1$ なので $a_0=\lfloor x\rfloor$。$n=0$ なら $x=a_0$ は整数で、$m\ge1$ だと $x-b_0\in(0,1)$ となり整数でないので $m=0$。$n,m\ge1$ では $a_0=b_0=\lfloor x\rfloor$ で、$[a_1;\dots,a_n]=1/(x-a_0)=[b_1;\dots,b_m]$。長さが 1 つ短い表示に帰納法の仮定を使って $a_i=b_i$、$n=m$。

∎

例 6.3（47/17 の連分数）

$47=2\cdot17+13$、$17=1\cdot13+4$、$13=3\cdot4+1$、$4=4\cdot1$ なので、商は $2,1,3,4$ で $\dfrac{47}{17}=[2;1,3,4]$。実際 $3+\frac14=\frac{13}4$、$1+\frac4{13}=\frac{17}{13}$、$2+\frac{13}{17}=\frac{47}{17}$。

無理数の連分数は終わらず無限に続きます。$\sqrt2$ の場合を見ます。

命題 6.4（√2 の連分数と近似分数）✓

$t_0=1$、$t_{n+1}=1+\dfrac1{1+t_n}$ とおくと、$t_n=[1;\underbrace{2,\dots,2}_{n}]$ であり、$t_n=p_n/q_n$ と書くと整数列 $p_n,q_n$ は

$$p_{n+1}=p_n+2q_n,\quad q_{n+1}=p_n+q_n,\quad(p_0,q_0)=(1,1)$$

で与えられ、$p_n^2-2q_n^2=(-1)^{n+1}$ を満たす。さらに $\bigl|t_n-\sqrt2\bigr|<\dfrac1{2q_n^2}$ である。

証明（命題 6.4）

$t_n=[1;2^n]$（$n$ 個の 2）と書く。$[2;2^n]=2+z=1+(1+z)$ より $[2;2^n]=1+[1;2^n]=1+t_n$（$z$ は 2 以降の連分数部分）なので、$t_{n+1}=[1;2^{n+1}]=1+\dfrac1{[2;2^n]}=1+\dfrac1{1+t_n}$。$t_n=p_n/q_n$ とすると $t_{n+1}=1+\dfrac{q_n}{p_n+q_n}=\dfrac{p_n+2q_n}{p_n+q_n}$。ここで $(p_n,q_n)$ を漸化式で定める。 $(p_{n+1})^2-2(q_{n+1})^2=(p_n+2q_n)^2-2(p_n+q_n)^2=-p_n^2+2q_n^2=-(p_n^2-2q_n^2)$。$p_0^2-2q_0^2=-1$ から帰納的に $(-1)^{n+1}$。 $p_n,q_n\ge1$ なので $p_n/q_n\ge1$。$\sqrt2$ の存在は 定理 5.6［数とは何か］。$|p_n/q_n-\sqrt2|=\dfrac{|p_n^2-2q_n^2|}{q_n^2(p_n/q_n+\sqrt2)}=\dfrac1{q_n^2(p_n/q_n+\sqrt2)}<\dfrac1{2q_n^2}$（$p_n/q_n+\sqrt2>2$）。

∎

近似分数は $1,\ \frac32,\ \frac75,\ \frac{17}{12},\ \frac{41}{29},\dots$ です。$p^2-2q^2=\pm1$ を満たす整数の組が無限に続くことは、次の記事の Pell 方程式の入口になります。

7. Farey 数列と Ford の円

定義 7.1（Farey 数列）↗

正の整数 $n$ に対し、$0\le a\le b\le n$、$\gcd(a,b)=1$ の分数 $a/b$（$0=0/1$、$1=1/1$ を含む）を小さい順に並べた数列を Farey 数列 $F_n$ という。

$F_5$ は $\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34,\frac45,\frac11$ です。隣り合う分数 $\frac13,\frac25$ では $3\cdot2-1\cdot5=1$、$\frac14,\frac13$ では $4\cdot1-1\cdot3=1$ です。

定理 7.2（Farey 数列の隣り合う分数）✓

$F_n$ の隣り合う 2 項 $\dfrac ab<\dfrac cd$ について

$$bc-ad=1,\qquad b+d>n$$

が成り立つ。

証明の方針は、分数 $\dfrac ab$ の「すぐ右隣」になるはずの分数 $\dfrac xy$ を、$bx-ay=1$ を満たすものとして先に作り、それが本当に隣であることを確かめる、というものです。$bx-ay=1$ の解は $(x,y)$ を一定の幅ずつ平行移動した無数の組になるので、その中から分母 $y$ が $n-b<y\le n$ に入るものを選ぶ、というのが「範囲に収める」操作の意味です。

証明（定理 7.2）

$\gcd(a,b)=1$ なので 定理 2.2［合同式とフェルマーの小定理］ により $bx'-ay'=1$ となる整数 $x',y'$ がある。$(x,y)=(x'+ka,\ y'+kb)$ も同じ式 $bx-ay=1$ を満たすから、$k$ を選んで $n-b<y\le n$ にできる（$y$ は法 $b$ で決まった剰余類を動き、長さ $b$ の区間にはその剰余類の整数がちょうど 1 つある）。$b\le n$ なので $y\ge1$。$bx-ay=1$ より $\gcd(x,y)=1$、$\dfrac xy-\dfrac ab=\dfrac1{by}>0$。 $\dfrac xy\in F_n$ である：$\dfrac ab<\dfrac cd\le1$ なので $a\le b-1$、$\dfrac xy=\dfrac ab+\dfrac1{by}\le\dfrac{b-1}b+\dfrac1b=1$、また $\dfrac xy>\dfrac ab\ge0$、$y\le n$。 $\dfrac cd$ は $\dfrac ab$ の次の項だから $\dfrac cd\le\dfrac xy$。もし $\dfrac cd<\dfrac xy$ なら、$\dfrac xy-\dfrac cd=\dfrac{xd-cy}{dy}\ge\dfrac1{dy}$、$\dfrac cd-\dfrac ab=\dfrac{bc-ad}{bd}\ge\dfrac1{bd}$ で

$$\frac1{by}=\frac xy-\frac ab=\Bigl(\frac xy-\frac cd\Bigr)+\Bigl(\frac cd-\frac ab\Bigr)\ge\frac1{dy}+\frac1{bd}=\frac{b+y}{bdy}$$

より $d\ge b+y>n$ となり $d\le n$ に反する。ゆえに $\dfrac cd=\dfrac xy$、$\gcd(c,d)=1=\gcd(x,y)$ から $c=x$、$d=y$。よって $bc-ad=bx-ay=1$、$b+d=b+y>n$。

∎

既約分数 $a/b$ に対し、Ford の円 $C(a/b)$ を、$x$ 軸に点 $(a/b,0)$ で接し、半径が $\dfrac1{2b^2}$ の円（中心 $\bigl(\tfrac ab,\tfrac1{2b^2}\bigr)$）とします。

命題 7.3（Ford の円の接し方）✓

既約分数 $\dfrac ab\ne\dfrac cd$（$b,d\ge1$）について、$C(a/b)$ と $C(c/d)$ は、$|ad-bc|=1$ のときに限って外接し、$|ad-bc|\ge2$ のときは共有点をもたない（互いの外側にある）。

証明（命題 7.3）

2 つの円の中心間の距離の 2 乗は $\bigl(\tfrac ab-\tfrac cd\bigr)^2+\bigl(\tfrac1{2b^2}-\tfrac1{2d^2}\bigr)^2$、半径の和の 2 乗は $\bigl(\tfrac1{2b^2}+\tfrac1{2d^2}\bigr)^2$。差をとると、$(r-r')^2-(r+r')^2=-4rr'=-\dfrac1{b^2d^2}$ なので

$$(\text{距離})^2-(\text{半径の和})^2=\frac{(ad-bc)^2}{b^2d^2}-\frac1{b^2d^2}=\frac{(ad-bc)^2-1}{b^2d^2}.$$

$\dfrac ab\ne\dfrac cd$ から $ad-bc$ は $0$ でない整数で $(ad-bc)^2\ge1$。等号（距離＝半径の和、外接）となるのは $|ad-bc|=1$ のときに限り、$|ad-bc|\ge2$ なら距離が半径の和より大きい。

∎

Ford の円（1/2, 1/3, 1/4, 1/5, 2/5）。隣り合う Farey 分数の円は接している（半径 1/2 の 0/1, 1/1 の円は図の外なので省略）

注意 7.4

定理 7.2 と 命題 7.3 を合わせると、$F_n$ で隣り合う分数の Ford の円は接します。逆は $n$ を固定すると成り立ちません：$\frac13,\frac12$ の円は接します（$1\cdot2-3\cdot1=-1$）が、$F_5$ では間に $\frac25$ があり隣り合いません（$F_3$ では隣り合います）。Ford の円は、モジュラー群 $SL_2(\mathbb{Z})$ の作用（双曲幾何）で美しく理解されます。

8. 単位分数の和

定理 8.1（単位分数の和（エジプト式分数））✓

$0<x<1$ の有理数は、相異なる単位分数 $\dfrac1{n_1}+\dfrac1{n_2}+\cdots+\dfrac1{n_s}$（$n_1<n_2<\cdots<n_s$ は正の整数）の和として表せる。

証明（定理 8.1）

$x=\dfrac pq$（$p,q$ は正の整数、$p<q$）とする。$n=\lceil q/p\rceil$（$q/p$ 以上の最小の整数）とおくと $\dfrac1n\le x<\dfrac1{n-1}$（$n\ge2$ で、$n-1<q/p$ は $\dfrac1{n-1}>x$ と同値）。残り $x-\dfrac1n=\dfrac{pn-q}{qn}$ の分子は $pn-q\ge0$（$n\ge q/p$ より）で、$n<\dfrac qp+1$ より $pn<q+p$ なので $pn-q<p$。分子が $0$ なら終わり。そうでなければ、残りは $0<x'=\dfrac{p'}{q'}<1$（$p'=pn-q<p$）なので、同じ操作を繰り返す。分子は負でない整数で真に減少するから、有限回で終わる。 単位分数の相異なり性: 次に選ぶ $n'$ は、$x'=x-\dfrac1n<\dfrac1{n-1}-\dfrac1n=\dfrac1{n(n-1)}$ から $\dfrac1{n'}\le x'<\dfrac1{n(n-1)}$ より $n'>n(n-1)\ge n$（$n\ge2$）。よって選ばれる $n_1<n_2<\cdots$ は真に増加し、相異なる。

∎

例 8.2（貪欲法で作る分解）

$\dfrac56$: $n=\lceil6/5\rceil=2$、$\dfrac56-\dfrac12=\dfrac13$ で終わり、$\dfrac56=\dfrac12+\dfrac13$。$\dfrac37$: $n=3$、$\dfrac37-\dfrac13=\dfrac2{21}$。$n'=\lceil21/2\rceil=11$、$\dfrac2{21}-\dfrac1{11}=\dfrac1{231}$ で、$\dfrac37=\dfrac13+\dfrac1{11}+\dfrac1{231}$。貪欲法の項数は一般に少なくありません（分母が急激に大きくなる）が、有限で止まることは上の定理で保証されます。

9. 大学ではどこへ続くか

• 約数の総和・Euler 関数など $n$ の約数についての関数（算術関数）は 初等整数論 と解析的整数論へ続きます。完全数・Mersenne 素数の探索は GIMPS という計算プロジェクトで続いています。
• 連分数は Diophantus 近似（無理数を有理数でどこまで近似できるか）の基本道具で、Pell 方程式の解とも結びつきます（次の記事 整数の性質 II）。
• Farey 数列と Ford の円は、モジュラー群と楕円曲線・モジュラー形式（楕円曲線とモジュラー形式）への入口です。

10. 演習

演習 10.1易

$496$ が完全数であることを 命題 2.2 で確かめよ。

解答

$496=2^4\cdot31$（31 は素数）。$\sigma(496)=(1+2+4+8+16)(1+31)=31\cdot32=992=2\cdot496$。

演習 10.2標準

金額 $7x+11y$（$x,y\ge0$）で表せない最大の整数を求め、その値が表せないことを確かめよ。

解答

$\gcd(7,11)=1$ なので 定理 3.3 より $77-7-11=59$。確かめ: $59=7x+11y$ なら $11y\equiv59\equiv3\pmod7$、$11\equiv4$ で $4y\equiv3\pmod7$、$y\equiv6\pmod7$（$4\cdot6=24\equiv3$）なので $y\ge6$ で $11y\ge66>59$。

演習 10.3標準

$50!$ を $3$ で割り切れる回数 $v_3(50!)$ を求めよ。また $\binom{100}{50}$ が $3$ で割り切れる回数を求めよ。

解答

定理 5.2 より $v_3(50!)=16+5+1=22$。$v_3(100!)=33+11+3+1=48$ で、$\binom{100}{50}=\dfrac{100!}{50!\,50!}$ なので $48-2\cdot22=4$（命題 5.3［整除と素因数分解］ の 1.）。

演習 10.4標準

(1) $\dfrac{43}{19}$ を有限連分数に展開せよ。(2) $\dfrac{4}{5}$ を貪欲法で単位分数の和に分けよ。

解答

(1) $43=2\cdot19+5$、$19=3\cdot5+4$、$5=1\cdot4+1$、$4=4\cdot1$ なので $\dfrac{43}{19}=[2;3,1,4]$。確かめ: $1+\frac14=\frac54$、$3+\frac45=\frac{19}5$、$2+\frac5{19}=\frac{43}{19}$。(2) $n=\lceil5/4\rceil=2$、$\dfrac45-\dfrac12=\dfrac3{10}$、$n'=\lceil10/3\rceil=4$、$\dfrac3{10}-\dfrac14=\dfrac1{20}$ で、$\dfrac45=\dfrac12+\dfrac14+\dfrac1{20}$。

参考文献

1. G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — 第 3 章（Farey 数列）、第 10 章（連分数）。
2. Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991 — 第 1 章・第 2 章（整除と合同）、第 7 章（連分数）。
3. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994 — 第 4 章（整数論）。
4. 高木貞治『初等整数論講義』第 2 版、共立出版、1971。