整数の性質 II：合同式・位数・循環小数・ピタゴラス数・Pell 方程式

0. この記事の要点

「2 の 100 乗の末尾 2 桁は」「$1/7$ を小数にすると、なぜ同じ数字が繰り返すのか」といった素朴な疑問は、整数を割った余りだけに注目すると、見通しよく答えられます。この記事では、余りで整数を扱う記法（合同式）を使って、倍数の見分け方、冪の余りが繰り返す仕組み、循環小数、直角三角形の辺の整数比、$x^2-2y^2=1$ のような方程式の整数解を、同じ考え方で説明します。読み終えると、これらの問題を余りの計算に置き換えて解けるようになります。

• 合同式の計算規則・消去法則・Euler の定理・Fermat の小定理・中国剰余定理は、大学の初等整数論の記事に証明があります。この記事ではそれらを <Ref> で指し、高校の問題でよく使う形に仕立てます。
• 倍数の判定法（3・9・11 の倍数、$7\cdot11\cdot13=1001$ による判定）は、$10\equiv1$、$10\equiv-1$、$1000\equiv-1$ という合同式の言い換えです。
• 法 $m$ での $a$ の位数は $a^k\equiv1$ となる最小の $k$。$a^k\equiv1$ となる $k$ はすべて位数の倍数で、位数は $\varphi(m)$ の約数です。冪の余りは位数を周期として繰り返します。
• Wilson の定理: 素数 $p$ について $(p-1)!\equiv-1\pmod p$。逆も成り立ち、素数判定の条件になります。
• 有理数の小数展開は有限小数か循環小数で、循環節の長さは 10 の位数です。
• 原始ピタゴラス数は $(m^2-n^2,\,2mn,\,m^2+n^2)$ の形に限り、単位円上の有理点は有理数 $t$ でパラメータ表示できます。
• Pell 方程式 $x^2-dy^2=1$（$d$ は平方数でない）には必ず正の整数解があり（Dirichlet の近似定理と鳩の巣原理で証明します）、正の解は最小解の冪で尽くされます。

この記事で使う事前知識

• 約数・互除法・Bézout の等式: 整数どうしの割り算と最大公約数の求め方、$\gcd(a,b)=ax+by$ と書けるという事実。→ 整数の性質 I
• 連分数: 実数を分数の入れ子で近似する表し方。前の記事で扱った近似分数の例を、Pell 方程式の例で参照します。→ 整数の性質 I
• 剰余環: 整数を $m$ で割った余りで分類し、余りどうしで足し算と掛け算を考えるしくみ。→ 剰余環
• 単元群: 法 $m$ で掛けて $1$ になる相手（逆元）をもつ余り、つまり $m$ と互いに素な余りの集まり。→ 単元群
• 整列性: 正の整数の空でない集まりには、必ず最小の元がある、という性質。→ 整列性

1. 動機

高校の整数問題では、合同式を使うと見通しがよくなる場面が多くあります。「$2^{100}$ の末尾 2 桁」「ある数が 7 の倍数か」「$1/7$ の小数展開が $142857$ の繰り返しになる理由」「$x^2-2y^2=1$ の整数解を全部求めよ」。これらはバラバラの問題に見えて、すべて剰余類の乗法（位数・単元）の話です。

この記事は、前の記事（整数の性質 I）で作った道具（付値（素数 $p$ が何回割り切れるかを表す数）・Bézout・連分数）に、合同式の言葉を加えて、これらの問題を同じ土台で証明します。

2. 合同式の計算と倍数の判定法

整数 $a,b$ と正の整数 $m$ について、$m\mid(a-b)$ のとき $a\equiv b\pmod m$ と書きます（定義 3.1［合同式とフェルマーの小定理］）。和・差・積・冪は、合同式の両辺に使えます（命題 3.3［合同式とフェルマーの小定理］）。割り算は注意が必要で、$ca\equiv cb\pmod m$ から $a\equiv b$ が言えるのは $\gcd(c,m)=1$ のときだけです（命題 3.6［合同式とフェルマーの小定理］）。より正確には $ca\equiv cb\pmod m\iff a\equiv b\pmod{m/\gcd(c,m)}$。

たとえば法 $6$ で $2\cdot1=2$ と $2\cdot4=8$ は合同（差が $6$）ですが、$1$ と $4$ は合同ではありません（差が $3$）。$\gcd(2,6)=2$ で、割れるのは法を $6/2=3$ に縮めたときだけで、実際 $1\equiv4\pmod3$ です。

命題 2.1（倍数の判定法）✓

正の整数 $N$ の 10 進表示を $N=\sum_{i=0}^kd_i10^i$（$0\le d_i\le9$）とする。

1. $N\equiv\sum_id_i\pmod9$。したがって $9$（および $3$）で割り切れるための必要十分条件は、各位の数字の和が $9$（$3$）で割り切れること。
2. $N\equiv\sum_i(-1)^id_i\pmod{11}$。$11$ で割り切れるのは、交代和 $d_0-d_1+d_2-\cdots$ が $11$ で割り切れるとき。
3. $N$ を下から 3 桁ずつの組 $g_0,g_1,\dots$ に分けて $N=\sum_jg_j1000^j$ とすると、$N\equiv\sum_j(-1)^jg_j\pmod{1001}$。$1001=7\cdot11\cdot13$ なので、$N$ が $7$ や $11$ や $13$ で割り切れるかは、この交代和でも判定できる。
4. $N$ を $2^e$ や $5^e$（$e\le k+1$）で割った余りは、下 $e$ 桁の数で決まる。とくに $4$ で割り切れるかは下 2 桁、$8$ で割り切れるかは下 3 桁で決まる。

証明（命題 2.1）

1. $10\equiv1\pmod9$ なので 命題 3.3［合同式とフェルマーの小定理］ から $10^i\equiv1$、$N\equiv\sum d_i$。$3\mid9$ なので $\pmod3$ でも同じ。
2. $10\equiv-1\pmod{11}$ から $10^i\equiv(-1)^i$。
3. $1000=1001-1\equiv-1\pmod{1001}$ から $1000^j\equiv(-1)^j$。
4. $10^i$ は $i\ge e$ で $2^e$ の倍数かつ $5^e$ の倍数（$10^e=2^e5^e$）なので、$N\equiv\sum_{i<e}d_i10^i\pmod{2^e}$、$\pmod{5^e}$。

