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

> 倍数の判定法、位数と冪の余りの周期、Wilson の定理とその逆、有理数と循環小数・循環節の長さ、原始ピタゴラス数と単位円の有理点、Pell 方程式の解の存在と構造を合同式で証明する。
> https://rikai.mugen-giken.com/mathematics/hs-algebra/congruences

## 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 の近似定理と鳩の巣原理で証明します）、正の解は最小解の冪で尽くされます。

<Aside type="tip" title="この記事で使う事前知識">

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

</Aside>

## 1. 動機

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

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

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

整数 $a,b$ と正の整数 $m$ について、$m\mid(a-b)$ のとき $a\equiv b\pmod m$ と書きます（<Ref to="mathematics/number-theory/congruences-and-fermat#def-congruence" />）。和・差・積・冪は、合同式の両辺に使えます（<Ref to="mathematics/number-theory/congruences-and-fermat#prop-arithmetic" />）。割り算は注意が必要で、$ca\equiv cb\pmod m$ から $a\equiv b$ が言えるのは $\gcd(c,m)=1$ のときだけです（<Ref to="mathematics/number-theory/congruences-and-fermat#prop-cancellation" />）。より正確には $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$ です。

<Proposition id="prop-divisibility-tests" title="倍数の判定法">
正の整数 $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 桁で決まる。
</Proposition>

<Proof of="prop-divisibility-tests">
1. $10\equiv1\pmod9$ なので <Ref to="mathematics/number-theory/congruences-and-fermat#prop-arithmetic" /> から $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}$。
</Proof>

<Example id="ex-divisibility-1234567" title="1234567 は 7 の倍数か">
$1234567$ を 3 桁ずつに分けて $1|234|567$。交代和は $567-234+1=334$。$334=7\cdot47+5$ なので $7$ で割り切れず、余りは $5$ です（<Ref to="prop-divisibility-tests" /> の 3. は、余りまで $\pmod{1001}$ で保つので、$1234567\equiv334\pmod{1001}$、したがって $\bmod7$ で $334\equiv5$）。実際 $1234567=7\cdot176366+5$ です。
</Example>

## 3. 位数と冪の余り

<Definition id="def-order" title="位数">
$m\ge2$ を整数、$a$ を $\gcd(a,m)=1$ の整数とする。$a^k\equiv1\pmod m$ となる最小の正の整数 $k$ を、法 $m$ における $a$ の**位数**といい $\operatorname{ord}_m(a)$ と書く。
</Definition>

Euler の定理（<Ref to="mathematics/number-theory/congruences-and-fermat#thm-euler" />）から $a^{\varphi(m)}\equiv1$ なので、$k=\varphi(m)$ は条件を満たし、位数は存在します。

<Theorem id="thm-order-divides" title="位数は φ(m) を割る">
$\gcd(a,m)=1$、$d=\operatorname{ord}_m(a)$ とする。正の整数 $k$ について $a^k\equiv1\pmod m\iff d\mid k$。とくに $d\mid\varphi(m)$ である。
</Theorem>

<Proof of="thm-order-divides">
$d\mid k$ なら $k=dj$ で $a^k=(a^d)^j\equiv1^j=1$（<Ref to="mathematics/number-theory/congruences-and-fermat#prop-arithmetic" />）。逆に $a^k\equiv1$ とする。除法の原理（<Ref to="mathematics/number-theory/congruences-and-fermat#thm-division" />）で $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$。最後に <Ref to="mathematics/number-theory/congruences-and-fermat#thm-euler" text="Euler の定理" /> より $a^{\varphi(m)}\equiv1$ なので $d\mid\varphi(m)$。
</Proof>

大学では、これは群 $(\mathbb{Z}/m\mathbb{Z})^\times$ の元の位数が群の位数を割る、という Lagrange の定理の特別な場合です（<Ref to="mathematics/algebra/subgroups-and-lagrange#thm-euler-fermat" text="Euler の定理と Fermat の小定理" />）。

<Proposition id="prop-power-period" title="冪の余りの周期">
$\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$ である。
</Proposition>

<Proof of="prop-power-period">
$k\ge l$ とする。$\gcd(a,m)=1$ なので <Ref to="mathematics/number-theory/congruences-and-fermat#prop-cancellation" /> により $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$ は <Ref to="thm-order-divides" /> から $d\mid(k-l)$ と同値。
</Proof>

<Example id="ex-power-last-digits" title="冪の下 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 の小定理（<Ref to="mathematics/number-theory/congruences-and-fermat#thm-fermat-little" />）を使って $7^{100}\bmod13$ を計算すると、$7^{12}\equiv1$ より $7^{100}=7^{96}\cdot7^4\equiv7^4=2401\equiv9$（$2401=13\cdot184+9$）です。
</Example>

