# 整数の性質 I：約数・互除法・n 進法・連分数 > 約数の総和と完全数、2 種類の硬貨で払えない最大の金額、n 進法の存在と一意性、Legendre の公式、連分数、Farey 数列と Ford の円、単位分数の和を、既存の初等整数論の定理を使って証明する。 > https://rikai.mugen-giken.com/mathematics/hs-algebra/integers-divisibility ## 0. この記事の要点 「6 は、自分以外の約数 1, 2, 3 を足すとちょうど 6 になる」「3 円玉と 5 円玉だけでは、7 円だけはどうしても払えない」。こうした整数の身近な不思議を、なぜそうなるのかまで言葉で確かめるのがこの記事です。読み終えると、約数の足し算、硬貨で払えない金額、$n$ 進法の書き換え、階乗に含まれる素数の個数などを、計算だけでなく理由つきで説明できるようになります。以下の箇条書きは全体の見取り図なので、知らない言葉があっても、先に進んで各節で出会ったときに戻って読めば十分です。 - 高校の整数問題で使う道具（互除法・素因数分解の一意性・不定方程式）は、大学の初等整数論の記事で証明されています。この記事はそれらを `` で指し、**高校の整数の問題が実際に使う形**（約数の総和・完全数・硬貨の問題・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 の円は隣り合う分数のところで接します。 ## 1. 動機 高校の整数の問題は、数学の他の分野と比べて道具が少ないのに、解くたびに発想が要ります。それは、道具（割り算・素因数分解・余り）の**正確な形**があいまいなまま、問題ごとにその場しのぎで使っているからです。 この記事では、「割り切れる」「素因数の指数」「余り」を厳密に使って、よく出る結果を最初から組み立てます。互除法・Bézout の等式・素因数分解の一意性はすでに証明されているので、これらは再証明せずに使います。使った箇所を毎回 `` で示します。 ## 2. 約数と約数の総和 記号: 正の整数 $n$ の素数 $p$ についての付値 $v_p(n)$（$p^e\mid n$ となる最大の $e\ge0$。$n$ を割り切る $p$ の個数のこと）は 。$n=\prod_pp^{v_p(n)}$（）。 正の整数 $n$ の正の約数全体の和を $\sigma(n)$ と書く。$\sigma(n)=2n$ となる $n$ を**完全数**という。 正の整数 $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 つずつに対応する、というのが証明の中身です。 正の整数 $d$ について、$d\mid n$ であることと、すべての素数 $p$ で $v_p(d)\le v_p(n)$ であることは同値（ の 2.）。$d$ は指数の組 $(v_p(d))_p$ から $d=\prod p^{v_p(d)}$ と復元できる（）。したがって $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)$ に分かれることから従う。 $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$ は と同じ数え方です。 $n\ge2$ について $2^n-1$ が素数ならば、$n$ は素数である。 $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$ は素数でないことになり、仮定に反する。 偶数 $n$ が完全数であるための必要十分条件は、$n=2^{p-1}(2^p-1)$ と書け、$2^p-1$ が素数となる整数 $p\ge2$ が存在することである。 この定理は「この形の数は完全数である」（十分性）と「偶数の完全数はこの形に限る」（必要性）の 2 つを言っています。十分性は に当てはめる計算だけです。必要性は、偶数の完全数を $2^k$ と奇数 $m$ の積に分け、$\sigma(n)=2n$ という条件から $m$ の約数が $1$ と $m$ だけ（つまり $m$ が素数）に絞られる、という流れで進みます。たとえば $6=2\cdot3$ では $k=1$、$m=3$ です。 (十分性) $M=2^p-1$ が素数であるとし、$n=2^{p-1}M$ とする。$M$ は奇数なので $2^{p-1}$ と互いに素で、 から $\sigma(n)=\sigma(2^{p-1})\sigma(M)=(2^p-1)(1+M)=M\cdot2^p=2n$。 (必要性) $n$ が偶数の完全数とし、$n=2^km$（$k\ge1$、$m$ は奇数）と書く。 より $\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^{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)$。 $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$ は完全数ではありません。 は $p$ が素数であることを要請しますが、逆（$p$ が素数なら $2^p-1$ が素数）は $p=11$ で成り立ちません。奇数の完全数が存在するかどうかは未解決です。 ## 3. 1 次不定方程式と硬貨の問題 $a,b$ を正の整数で互いに素とします。$ax+by=c$ の整数解の存在と一般解は、すでに （$\gcd(a,b)\mid c$ が条件で、解は $(x_0+bk,\ y_0-ak)$ の形）と で証明されています。高校の問題で本当に問われるのは、**負でない整数解**の存在と個数です。 実数 $x$ と正の整数 $b$ について $\bigl\lfloor\lfloor x\rfloor/b\bigr\rfloor=\lfloor x/b\rfloor$ である。ここで $\lfloor t\rfloor$ は $t$ 以下の最大の整数。 $L=\lfloor x\rfloor$、$q=\lfloor L/b\rfloor$ とおくと $qb\le L\le x $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 回現れるので、区間をいくつ並べられるかを数えれば個数が分かります。 まず $x\ge0$ に対し、$y=(c-ax)/b$ が整数となるのは $ax\equiv c\pmod b$ のときで、$a$ は $b$ と互いに素なので から $ax\equiv c$ を満たす $x$ は法 $b$ でただ 1 つの剰余類 $x\equiv x_0\pmod b$（$0\le x_0 より $q=\lfloor c/(ab)\rfloor$。 $a,b$ を互いに素な正の整数とする。$ax+by$（$x,y$ は $0$ 以上の整数）の形に表せない整数のうち最大のものは $ab-a-b$ である（$a=1$ のときは、負の整数がすべて表せず、最大の $-1$ が $ab-a-b$ に一致する）。 $c>ab-a-b$ が表せることを示す。$a$ は $b$ と互いに素なので、 により $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$ なので、 から $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$ となり矛盾する。 $a=3$、$b=5$ のとき、$3x+5y$ で表せない最大の整数は $15-3-5=7$。実際、$0,3,5,6,8,9,10,\dots$ が表せて、$1,2,4,7$ が表せません（8 以上はすべて表せる）。非負解の個数は によると $3x+5y=40$ で $\lfloor40/15\rfloor=2$ または $3$ で、実際 $(x,y)=(0,8),(5,5),(10,2)$ の 3 個です。 ## 4. 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 通りに書ける。 (存在) $N$ についての完全帰納法（）。$N で $N=qb+r$（$0\le r の一意性）、両方の表示で一致する。残りの部分 $(N-d_0)/b=d_kb^{k-1}+\cdots+d_1$ は最高位の係数が $0$ でない正の整数 $(N-d_0)/b$ の表示で、$N$ より小さいから、完全帰納法の仮定により 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$）。この「割って余りを集める」手順が の存在の証明そのものです。10 進法の筆算の繰り上がりは、桁ごとの和が $b=10$ 以上になったとき $d=qb+r$ と書き直して $q$ を上の桁に足す操作で、これも除法の原理です。 ## 5. 倍数の個数と Legendre の公式 正の整数 $n,d$ について、$1,2,\dots,n$ のうち $d$ の倍数の個数は $\lfloor n/d\rfloor$ である。 $d$ の倍数は $d,2d,\dots$ で、$jd\le n$ は $j\le n/d$、すなわち $j\le\lfloor n/d\rfloor$ と同値（$j$ は整数）。 素数 $p$ と正の整数 $n$ について $$ v_p(n!)=\sum_{i=1}^\infty\Bigl\lfloor\frac n{p^i}\Bigr\rfloor $$ である（$p^i>n$ の項は $0$ なので実際は有限和）。 の 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$（）。 末尾に並ぶ 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]}$ と再帰的に定義）。これを**有限連分数**といいます。 $n\ge1$ で $a_n\ge2$ ならば、$y=[a_1;a_2,\dots,a_n]$ は $y>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$。 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$ の互除法の商（）に一致する。 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$（$01$ が整数なので $a_n\ge2$。 (一意性) $x=[a_0;\dots,a_n]=[b_0;\dots,b_m]$ を条件を満たす 2 つの表示とする。$n\ge1$ なら、 より $0 $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$ の場合を見ます。 $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}$ である。 $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$ の存在は 。$|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 の円 正の整数 $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$ です。 $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 $\gcd(a,b)=1$ なので により $bx'-ay'=1$ となる整数 $x',y'$ がある。$(x,y)=(x'+ka,\ y'+kb)$ も同じ式 $bx-ay=1$ を満たすから、$k$ を選んで $n-b0$。 $\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)$）とします。 既約分数 $\dfrac ab\ne\dfrac cd$（$b,d\ge1$）について、$C(a/b)$ と $C(c/d)$ は、$|ad-bc|=1$ のときに限って外接し、$|ad-bc|\ge2$ のときは共有点をもたない（互いの外側にある）。 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$ なら距離が半径の和より大きい。
1/21/3 1/41/52/5
と を合わせると、$F_n$ で隣り合う分数の Ford の円は接します。逆は $n$ を固定すると成り立ちません：$\frac13,\frac12$ の円は接します（$1\cdot2-3\cdot1=-1$）が、$F_5$ では間に $\frac25$ があり隣り合いません（$F_3$ では隣り合います）。Ford の円は、モジュラー群 $SL_2(\mathbb{Z})$ の作用（双曲幾何）で美しく理解されます。 ## 8. 単位分数の和 $0 $x=\dfrac pq$（$p,q$ は正の整数、$px$ と同値）。残り $x-\dfrac1n=\dfrac{pn-q}{qn}$ の分子は $pn-q\ge0$（$n\ge q/p$ より）で、$n<\dfrac qp+1$ より $pnn(n-1)\ge n$（$n\ge2$）。よって選ばれる $n_1 $\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$ の約数についての関数（算術関数）は [初等整数論](/mathematics/number-theory/elementary-number-theory) と解析的整数論へ続きます。完全数・Mersenne 素数の探索は GIMPS という計算プロジェクトで続いています。 - 連分数は Diophantus 近似（無理数を有理数でどこまで近似できるか）の基本道具で、Pell 方程式の解とも結びつきます（次の記事 [整数の性質 II](/mathematics/hs-algebra/congruences)）。 - Farey 数列と Ford の円は、モジュラー群と楕円曲線・モジュラー形式（[楕円曲線とモジュラー形式](/mathematics/number-theory/elliptic-curves-and-modular-forms)）への入口です。 ## 10. 演習 $496$ が完全数であることを で確かめよ。 $496=2^4\cdot31$（31 は素数）。$\sigma(496)=(1+2+4+8+16)(1+31)=31\cdot32=992=2\cdot496$。 金額 $7x+11y$（$x,y\ge0$）で表せない最大の整数を求め、その値が表せないことを確かめよ。 $\gcd(7,11)=1$ なので より $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$。 $50!$ を $3$ で割り切れる回数 $v_3(50!)$ を求めよ。また $\binom{100}{50}$ が $3$ で割り切れる回数を求めよ。 より $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$（ の 1.）。 (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。