∎

例 2.2（1234567 は 7 の倍数か）

$1234567$ を 3 桁ずつに分けて $1|234|567$。交代和は $567-234+1=334$。$334=7\cdot47+5$ なので $7$ で割り切れず、余りは $5$ です（命題 2.1 の 3. は、余りまで $\pmod{1001}$ で保つので、$1234567\equiv334\pmod{1001}$、したがって $\bmod7$ で $334\equiv5$）。実際 $1234567=7\cdot176366+5$ です。

3. 位数と冪の余り

定義 3.1（位数）↗

$m\ge2$ を整数、$a$ を $\gcd(a,m)=1$ の整数とする。$a^k\equiv1\pmod m$ となる最小の正の整数 $k$ を、法 $m$ における $a$ の位数といい $\operatorname{ord}_m(a)$ と書く。

Euler の定理（定理 5.3［合同式とフェルマーの小定理］）から $a^{\varphi(m)}\equiv1$ なので、$k=\varphi(m)$ は条件を満たし、位数は存在します。

定理 3.2（位数は φ(m) を割る）✓

$\gcd(a,m)=1$、$d=\operatorname{ord}_m(a)$ とする。正の整数 $k$ について $a^k\equiv1\pmod m\iff d\mid k$。とくに $d\mid\varphi(m)$ である。

証明（定理 3.2）

$d\mid k$ なら $k=dj$ で $a^k=(a^d)^j\equiv1^j=1$（命題 3.3［合同式とフェルマーの小定理］）。逆に $a^k\equiv1$ とする。除法の原理（定理 2.1［合同式とフェルマーの小定理］）で $k=qd+r$（$0\le r<d$）。$a^k=(a^d)^qa^r\equiv a^r$ なので $a^r\equiv1$。$d$ の最小性から $r=0$、すなわち $d\mid k$。最後に Euler の定理（定理 5.3）［合同式とフェルマーの小定理］ より $a^{\varphi(m)}\equiv1$ なので $d\mid\varphi(m)$。

∎

大学では、これは群 $(\mathbb{Z}/m\mathbb{Z})^\times$ の元の位数が群の位数を割る、という Lagrange の定理の特別な場合です（Euler の定理と Fermat の小定理（定理 7.3）［部分群と剰余類］）。

命題 3.3（冪の余りの周期）✓

$\gcd(a,m)=1$、$d=\operatorname{ord}_m(a)$ とする。すべての整数 $k,l\ge0$ について $a^k\equiv a^l\pmod m\iff k\equiv l\pmod d$。したがって $a^k\bmod m$ は $d$ を周期として繰り返し、最小の周期はちょうど $d$ である。

証明（命題 3.3）

$k\ge l$ とする。$\gcd(a,m)=1$ なので 命題 3.6［合同式とフェルマーの小定理］ により $a^l$ を両辺から消去できて、$a^k\equiv a^l\iff a^{k-l}\equiv1$（$\gcd(a^l,m)=1$ に注意。$\Leftarrow$ は両辺に $a^l$ を掛ければよい）。$k=l$ なら両辺とも成り立ち $d\mid0$ も成り立つ。$k>l$ なら $a^{k-l}\equiv1$ は 定理 3.2 から $d\mid(k-l)$ と同値。

∎

例 3.4（冪の下 2 桁）

$7^2=49$、$7^4=2401\equiv1\pmod{100}$ なので $\operatorname{ord}_{100}(7)\mid4$、また $7^2=49\not\equiv1$ だから位数は $4$。$2026=4\cdot506+2$ より $7^{2026}\equiv7^2=49\pmod{100}$。下 2 桁は $49$ です。位数が分かれば、巨大な冪の余りは周期で圧縮できます。Fermat の小定理（定理 5.1［合同式とフェルマーの小定理］）を使って $7^{100}\bmod13$ を計算すると、$7^{12}\equiv1$ より $7^{100}=7^{96}\cdot7^4\equiv7^4=2401\equiv9$（$2401=13\cdot184+9$）です。

4. Wilson の定理

定理 4.1（Wilson の定理とその逆）✓

$n\ge2$ を整数とする。$n$ が素数であることと、$(n-1)!\equiv-1\pmod n$ であることは同値である。

素数 $p$ のとき、証明では $1,\dots,p-1$ を、掛けて $1$ になる相手（法 $p$ の逆元）どうしでペアにします。たとえば $p=7$ なら $2\cdot4=8\equiv1$、$3\cdot5=15\equiv1$ で、残るのは $1$ と $6\equiv-1$ だけです。ペアの積は $1$ なので、$6!\equiv1\cdot1\cdot1\cdot6\equiv-1$ となります。自分自身とペアになる数が $1$ と $p-1$ だけであることを示すのが、証明の要点です。

証明（定理 4.1）