## 4. Wilson の定理

<Theorem id="thm-wilson" title="Wilson の定理とその逆">
$n\ge2$ を整数とする。$n$ が素数であることと、$(n-1)!\equiv-1\pmod n$ であることは同値である。
</Theorem>

素数 $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$ だけであることを示すのが、証明の要点です。

<Proof of="thm-wilson">
(素数ならば) $n=p$ が素数とする。$p=2$ のとき $1!=1\equiv-1\pmod2$。$p\ge3$ とする。$1,\dots,p-1$ の各 $a$ は $\gcd(a,p)=1$ なので <Ref to="mathematics/number-theory/congruences-and-fermat#prop-unit-criterion" /> により法 $p$ の逆元 $a'$（$aa'\equiv1$）が $\{1,\dots,p-1\}$ の中にただ 1 つある。$a'=a$、すなわち $a^2\equiv1$ のとき $p\mid(a-1)(a+1)$ で、<Ref to="mathematics/number-theory/primes-and-prime-number-theorem#lem-euclid-lemma" text="素数に関する Euclid の補題" /> から $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$。
</Proof>

<Example id="ex-wilson-use" title="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)!$ の計算が重すぎて実用になりませんが、「合成数でも素数でも、階乗の余りがこれほど鮮やかに分かれる」ことを示しています。
</Example>

## 5. 有理数と循環小数

実数 $0\le x<1$ の小数展開 $0.d_1d_2d_3\cdots$ とは、部分和 $s_n=\sum_{k\le n}d_k10^{-k}$ の上限が $x$ であることをいいます（<Ref to="mathematics/foundations/what-is-a-number#def-decimal" />）。有理数 $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\}$）。

<Theorem id="thm-rational-decimal" title="有理数と循環小数">
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}$ の値は有理数である。
</Theorem>

<Proof of="thm-rational-decimal">
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$ に対し <Ref to="mathematics/foundations/what-is-a-number#prop-archimedes" text="アルキメデスの原理" /> で $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$ 個の値をとるので、<Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-pigeonhole" text="鳩の巣原理" /> によりある $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)}$（等比級数、<Ref to="mathematics/foundations/what-is-a-number#prop-geometric" />）。したがって値は $A+\dfrac C{10^s(10^t-1)}$ で、有理数。
</Proof>

<Theorem id="thm-period-order" title="循環節の長さは 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)$ である。
</Theorem>

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

<Proof of="thm-period-order">
1. $b'=1$ なら $10^m\dfrac ab=a\cdot2^{m-\alpha}5^{m-\beta}$ は整数なので、展開は小数第 $m$ 位までで終わる（<Ref to="thm-rational-decimal" /> の手順で、$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$）とおく。一方、<Ref to="thm-rational-decimal" /> の証明の式から $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$ なので <Ref to="mathematics/number-theory/congruences-and-fermat#prop-cancellation" /> で $c$ を消去して）$10^k\equiv1\pmod{b'}$ のときで、これは <Ref to="thm-order-divides" /> から $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$ だから <Ref to="mathematics/number-theory/elementary-number-theory#lem-euclid-general" /> により $b'\mid10^\ell-1$、すなわち $10^\ell\equiv1\pmod{b'}$ で $L\mid\ell$。ゆえに $\ell\ge L$ で、最小の周期は $L$。
</Proof>

<Example id="ex-recurring-decimals" title="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$ はその例）。
</Example>

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

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

<Lemma id="lem-coprime-square" title="互いに素な数の積が平方数なら、それぞれ平方数">
$u,v$ を互いに素な正の整数とし、$uv$ が平方数ならば、$u$ も $v$ も平方数である。
</Lemma>

<Proof of="lem-coprime-square">
$uv=w^2$ とする。素数 $p$ について $v_p(u)+v_p(v)=v_p(uv)=2v_p(w)$（<Ref to="mathematics/number-theory/elementary-number-theory#prop-valuation-rules" /> の 1.）は偶数。$u,v$ は互いに素なので、どの素数 $p$ も両方を割ることはなく、$v_p(u)$ と $v_p(v)$ の少なくとも一方は $0$。したがって他方は偶数で、$v_p(u),v_p(v)$ はともに偶数。$u=\prod p^{v_p(u)}$（<Ref to="mathematics/number-theory/elementary-number-theory#thm-unique-factorization" />）なので $u=\bigl(\prod p^{v_p(u)/2}\bigr)^2$、$v$ も同様。
</Proof>

<Theorem id="thm-pythagorean-triples" title="原始ピタゴラス数">
$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)$ は原始ピタゴラス数である。
</Theorem>