(素数ならば) $n=p$ が素数とする。$p=2$ のとき $1!=1\equiv-1\pmod2$。$p\ge3$ とする。$1,\dots,p-1$ の各 $a$ は $\gcd(a,p)=1$ なので 命題 4.4［合同式とフェルマーの小定理］ により法 $p$ の逆元 $a'$（$aa'\equiv1$）が $\{1,\dots,p-1\}$ の中にただ 1 つある。$a'=a$、すなわち $a^2\equiv1$ のとき $p\mid(a-1)(a+1)$ で、素数に関する Euclid の補題（補題 4.1）［素数の魅力と素数定理］ から $a\equiv1$ か $a\equiv-1$、すなわち $a=1$ か $a=p-1$。それ以外の $a\in\{2,\dots,p-2\}$ は、$a\ne a'$ の組 $\{a,a'\}$ に分かれ（$a'\in\{2,\dots,p-2\}$：$a'\equiv1$ なら $a\equiv1$、$a'\equiv-1$ なら $a\equiv-1$ になってしまうので）、各組の積は $aa'\equiv1$。よって $2\cdot3\cdots(p-2)\equiv1$、$(p-1)!=1\cdot(2\cdots(p-2))\cdot(p-1)\equiv p-1\equiv-1$。 (逆) $n$ が素数でないとする。$n\ge2$ なので $1<a<n$ の約数 $a$ がある。$a\le n-1$ だから $a\mid(n-1)!$。もし $(n-1)!\equiv-1\pmod n$ なら $n\mid(n-1)!+1$ で、$a\mid n$ だから $a\mid(n-1)!+1$。$a\mid(n-1)!$ と合わせて $a\mid1$ となり、$a>1$ に反する。ゆえに $(n-1)!\not\equiv-1$。

∎

例 4.2（Wilson の定理で階乗の余りを求める）

$p=23$ で $22!\equiv-1\pmod{23}$。$22!=22\cdot21\cdot20!\equiv(-1)(-2)\cdot20!=2\cdot20!$ なので $2\cdot20!\equiv-1\equiv22$、$20!\equiv11\pmod{23}$（$2\cdot11=22\equiv-1$）。Wilson の定理は素数判定のアルゴリズムとしては $(n-1)!$ の計算が重すぎて実用になりませんが、「合成数でも素数でも、階乗の余りがこれほど鮮やかに分かれる」ことを示しています。

5. 有理数と循環小数

実数 $0\le x<1$ の小数展開 $0.d_1d_2d_3\cdots$ とは、部分和 $s_n=\sum_{k\le n}d_k10^{-k}$ の上限が $x$ であることをいいます（定義 6.1［数とは何か］）。有理数 $a/b$（$0\le a<b$）の小数展開は、筆算（割り算）の手順で作れます。$r_0=a$ とし、$k=1,2,\dots$ について

$$d_k=\Bigl\lfloor\frac{10r_{k-1}}b\Bigr\rfloor,\qquad r_k=10r_{k-1}-d_kb$$

と定めます（$r_k$ は筆算の「余り」で $0\le r_k<b$、$d_k\in\{0,\dots,9\}$）。

定理 5.1（有理数と循環小数）✓

1. 有理数 $a/b$（$0\le a<b$）について、上の手順で得られる $d_1,d_2,\dots$ は $a/b$ の小数展開であり、ある位置から先は繰り返す（有限小数は $0$ の繰り返しとみなす）。
2. 逆に、ある位置から先で同じ数字の並びを繰り返す小数展開 $0.d_1\cdots d_s\overline{c_1\cdots c_t}$ の値は有理数である。

証明（定理 5.1）

1. 帰納法で $\dfrac ab=\sum_{k=1}^n\dfrac{d_k}{10^k}+\dfrac{r_n}{b\,10^n}$ が示される（$n=0$ は自明、$10r_{n-1}=d_nb+r_n$ より $\dfrac{r_{n-1}}{b10^{n-1}}=\dfrac{d_n}{10^n}+\dfrac{r_n}{b10^n}$）。よって $0\le\dfrac ab-s_n=\dfrac{r_n}{b10^n}<10^{-n}$。$s_n\le\dfrac ab$ なので上限は $\dfrac ab$ 以下で、任意の $y<\dfrac ab$ に対し アルキメデスの原理（命題 5.4）［数とは何か］ で $10^{-n}\le\frac1n<\dfrac ab-y$ となる $n$ をとれば $s_n>y$。したがって上限は $\dfrac ab$。余り $r_0,r_1,\dots,r_b$ は $\{0,1,\dots,b-1\}$ の $b+1$ 個の値をとるので、鳩の巣原理（定理 7.5）［数え上げと母関数］ によりある $i<j\le b$ で $r_i=r_j$。$(d_{k+1},r_{k+1})$ は $r_k$ だけで決まるので、$k\ge i$ で $r_{k+(j-i)}=r_k$、$d_{k+1+(j-i)}=d_{k+1}$ となり、数字は第 $i+1$ 位から先で周期 $j-i$ で繰り返す。
2. $A=0.d_1\cdots d_s$（有限小数、有理数）、$C=c_1\cdots c_t$（$t$ 桁の整数）とする。繰り返し部分の値は $\sum_{j\ge1}C\,10^{-s}10^{-tj}=C\,10^{-s}\Bigl(\dfrac1{1-10^{-t}}-1\Bigr)=\dfrac{C}{10^s(10^t-1)}$（等比級数、命題 6.2［数とは何か］）。したがって値は $A+\dfrac C{10^s(10^t-1)}$ で、有理数。

∎

定理 5.2（循環節の長さは 10 の位数）✓

既約分数 $\dfrac ab$（$0<a<b$、$\gcd(a,b)=1$）の分母を $b=2^\alpha5^\beta b'$（$\gcd(b',10)=1$）と書き、$m=\max(\alpha,\beta)$ とする。

1. 小数展開が有限小数であるための必要十分条件は $b'=1$ である。
2. $b'>1$ のとき、小数第 $m+1$ 位から先は純粋に循環し、その最小の周期（循環節の長さ）は法 $b'$ における $10$ の位数 $\operatorname{ord}_{b'}(10)$ である。

証明の方針は次のとおりです。分母の $2$ と $5$ の部分は、小数点を $m$ 桁ずらすと消えます。その後に残る分母 $b'$ の部分では、筆算の余りが「$10$ 倍して $b'$ で割った余りをとる」操作で更新されるので、$k$ 回後の余りは元の余りの $10^k$ 倍（法 $b'$）になります。余りが最初に戻るのは $10^k\equiv1$ となるときで、その最小の $k$ がちょうど位数です。

証明（定理 5.2）

1. $b'=1$ なら $10^m\dfrac ab=a\cdot2^{m-\alpha}5^{m-\beta}$ は整数なので、展開は小数第 $m$ 位までで終わる（定理 5.1 の手順で、$10^mx$ が整数なら以後の余りは $0$）。逆に有限小数 $x=N/10^n$ なら、既約分数の分母 $b$ は $10^n$ を割り（$a10^n=Nb$ で $\gcd(a,b)=1$ より $b\mid10^n$）、$b'$ は $10^n$ の約数で $\gcd(b',10)=1$ なので $b'=1$。
2. $y=10^mx=\dfrac{a''}{b'}$、$a''=a\cdot2^{m-\alpha}5^{m-\beta}$ は $b'$ と互いに素（$a$ は $b$ と、$2^{m-\alpha}5^{m-\beta}$ は $b'$ と互いに素）。$y$ の整数部分を除いた小数部分を $f=\dfrac c{b'}$（$0<c<b'$、$\gcd(c,b')=1$）とおく。一方、定理 5.1 の証明の式から $10^mx=\sum_{k\le m}d_k10^{m-k}+\dfrac{r_m}b$（第 1 項は整数）なので、$f=r_m/b$。筆算の数字は $d_k=\lfloor10\cdot r_{k-1}/b\rfloor$、$r_k/b=10\cdot r_{k-1}/b-d_k$ と比 $r_{k-1}/b$ だけで決まるから、$x$ の小数第 $m+1$ 位以降の数字は、$f=c/b'$ に筆算の手順を適用して得られる数字に一致する。$f$ に筆算の手順を適用すると $r_0=c$、$r_k\equiv10r_{k-1}\pmod{b'}$ なので $r_k\equiv10^kc\pmod{b'}$。$r_k=r_0$ となるのは $10^kc\equiv c$、すなわち（$\gcd(c,b')=1$ なので 命題 3.6［合同式とフェルマーの小定理］ で $c$ を消去して）$10^k\equiv1\pmod{b'}$ のときで、これは 定理 3.2 から $L=\operatorname{ord}_{b'}(10)$ が $k$ を割ることと同値。$r_L=r_0$ だから、すべての $k\ge0$ で $r_{k+L}=r_k$（$r_{k+1}$ は $r_k$ だけで決まる）、したがって数字は第 1 位から周期 $L$ で繰り返す。周期 $\ell$（$d_{k+\ell}=d_k$）で繰り返すなら、$f=0.d_1d_2\cdots$ について $10^\ell f=D+f$（$D=d_1\cdots d_\ell$ を整数とみたもの）なので $(10^\ell-1)c/b'=D$ は整数。$b'\mid(10^\ell-1)c$、$\gcd(c,b')=1$ だから 補題 2.2［整除と素因数分解］ により $b'\mid10^\ell-1$、すなわち $10^\ell\equiv1\pmod{b'}$ で $L\mid\ell$。ゆえに $\ell\ge L$ で、最小の周期は $L$。

∎

例 5.3（1/7、1/13、1/6 の小数展開）

$10\bmod7$ の冪は $3,2,6,4,5,1$ で $\operatorname{ord}_7(10)=6$。$\dfrac17=0.\overline{142857}$（周期 $6$）。$\operatorname{ord}_{13}(10)=6$（$10^3=1000\equiv-1\pmod{13}$ なので $10^6\equiv1$、$10^3\not\equiv1$、位数は $6$ の約数で $2,3$ では $1$ にならない）で、$\dfrac1{13}=0.\overline{076923}$。$\dfrac16$ は $b=2\cdot3$、$\alpha=1$、$b'=3$、$\operatorname{ord}_3(10)=1$ で、$m=1$ なので小数第 $2$ 位から先が循環します：$0.1\overline{6}$。素数 $p$ について $\operatorname{ord}_p(10)$ が $p-1$ に等しいとき、$1/p$ の循環節の長さは最大の $p-1$ になります（$p=7$ はその例）。

6. 原始ピタゴラス数と単位円の有理点

$a^2+b^2=c^2$ を満たす正の整数の組 $(a,b,c)$ をピタゴラス数、さらに $\gcd(a,b)=1$ のものを原始ピタゴラス数といいます。

補題 6.1（互いに素な数の積が平方数なら、それぞれ平方数）✓

$u,v$ を互いに素な正の整数とし、$uv$ が平方数ならば、$u$ も $v$ も平方数である。

証明（補題 6.1）

$uv=w^2$ とする。素数 $p$ について $v_p(u)+v_p(v)=v_p(uv)=2v_p(w)$（命題 5.3［整除と素因数分解］ の 1.）は偶数。$u,v$ は互いに素なので、どの素数 $p$ も両方を割ることはなく、$v_p(u)$ と $v_p(v)$ の少なくとも一方は $0$。したがって他方は偶数で、$v_p(u),v_p(v)$ はともに偶数。$u=\prod p^{v_p(u)}$（定理 5.2［整除と素因数分解］）なので $u=\bigl(\prod p^{v_p(u)/2}\bigr)^2$、$v$ も同様。

∎

定理 6.2（原始ピタゴラス数）✓

$b$ が偶数であるような原始ピタゴラス数 $(a,b,c)$ は、互いに素な正の整数 $m>n$ で $m-n$ が奇数であるものを用いて

$$(a,b,c)=(m^2-n^2,\ 2mn,\ m^2+n^2)$$

とただ 1 通りに表される。逆に、そのような $m,n$ から作った $(a,b,c)$ は原始ピタゴラス数である。

証明（定理 6.2）

$(a,b,c)$ を原始ピタゴラス数とする。$a,b$ がともに偶数なら $\gcd(a,b)\ge2$ に反する。ともに奇数なら $a^2+b^2\equiv2\pmod4$ だが、平方数は $\bmod4$ で $0$ か $1$ なので $c^2$ にならない。よって一方だけが偶数で、$b$ を偶数、$a$ を奇数とする（$c$ は奇数）。$\gcd(a,c)=1$ である：素数 $p$ が $a,c$ を割れば $p\mid c^2-a^2=b^2$ なので $p\mid b$、$\gcd(a,b)=1$ に反する。 $b^2=c^2-a^2=(c-a)(c+a)$。$c,a$ はともに奇数なので $c-a=2u$、$c+a=2v$（$u,v$ は正の整数、$c>a$）と書ける。$\bigl(\tfrac b2\bigr)^2=uv$。$u,v$ は互いに素：$d\mid u,v$ なら $d\mid v+u=c$、$d\mid v-u=a$ で、$\gcd(a,c)=1$ より $d=1$。補題 6.1 から $u=n^2$、$v=m^2$（$m,n$ は正の整数）。$c=v+u=m^2+n^2$、$a=v-u=m^2-n^2$、$\bigl(\tfrac b2\bigr)^2=m^2n^2$ より $b=2mn$。$a>0$ から $m>n$、$\gcd(u,v)=1$ から $\gcd(m,n)=1$、$a$ が奇数だから $m,n$ の偶奇は異なる（$m-n$ は奇数）。 逆に、$m>n>0$、$\gcd(m,n)=1$、$m-n$ 奇数のとき、$(m^2-n^2)^2+(2mn)^2=(m^2+n^2)^2$ が展開で確かめられる。$a=m^2-n^2$ は奇数。素数 $p$ が $a$ と $c$ を割れば、$p$ は奇数で $2m^2=a+c$、$2n^2=c-a$ を割るので $p\mid m$、$p\mid n$ となり $\gcd(m,n)=1$ に反する。よって $\gcd(a,c)=1$ で、$\gcd(a,b)=1$（$p\mid a,b$ なら $p\mid c^2=a^2+b^2$）。表し方が一意なのは、上の構成で $m,n$ が $u,v$ から決まるため。

∎

$(m,n)=(2,1),(3,2),(4,1),(4,3),(5,2)$ から $(3,4,5)$、$(5,12,13)$、$(15,8,17)$、$(7,24,25)$、$(21,20,29)$ が得られます（偶数の方を $b$ に並べ替えれば上の形）。

系 6.3（単位円上の有理点）✓

単位円 $x^2+y^2=1$ 上の有理点（座標がともに有理数の点）のうち $(-1,0)$ でないものは、有理数 $t$ を使って

$$(x,y)=\Bigl(\frac{1-t^2}{1+t^2},\ \frac{2t}{1+t^2}\Bigr)$$

とただ 1 通りに表される。逆に、有理数 $t$ からこの式で得られる点は単位円上の有理点である。

証明（系 6.3）

$P=(x,y)$ を有理点で $x\ne-1$ とすると、$t=\dfrac y{1+x}$（$(-1,0)$ と $P$ を結ぶ直線の傾き）は有理数。$y=t(1+x)$ を $x^2+y^2=1$ に代入すると $x^2-1+t^2(1+x)^2=0$、すなわち $(1+x)\bigl(x-1+t^2(1+x)\bigr)=0$。$1+x\ne0$ なので $x=\dfrac{1-t^2}{1+t^2}$、$y=t(1+x)=\dfrac{2t}{1+t^2}$。$t$ は $P$ から $t=y/(1+x)$ と決まるので一意。逆に有理数 $t$ について $(1-t^2)^2+(2t)^2=(1+t^2)^2$ が展開で確かめられ、点は単位円上にある。

∎

$t=n/m$ とおくと、この式は原始ピタゴラス数の $(m^2-n^2,2mn,m^2+n^2)/(m^2+n^2)$ と一致します（定理 6.2 と同じ公式）。これは、円という曲線の有理点を、直線の傾きという 1 つの有理数で全部数え上げた最も簡単な例で、楕円曲線の有理点（楕円曲線とモジュラー形式）への入口になります。

点 (-1, 0) から傾き 1/2 の直線を引くと、円との 2 つ目の交点は (3/5, 4/5)。傾きが有理数なら、交点も有理点になる。

7. Pell 方程式

$d\ge2$ を平方数でない整数とします。$x^2-dy^2=1$ の整数解を調べます。$\sqrt d>0$ は存在します（$f(x)=x^2-d$ は $f(1)<0<f(d)$ なので 中間値の定理（定理 5.7）［極限と連続性］ による）。$\sqrt d$ は無理数（系 7.7［証明の技術］）なので、整数 $x,y$ について $x+y\sqrt d=x'+y'\sqrt d$ なら $x=x'$、$y=y'$（$(y-y')\sqrt d=x'-x$ で $y\ne y'$ なら $\sqrt d$ が有理数になる）。

整数 $x,y$ に対し $\xi=x+y\sqrt d$、$\bar\xi=x-y\sqrt d$、$N(\xi)=\xi\bar\xi=x^2-dy^2$ とおきます。$\xi'=x'+y'\sqrt d$ との積 $\xi\xi'=(xx'+dyy')+(xy'+x'y)\sqrt d$ は同じ形で、$\overline{\xi\xi'}=\bar\xi\bar\xi'$ なので $N(\xi\xi')=N(\xi)N(\xi')$ です。

まず、正の整数解が必ず存在することを示します。方針は次のとおりです。$\sqrt d$ をよく近似する分数 $x/y$ をたくさん作ると、$x^2-dy^2$ は $0$ でない小さな整数になります。とる値は有限個しかないので、同じ値 $k$ をとり、しかも $x,y$ の $k$ で割った余りまで等しい 2 組が見つかります。その 2 組を「割り算」すると、$x^2-dy^2=1$ の解が出てきます。

証明の数え上げの理由を先に述べます。値 $k$ は $4d$ 通り、$|k|$ で割った余りの組は $|k|^2\le4d^2$ 通りです。したがって $4d\cdot4d^2=16d^3$ を超える数の組を用意すれば、鳩の巣原理を 2 回使って、同じ値・同じ余りの 2 組が見つかります。また、ステップ 3 の $X,Y$ は、$(x+y\sqrt d)$ と $(x'-y'\sqrt d)$ の積 $X+Y\sqrt d$ の係数で、積の $N$ は $k\cdot k=k^2$ になります。これを $k$ で割って $N=1$ の解を得る、という見通しです。

補題 7.1（Dirichlet の近似定理）✓

$\alpha>0$ を実数、$Q$ を正の整数とする。整数 $p$ と、$1\le q\le Q$ を満たす整数 $q$ で

$$|q\alpha-p|<\frac1Q$$

となるものが存在する。

証明（補題 7.1）

(整数部分) 実数 $t\ge0$ に対し、$t$ 以下の最大の整数 $\lfloor t\rfloor$ があることを確かめる。アルキメデスの原理（命題 5.4）［数とは何か］ の (1) により $n>t$ となる自然数 $n$ がある。整数 $m$ で $0\le m\le t$ を満たすものの集合は $0$ を含み、その元はすべて $n$ より小さいので、$0,1,\dots,n-1$ のうちの空でない有限集合であり、最大元 $\lfloor t\rfloor$ をもつ。最大性から $\lfloor t\rfloor+1>t$ なので $0\le t-\lfloor t\rfloor<1$。 (鳩の巣) $k=0,1,\dots,Q$ について $f_k=k\alpha-\lfloor k\alpha\rfloor$ とおく（$k\alpha\ge0$）。$0\le f_k<1$ なので $0\le Qf_k<Q$ で、$j_k=\lfloor Qf_k\rfloor$ は $\{0,1,\dots,Q-1\}$ の元である。$Q+1$ 個の $k$ を $Q$ 個の値 $j_k$ に写す写像は、鳩の巣原理（定理 7.5）［数え上げと母関数］ の 1.（定理中の整数を $1$ とした場合）により単射でない。よって $0\le k<l\le Q$ で $j_k=j_l=j$ となるものがある。$j\le Qf_k<j+1$、$j\le Qf_l<j+1$ なので $|Qf_l-Qf_k|<1$、すなわち $|f_l-f_k|<\dfrac1Q$。 $q=l-k$、$p=\lfloor l\alpha\rfloor-\lfloor k\alpha\rfloor$ とおくと、$1\le q\le Q$ で $q\alpha-p=(l\alpha-\lfloor l\alpha\rfloor)-(k\alpha-\lfloor k\alpha\rfloor)=f_l-f_k$。ゆえに $|q\alpha-p|<\dfrac1Q$。

∎

補題 7.2（√d のよい近似分数はいくらでもある）✓

$d\ge2$ を平方数でない整数とする。どんな正の整数 $M$ に対しても、

$$|x-y\sqrt d|<\frac1y$$

を満たす正の整数の組 $(x,y)$ で、互いに異なるものが $M$ 個以上ある。

証明（補題 7.2）

まず 2 つのことに注意する。(i) 正の整数 $x,y$ について $x-y\sqrt d\ne0$。実際 $x=y\sqrt d$ なら $\sqrt d=x/y$ が有理数になり、系 7.7［証明の技術］ に反する。(ii) $\sqrt d>1$。$\sqrt d\le1$ なら $d=(\sqrt d)^2\le1$ となり $d\ge2$ に反する。 $M$ についての帰納法で示す。 ($M=1$) 補題 7.1 を $\alpha=\sqrt d$、$Q=1$ に使うと、$q=1$ と整数 $p$ で $|p-\sqrt d|<1$ となるものがある。(ii) より $p>\sqrt d-1>0$ なので $p$ は正の整数で、$(x,y)=(p,1)$ は $|x-y\sqrt d|<1=1/y$ を満たす。 ($M$ から $M+1$ へ) 条件を満たす相異なる $M$ 個の組 $(x_1,y_1),\dots,(x_M,y_M)$ があるとする。(i) より $\delta=\min_i|x_i-y_i\sqrt d|>0$。アルキメデスの原理（命題 5.4）［数とは何か］ の (2) で $\dfrac1Q<\delta$ となる正の整数 $Q$ をとり、補題 7.1 を $\alpha=\sqrt d$ とこの $Q$ に使って、$1\le q\le Q$ と整数 $p$ で $|q\sqrt d-p|<\dfrac1Q$ となるものをとる。

• $q\le Q$ なので $|p-q\sqrt d|<\dfrac1Q\le\dfrac1q$。
• $p>q\sqrt d-1\ge\sqrt d-1>0$（(ii)）なので $p$ は正の整数。
• $|p-q\sqrt d|<\dfrac1Q<\delta\le|x_i-y_i\sqrt d|$ なので、$(p,q)$ はどの $(x_i,y_i)$ とも異なる。

よって $(p,q)$ を加えた $M+1$ 個の相異なる組が条件を満たす。

∎

定理 7.3（Pell 方程式の解の存在）✓

$d\ge2$ を平方数でない整数とする。$x^2-dy^2=1$ は正の整数解（$x\ge1$、$y\ge1$）をもつ。

証明（定理 7.3）

(ステップ 1：値の範囲) 補題 7.2 の条件 $|x-y\sqrt d|<1/y$ を満たす正の整数の組 $(x,y)$ について、$k=x^2-dy^2$ は $0$ でなく（補題 7.2 の証明の (i) と同じく、$k=0$ なら $\sqrt d=x/y$ が有理数になり 系 7.7［証明の技術］ に反する）、

$$0<x+y\sqrt d=(x-y\sqrt d)+2y\sqrt d<\frac1y+2y\sqrt d$$

なので

$$|k|=|x-y\sqrt d|\,(x+y\sqrt d)<\frac1y\Bigl(\frac1y+2y\sqrt d\Bigr)=\frac1{y^2}+2\sqrt d\le1+2\sqrt d .$$

さらに $\sqrt d<d$ である（$\sqrt d\ge d$ なら $d=(\sqrt d)^2\ge d^2$ となり、$d\ge2$ に反する）。よって $|k|<1+2d$ で、$k$ は整数だから $1\le|k|\le2d$。すなわち $k$ は $4d$ 個の元からなる集合 $K=\{-2d,\dots,-1,1,\dots,2d\}$ に属する。 (ステップ 2：同じ値・同じ余りの 2 組) 補題 7.2 で、条件を満たす相異なる組を $16d^3+1$ 個とり、その集合を $A$ とする。$A$ の各組に $x^2-dy^2\in K$ を対応させる写像は $|A|>4d^2\cdot|K|$ を満たすので、鳩の巣原理（定理 7.5）［数え上げと母関数］ の 1.（定理中の整数を $4d^2$ とした場合）により、ある $k\in K$ について $x^2-dy^2=k$ となる組が $4d^2+1$ 個以上ある。$|k|\le2d$ なので、これは $|k|^2+1$ 個以上である。これらの組に、$x$ と $y$ をそれぞれ $|k|$ で割った余りの組（$|k|^2$ 通り）を対応させると、再び鳩の巣原理の 1.（定理中の整数を $1$ とした場合）により、相異なる 2 組 $(x,y)\ne(x',y')$ で

$$x^2-dy^2=x'^2-dy'^2=k,\qquad x\equiv x',\quad y\equiv y'\pmod{|k|}$$

となるものがある（$|k|=1$ のときは合同の条件は自動的に成り立つ）。 (ステップ 3：割り算) $X=xx'-dyy'$、$Y=x'y-xy'$ とおく。命題 3.3［合同式とフェルマーの小定理］ により、$x'\equiv x$、$y'\equiv y\pmod{|k|}$ を代入して

$$X\equiv x^2-dy^2=k\equiv0,\qquad Y\equiv xy-xy=0\pmod{|k|}.$$

よって $X=ku$、$Y=kv$ となる整数 $u,v$ がある。一方、展開すると

$$\begin{aligned} X^2-dY^2&=x^2x'^2-2dxx'yy'+d^2y^2y'^2-d\bigl(x'^2y^2-2xx'yy'+x^2y'^2\bigr)\\ &=x^2x'^2-dx^2y'^2-dx'^2y^2+d^2y^2y'^2=(x^2-dy^2)(x'^2-dy'^2)=k^2 \end{aligned}$$

なので $k^2(u^2-dv^2)=k^2$、$k\ne0$ で割って $u^2-dv^2=1$。 (ステップ 4：自明でないこと) $v\ne0$ を示す。$v=0$ なら $x'y=xy'$ で、$t=x'/x$ とおくと $t>0$、$x'=tx$、$y'=ty$。すると $k=x'^2-dy'^2=t^2(x^2-dy^2)=t^2k$ で、$k\ne0$ から $t^2=1$、$t>0$ から $t=1$。これは $(x',y')=(x,y)$ を意味し、2 組が相異なることに反する。ゆえに $v\ne0$ で、$u^2=1+dv^2\ge1+d>1$ から $u\ne0$。$(|u|,|v|)$ は $x^2-dy^2=1$ の正の整数解である。

∎

この証明は解の存在を示すだけで、最小解の大きさについては何も教えてくれません（実際、最小解は小さな $d$ でも非常に大きくなることがあります。直後の注意を見てください）。存在が分かれば、すべての正の解を記述できます。

定理 7.4（Pell 方程式の解の構造）✓

$d\ge2$ を平方数でない整数とする。$x^2-dy^2=1$ の正の整数解（$x\ge1$、$y\ge1$）のうち $x$ が最小のもの（定理 7.3 と整列性により存在する）を $(x_1,y_1)$ とし、$\varepsilon=x_1+y_1\sqrt d$ とおく。各 $n\ge1$ について $\varepsilon^n=x_n+y_n\sqrt d$（$x_n,y_n$ は正の整数）とおくと、正の整数解は $(x_n,y_n)$（$n=1,2,\dots$）で尽くされ、互いに異なる。

証明（定理 7.4）

(最小解の存在) 定理 7.3 により正の整数解は少なくとも 1 つあるので、正の整数解の $x$ の値全体は正の整数の空でない部分集合であり、整列性により最小元 $x_1$ をもつ。$y_1=\sqrt{(x_1^2-1)/d}$ は $x_1$ から決まる。 ($(x_n,y_n)$ は解) $\varepsilon^n$ は積の公式から $x_n+y_n\sqrt d$（整数 $x_n,y_n$）の形で、$x_{n+1}=x_nx_1+dy_ny_1$、$y_{n+1}=x_ny_1+x_1y_n$ から帰納的に正の整数。$N(\varepsilon^n)=N(\varepsilon)^n=1$。$\varepsilon>1$ なので $\varepsilon^n$ は真に増加し、異なる解を与える。 (尽くされる) $(x,y)$ を正の解、$\eta=x+y\sqrt d$ とする。$x\ge x_1$ で $y=\sqrt{(x^2-1)/d}\ge y_1$ だから $\eta\ge\varepsilon>1$。$\varepsilon^n\to\infty$（$\varepsilon^n\ge1+n(\varepsilon-1)$）なので、$\varepsilon^n\le\eta<\varepsilon^{n+1}$ となる $n\ge1$ がある。$\varepsilon^{-1}=\bar\varepsilon=x_1-y_1\sqrt d$（$N(\varepsilon)=1$）なので $\zeta=\eta\varepsilon^{-n}=\eta\bar\varepsilon^n$ は $x'+y'\sqrt d$（整数 $x',y'$）の形で、$N(\zeta)=1$、$1\le\zeta<\varepsilon$。$\zeta=1$ なら $\eta=\varepsilon^n$ で完了。$\zeta>1$ とすると、$\bar\zeta=\zeta^{-1}\in(\varepsilon^{-1},1)\subset(0,1)$ なので $x'=\dfrac{\zeta+\bar\zeta}2>0$、$y'=\dfrac{\zeta-\bar\zeta}{2\sqrt d}>0$ は正の整数で、$(x',y')$ は正の解である。正の解では $x+y\sqrt d=x+\sqrt{x^2-1}$ は $x$ について真に増加するので、$x'+y'\sqrt d=\zeta<\varepsilon=x_1+y_1\sqrt d$ から $x'<x_1$。これは $x_1$ の最小性に反する。ゆえに $\zeta=1$。

∎

注意 7.5

解の存在の証明（定理 7.3）は、Dirichlet の近似定理（補題 7.1）と鳩の巣原理による古典的な方法です。最小解を実際に求めるには、$\sqrt d$ の連分数展開が周期的になること（Lagrange）を使う方法が実用的で、最小解は連分数の近似分数の中に現れます（Niven–Zuckerman–Montgomery, An Introduction to the Theory of Numbers, 第 7 章）。最小解は小さな $d$ でも巨大になることがあり、$d=61$ の最小解は $(x_1,y_1)=(1766319049,\,226153980)$ です。大学の代数的整数論では、$\mathbb{Q}(\sqrt d)$ の単数群が無限群であること（Dirichlet の単数定理、定理 6.1［イデアル類群の有限性と Minkowski 限界］）の最も簡単な場合として、同じ存在定理が得られます。

例 7.6（d = 2 と d = 5）

$d=2$: $3^2-2\cdot2^2=1$。$x\le2$ では解がない（$x=2$ なら $y^2=3/2$ で整数でない）ので最小解は $(3,2)$。$(3+2\sqrt2)^2=17+12\sqrt2$ より $(17,12)$、$(3+2\sqrt2)^3=99+70\sqrt2$ より $(99,70)$。前の記事の近似分数 $1,\frac32,\frac75,\frac{17}{12},\frac{41}{29},\dots$ のうち $p^2-2q^2=+1$ となるのは $\frac32,\frac{17}{12},\frac{99}{70},\dots$ です。 $d=5$: 最小解は $(9,4)$（$81-80=1$）。$(9+4\sqrt5)^2=161+72\sqrt5$ で $161^2-5\cdot72^2=25921-25920=1$。

8. 応用の例

例 8.1（何曜日になるか（万年暦））

$2026$ 年 $10$ 月 $6$ 日は火曜日です。その $100$ 日後は、$100\equiv2\pmod7$ なので火曜の $2$ 日後、木曜日。1 年後の同じ月日の曜日は、間に 2 月 29 日を含まなければ $365\equiv1\pmod7$ より $1$ 日、含めば $366\equiv2$ より $2$ 日進みます。グレゴリオ暦は $400$ 年に閏年が $97$ 回なので $400\cdot365+97=146097=7\cdot20871$ 日で、曜日の並びは $400$ 年ごとに完全に繰り返します。

例 8.2（RSA の小さな例）

$p=5$、$q=11$、$n=55$、$\varphi(n)=40$、$e=3$、$d=27$（$3\cdot27=81\equiv1\pmod{40}$）。メッセージ $m=8$ の暗号文は $8^3=512\equiv17\pmod{55}$。復号は $17^{27}\bmod55$ で、中国剰余定理（定理 4.8［合同式とフェルマーの小定理］）により法 $5$ と法 $11$ に分けて計算します。$17\equiv2\pmod5$、Fermat の小定理で $2^4\equiv1$ なので $2^{27}=2^{24}\cdot2^3\equiv8\equiv3$。$17\equiv6\pmod{11}$、$6^{10}\equiv1$ より $6^{27}\equiv6^7$、$6^2\equiv3$、$6^4\equiv9$、$6^6\equiv27\equiv5$、$6^7\equiv30\equiv8$。$x\equiv3\pmod5$、$x\equiv8\pmod{11}$ の解は $x=8$（$8\bmod5=3$）で、元のメッセージに戻りました。一般にこれが戻る理由が RSA の正当性（定理 6.1）［合同式とフェルマーの小定理］ です。

例 8.3（合同数）

辺の長さが有理数の直角三角形の面積になる正の整数を合同数といいます。$6$ は $(3,4,5)$ の面積 $\frac12\cdot3\cdot4=6$ なので合同数です。$5$ も合同数で、辺が $\frac32,\frac{20}3,\frac{41}6$ の直角三角形（$\frac94+\frac{400}9=\frac{1681}{36}$、$\frac{41}6$ の平方）の面積は $\frac12\cdot\frac32\cdot\frac{20}3=5$。どの整数が合同数かの判定は、楕円曲線の有理点の問題（Tunnell の定理）として大学で扱われます。

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

• 剰余環 $\mathbb{Z}/m\mathbb{Z}$ とその単元群、位数と Lagrange の定理は 群と部分群、合同式と RSA・中国剰余定理は 合同式と Fermat の小定理 の主題です。原始根・平方剰余・相互法則へ進みます。
• 単位円の有理点のパラメータ表示は、楕円曲線の有理点（Mordell–Weil の定理）へ（楕円曲線とモジュラー形式）。
• Pell 方程式の解の構造は、2 次体の単数群（Dirichlet の単数定理）の最も簡単な場合です。

10. 演習

演習 10.1易

$\operatorname{ord}_{13}(2)$ を求めよ。また $2^{2026}\bmod13$ を求めよ。

解答

$2^1,2^2,\dots$ を法 $13$ で計算すると $2,4,8,3,6,12,11,9,5,10,7,1$ で、$2^{12}\equiv1$ が初めてなので位数は $12$（定理 3.2 から $12$ の約数 $1,2,3,4,6$ では $1$ にならないことだけ確かめればよい）。$2026=12\cdot168+10$ なので $2^{2026}\equiv2^{10}\equiv10$（命題 3.3）。

演習 10.2標準

$\dfrac1{17}$ の循環節の長さを求めよ。

解答

$b=17$ は素数で $b'=17$。$\operatorname{ord}_{17}(10)$ は $16$ の約数。$10^2=100\equiv15\equiv-2$、$10^4\equiv4$、$10^8\equiv16\equiv-1\pmod{17}$。$10^8\not\equiv1$ なので位数は $8$ の約数ではなく、$16$ の約数で $16$ の約数のうち $8$ を割らないものは $16$ だけ。よって位数は $16$、循環節の長さは $16$（定理 5.2）。

演習 10.3標準

$(n-1)!\equiv-1\pmod n$ となる $n\le12$ をすべて求めよ。

解答

定理 4.1 より $n$ が素数のときに限るので、$n=2,3,5,7,11$。

演習 10.4難

(1) $c\le40$ の原始ピタゴラス数をすべて挙げよ。(2) $x^2-3y^2=1$ の最小解と、次の解を求めよ。

解答

(1) 定理 6.2 で $c=m^2+n^2\le40$、$m>n$、互いに素、$m-n$ 奇数。$(m,n)=(2,1),(3,2),(4,1),(4,3),(5,2),(6,1)$ が条件を満たす（$(5,4)$ は $c=41>40$ で除外、$(6,5)$ は $c=61$）。順に $(3,4,5)$、$(5,12,13)$、$(15,8,17)$、$(7,24,25)$、$(21,20,29)$、$(35,12,37)$。直角をはさむ 2 辺の順序を無視すれば $(3,4,5)$、$(5,12,13)$、$(8,15,17)$、$(7,24,25)$、$(20,21,29)$、$(12,35,37)$ の 6 組。(2) $x=2$ で $y=1$（$4-3=1$）。最小解は $(2,1)$（$x=1$ では $y=0$ となり正の解でない）。定理 7.4 より正の解は $(2+\sqrt3)^n$ で尽くされ、$x$ の小さい順に並ぶので、次の解は $(2+\sqrt3)^2=7+4\sqrt3$ より $(7,4)$（$49-48=1$）。

参考文献

1. Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991 — 第 2 章（合同式）、第 7 章（連分数と Pell 方程式）。
2. G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — 第 6 章・第 9 章（Fermat の定理と小数）。
3. Kenneth Ireland, Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990 — 第 1 章・第 2 章（整除と合同）。
4. 高木貞治『初等整数論講義』第 2 版、共立出版、1971。