<Proof of="thm-pythagorean-triples">
$(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$。<Ref to="lem-coprime-square" /> から $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$ から決まるため。
</Proof>

$(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$ に並べ替えれば上の形）。

<Corollary id="cor-rational-points" title="単位円上の有理点">
単位円 $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$ からこの式で得られる点は単位円上の有理点である。
</Corollary>

<Proof of="cor-rational-points">
$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$ が展開で確かめられ、点は単位円上にある。
</Proof>

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

<Figure caption="点 (-1, 0) から傾き 1/2 の直線を引くと、円との 2 つ目の交点は (3/5, 4/5)。傾きが有理数なら、交点も有理点になる。">
<svg viewBox="0 0 400 280" width="100%" role="img" aria-label="単位円と、点 (-1,0) を通る傾き 1/2 の直線。直線は円と (3/5, 4/5) で再び交わる。">
<line x1="60" y1="140" x2="340" y2="140" stroke="currentColor" stroke-width="1" opacity="0.4" />
<line x1="200" y1="20" x2="200" y2="260" stroke="currentColor" stroke-width="1" opacity="0.4" />
<circle cx="200" cy="140" r="100" fill="none" stroke="currentColor" stroke-width="2" />
<line x1="100" y1="140" x2="330" y2="25" stroke="var(--sl-color-accent)" stroke-width="2" />
<circle cx="100" cy="140" r="4" fill="currentColor" />
<circle cx="260" cy="60" r="4" fill="var(--sl-color-accent)" />
<text x="62" y="162" font-size="14" fill="currentColor">(-1, 0)</text>
<text x="292" y="90" font-size="14" fill="currentColor">P = (3/5, 4/5)</text>
<text x="215" y="22" font-size="14" fill="var(--sl-color-accent)">傾き t = 1/2</text>
</svg>
</Figure>

## 7. Pell 方程式

$d\ge2$ を平方数でない整数とします。$x^2-dy^2=1$ の整数解を調べます。$\sqrt d>0$ は存在します（$f(x)=x^2-d$ は $f(1)<0<f(d)$ なので <Ref to="mathematics/calculus/limits-and-continuity#thm-ivt" text="中間値の定理" /> による）。$\sqrt d$ は無理数（<Ref to="mathematics/foundations/proof-techniques#cor-sqrt-nonsquare" />）なので、整数 $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$ の解を得る、という見通しです。

<Lemma id="lem-dirichlet-approx" title="Dirichlet の近似定理">
$\alpha>0$ を実数、$Q$ を正の整数とする。整数 $p$ と、$1\le q\le Q$ を満たす整数 $q$ で
$$
|q\alpha-p|<\frac1Q
$$
となるものが存在する。
</Lemma>

<Proof of="lem-dirichlet-approx">
(整数部分) 実数 $t\ge0$ に対し、$t$ 以下の最大の整数 $\lfloor t\rfloor$ があることを確かめる。<Ref to="mathematics/foundations/what-is-a-number#prop-archimedes" text="アルキメデスの原理" /> の (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$ に写す写像は、<Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-pigeonhole" text="鳩の巣原理" /> の 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$。
</Proof>

<Lemma id="lem-pell-many-approx" title="√d のよい近似分数はいくらでもある">
$d\ge2$ を平方数でない整数とする。どんな正の整数 $M$ に対しても、
$$
|x-y\sqrt d|<\frac1y
$$
を満たす正の整数の組 $(x,y)$ で、互いに異なるものが $M$ 個以上ある。
</Lemma>

<Proof of="lem-pell-many-approx">
まず 2 つのことに注意する。(i) 正の整数 $x,y$ について $x-y\sqrt d\ne0$。実際 $x=y\sqrt d$ なら $\sqrt d=x/y$ が有理数になり、<Ref to="mathematics/foundations/proof-techniques#cor-sqrt-nonsquare" /> に反する。(ii) $\sqrt d>1$。$\sqrt d\le1$ なら $d=(\sqrt d)^2\le1$ となり $d\ge2$ に反する。
$M$ についての帰納法で示す。
($M=1$) <Ref to="lem-dirichlet-approx" /> を $\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$。<Ref to="mathematics/foundations/what-is-a-number#prop-archimedes" text="アルキメデスの原理" /> の (2) で $\dfrac1Q<\delta$ となる正の整数 $Q$ をとり、<Ref to="lem-dirichlet-approx" /> を $\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$ 個の相異なる組が条件を満たす。
</Proof>

<Theorem id="thm-pell-existence" title="Pell 方程式の解の存在">
$d\ge2$ を平方数でない整数とする。$x^2-dy^2=1$ は正の整数解（$x\ge1$、$y\ge1$）をもつ。
</Theorem>

<Proof of="thm-pell-existence">
(ステップ 1：値の範囲) <Ref to="lem-pell-many-approx" /> の条件 $|x-y\sqrt d|<1/y$ を満たす正の整数の組 $(x,y)$ について、$k=x^2-dy^2$ は $0$ でなく（<Ref to="lem-pell-many-approx" /> の証明の (i) と同じく、$k=0$ なら $\sqrt d=x/y$ が有理数になり <Ref to="mathematics/foundations/proof-techniques#cor-sqrt-nonsquare" /> に反する）、
$$
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 組) <Ref to="lem-pell-many-approx" /> で、条件を満たす相異なる組を $16d^3+1$ 個とり、その集合を $A$ とする。$A$ の各組に $x^2-dy^2\in K$ を対応させる写像は $|A|>4d^2\cdot|K|$ を満たすので、<Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-pigeonhole" text="鳩の巣原理" /> の 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'$ とおく。<Ref to="mathematics/number-theory/congruences-and-fermat#prop-arithmetic" /> により、$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$ の正の整数解である。
</Proof>

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

<Theorem id="thm-pell-solutions" title="Pell 方程式の解の構造">
$d\ge2$ を平方数でない整数とする。$x^2-dy^2=1$ の正の整数解（$x\ge1$、$y\ge1$）のうち $x$ が最小のもの（<Ref to="thm-pell-existence" /> と[整列性](/mathematics/foundations/proof-techniques#ax-well-ordering)により存在する）を $(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$）で尽くされ、互いに異なる。
</Theorem>

<Proof of="thm-pell-solutions">
(最小解の存在) <Ref to="thm-pell-existence" /> により正の整数解は少なくとも 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$。
</Proof>

<Remark id="rem-pell-existence">
解の存在の証明（<Ref to="thm-pell-existence" />）は、Dirichlet の近似定理（<Ref to="lem-dirichlet-approx" />）と鳩の巣原理による古典的な方法です。最小解を実際に求めるには、$\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 の単数定理、<Ref to="mathematics/number-theory/class-group-and-minkowski-bound#thm-dirichlet-unit" />）の最も簡単な場合として、同じ存在定理が得られます。
</Remark>

<Example id="ex-pell-d2-d5" title="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$。
</Example>

## 8. 応用の例

<Example id="ex-weekday" title="何曜日になるか（万年暦）">
$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$ 年ごとに完全に繰り返します。
</Example>

<Example id="ex-rsa-toy" title="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$ で、中国剰余定理（<Ref to="mathematics/number-theory/congruences-and-fermat#thm-crt" />）により法 $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$）で、元のメッセージに戻りました。一般にこれが戻る理由が <Ref to="mathematics/number-theory/congruences-and-fermat#thm-rsa" text="RSA の正当性" /> です。
</Example>

<Example id="ex-congruent-number" title="合同数">
辺の長さが有理数の直角三角形の面積になる正の整数を**合同数**といいます。$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 の定理）として大学で扱われます。
</Example>

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

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

## 10. 演習

<Exercise id="exr-order-13" difficulty="易">
$\operatorname{ord}_{13}(2)$ を求めよ。また $2^{2026}\bmod13$ を求めよ。
<Solution>
$2^1,2^2,\dots$ を法 $13$ で計算すると $2,4,8,3,6,12,11,9,5,10,7,1$ で、$2^{12}\equiv1$ が初めてなので位数は $12$（<Ref to="thm-order-divides" /> から $12$ の約数 $1,2,3,4,6$ では $1$ にならないことだけ確かめればよい）。$2026=12\cdot168+10$ なので $2^{2026}\equiv2^{10}\equiv10$（<Ref to="prop-power-period" />）。
</Solution>
</Exercise>

<Exercise id="exr-decimal-17" difficulty="標準">
$\dfrac1{17}$ の循環節の長さを求めよ。
<Solution>
$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$（<Ref to="thm-period-order" />）。
</Solution>
</Exercise>

<Exercise id="exr-wilson-converse" difficulty="標準">
$(n-1)!\equiv-1\pmod n$ となる $n\le12$ をすべて求めよ。
<Solution>
<Ref to="thm-wilson" /> より $n$ が素数のときに限るので、$n=2,3,5,7,11$。
</Solution>
</Exercise>

<Exercise id="exr-pythagorean-pell" difficulty="難">
(1) $c\le40$ の原始ピタゴラス数をすべて挙げよ。(2) $x^2-3y^2=1$ の最小解と、次の解を求めよ。
<Solution>
(1) <Ref to="thm-pythagorean-triples" /> で $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$ となり正の解でない）。<Ref to="thm-pell-solutions" /> より正の解は $(2+\sqrt3)^n$ で尽くされ、$x$ の小さい順に並ぶので、次の解は $(2+\sqrt3)^2=7+4\sqrt3$ より $(7,4)$（$49-48=1$）。
</Solution>
</Exercise>

## 参考文献

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。