初等整数論

同義語：初等数論elementary number theory

概要

前提知識: 整数, 素数, 最大公約数, 合同式

初等整数論（elementary number theory）は、整数の性質を、割り算・最大公約数・素因数分解・合同式といった整数そのものの道具で調べる数論の分野である。整数全般を扱う数論のうち、複素関数論（解析的整数論）や代数体の整数環のイデアル（代数的整数論）を持ち込まずに進める部分を指す。この記事は分野の入口として、何を問い、どんな道具を使い、どこから先が別の分野になるのかをまとめ、あわせてこの分野らしい基本事実をいくつか完全に証明する。

定義

初等整数論

初等整数論とは、整数（および有理数）についての問い――整除関係、素数と素因数分解、合同式とその解、整数係数の方程式の整数解、数論的関数の値――を、次の道具を中心に研究する数論の分野である。
(i) 整数の順序と整列性（帰納法、最小の元の存在）。
(ii) 除法の原理、最大公約数、Euclid の互除法と Bézout の等式。
(iii) 素因数分解の一意性。
(iv) 合同式、すなわち剰余環 $\mathbb Z/n\mathbb Z$ での計算と、その乗法群の性質。
(v) 数え上げと、実数の初等的な評価（複素関数論を使わないもの）。

「初等的」は「易しい」という意味ではない。Moser の教科書の序文は、「初等的」を複素関数論を使わないことと、分かりやすいことの両方の意味で使うと述べている（Mos57 Preface、p. v）。前者の意味では、初等的でもきわめて難しい証明がある。素数定理には複素関数論を使わない証明が 1949 年ごろ Erdős と Selberg によって与えられ、大きな話題になった（Mos57 第 3 章、p. 26）。したがって分野の境界は、使う道具によって引かれる。

直感

整数は飛び飛びの値しかとらないので、実数の方程式のように連続的に解を動かすことができない。その代わり、整数には「割り切れる」という関係があり、これが強い制約を生む。初等整数論の基本の型は次の 3 つである。

余りで見る：整数 $n$ で割った余りだけを見ると、無限の問題が有限個の場合分けになる。$x^2\equiv-1\pmod 3$ が解をもたないことから、$x^2-3y^2=-1$ が整数解をもたないことが分かる（$x^2-3y^2\equiv x^2\pmod 3$ で、$x^2\bmod3$ は $0,1$ のどちらか）。
素数に分ける：素因数分解の一意性により、掛け算の問題は各素数の指数の足し算の問題になる。
うまい数を作る：Euclid が素数の無限性を示したように、既知の素数のどれでも割り切れない数を作って新しい素数を見つける。
以下の節で、この 3 つの型がどう組み合わさるかを具体的な定理で見る。

基本の道具

初等整数論の議論は、次の少数の基本事実の上に組み立てられる。いずれも Mathpedia のそれぞれの記事で証明されているので、ここでは主張と役割だけを述べる。

除法の原理：整数 $a$ と正の整数 $b$ について、$a=qb+r$、$0\le r< b$ となる整数 $q,r$ がただ 1 組ある（除法の原理）。「余り」という概念の出発点であり、合同式・互除法・$m$ 進表記のすべてがここから生じる。
最大公約数と Bézout の等式：$a,b$ の最大公約数 $d$ は $d=ax+by$（$x,y$ は整数）と書ける（Bézoutの等式）。$x,y$ は Euclidの互除法を逆にたどって具体的に求まる。$\gcd(a,n)=1$ なら $ax\equiv1\pmod n$ となる $x$ があり、法 $n$ で $a$ による割り算ができる（合同式の割り算と逆元）。
素数の基本性質と素因数分解の一意性：素数 $p$ が積 $ab$ を割り切れば $p\mid a$ または $p\mid b$ である。これは 2 から従う（$p\nmid a$ なら $\gcd(a,p)=1$ で $1=ax+py$、両辺に $b$ を掛けると $b=abx+pby$ は $p$ で割り切れる）。ここから $1$ より大きい整数の素因数分解が順序を除いて一意であることが導かれる（素因数分解の一意性）。
合同式は環の計算：$a\equiv b$、$c\equiv d\pmod n$ なら $a+c\equiv b+d$、$ac\equiv bd$ である（合同式の計算規則）。すなわち整数を法 $n$ の剰余類に送る写像 $\mathbb Z\to\mathbb Z/n\mathbb Z$ は和と積を保ち、整数の等式は各法での合同式に写る。
有限群としての見方：$n$ と互いに素な剰余類は掛け算で群をなし、その位数は $\varphi(n)$ である。Lagrange の定理から、$\gcd(a,n)=1$ なら $a^{\varphi(n)}\equiv1\pmod n$（Eulerの定理(整数論)）、とくに素数 $p$ と $p\nmid a$ について $a^{p-1}\equiv1\pmod p$（Fermatの小定理）が従う（既約剰余類群）。

余りで見る：$n^5-n$ は $30$ の倍数

すべての整数 $n$ について $30\mid n^5-n$ である。$30=2\cdot3\cdot5$ なので、$2,3,5$ のそれぞれで割り切れることを示せば、素因数分解の一意性（互いに素な数がどちらも割り切るなら積も割り切る）から $30$ で割り切れる。素数 $p\in\{2,3,5\}$ について、Fermat の小定理を $p\nmid n$ の場合に使うと $n^p\equiv n\pmod p$（$p\mid n$ なら両辺とも $0$）である。$p=5$ では直接 $n^5\equiv n$。$p=3$ では $n^5=n^3\cdot n^2\equiv n\cdot n^2=n^3\equiv n$。$p=2$ では $n^5\equiv n^4\cdot n$ で、$n^2\equiv n$ を繰り返して $n^5\equiv n$ である。

素数に分ける：素因数の指数を比べる

$a^2=2b^2$ を満たす正の整数 $a,b$ はない。両辺の素因数分解で $2$ の指数を比べると、左辺では $2v_2(a)$ で偶数、右辺では $1+2v_2(b)$ で奇数になり、素因数分解の一意性に反するからである（$v_2(m)$ は $m$ を割り切る $2$ の最高冪の指数）。これは $\sqrt2$ が無理数であることの言い換えである。同じ議論で、正の整数 $n$ の平方根が有理数になるのは $n$ が平方数のときに限ることが分かる（p進付値の記事の付値の基本性質を各素数に使う）。

主な話題と記事の地図

初等整数論の標準的な話題と、それぞれの中心になる主張、Mathpedia の記事を並べる。

話題	代表的な主張	記事
整除と最大公約数	除法の原理、互除法、Bézout の等式	除法の原理, Euclidの互除法, Bézoutの等式
素数と素因数分解	素因数分解の一意性、素数の無限性	素因数分解の一意性, 素数の無限性
合同式	合同式の計算、1 次合同式、中国剰余定理	合同式, 合同式の割り算と逆元, 中国剰余定理
乗法の構造	Fermat の小定理、Euler の定理、Wilson の定理、原始根	Fermatの小定理, Eulerの定理(整数論), Wilsonの定理, 原始根, 既約剰余類群
平方剰余	Euler の規準、平方剰余の相互法則	平方剰余, 平方剰余の相互法則
数論的関数	$\varphi$ の乗法性、Möbius の反転公式	Eulerのφ関数, Möbiusの反転公式, 約数の個数と約数の総和
不定方程式	ピタゴラス数、Pell 方程式、二平方・四平方定理	ピタゴラス数, Pell方程式, Fermatの二平方定理, Lagrangeの四平方定理
素数の分布（初等的な評価）	素数の逆数和の発散、Chebyshev 型の評価、Bertrand の仮説	素数の無限性, Bertrandの仮説, 素数計数関数

表の各行の主張は、それぞれの記事で証明されている。この記事では、それらを組み合わせて得られる次の事実を証明する。

代表的な基本事実

多項式の値は素数だけにはならない

$n^2+n+41$ は $n=0,1,\dots,39$ で素数になる。どこまでも素数を出し続ける整数係数の多項式はあるだろうか。答えは「定数でなければない」である。

素数だけを値にとる多項式は定数

$f(x)$ を整数係数の多項式とする。すべての正の整数 $n$ について $f(n)$ が素数なら、$f$ は定数である。

1 つの素数の倍数の位置で値が固定される

$p=f(1)$ とおくと、仮定から $p$ は素数である。各正の整数 $k$ について $1+kp\equiv1\pmod p$ なので、整数係数の多項式は合同を保つこと（$a\equiv b$ なら $a^i\equiv b^i$、係数を掛けて足しても合同。合同式の計算規則）から
$$ f(1+kp)\equiv f(1)=p\equiv0\pmod p $$
である。$f(1+kp)$ は素数で $p$ で割り切れるので、$f(1+kp)=p$ である。よって多項式 $f(x)-p$ は無限に多くの整数 $1+p,1+2p,1+3p,\dots$ を根にもつ。$0$ でない多項式の根は次数以下の個数しかないので、$f(x)-p$ は $0$ 多項式であり、$f$ は定数 $p$ である。

この証明は、型 1「余りで見る」と型 3「うまい数を作る」の組み合わせである。$f(x)=x^2+x+41$ では $f(40)=40^2+40+41=41^2$ が合成数になる。証明どおり、$f(1)=43$ とすれば $f(1+43k)$ はすべて $43$ の倍数で、$f(44)=44^2+44+41=2021=43\cdot47$ である。

$x^2+x+1$ の素因数

$x^2+x+1$ を割る素数

整数 $x$ と素数 $q$ について $q\mid x^2+x+1$ なら、$q=3$ または $q\equiv1\pmod 3$ である。

$x$ の法 $q$ での位数は $3$

$x^3-1=(x-1)(x^2+x+1)$ なので $x^3\equiv1\pmod q$ である。とくに $q\nmid x$ で、$x$ の法 $q$ での位数 $d$（$x^d\equiv1$ となる最小の正の整数）は $3$ の約数、すなわち $1$ か $3$ である。
$d=1$ なら $x\equiv1\pmod q$ で、$x^2+x+1\equiv3\pmod q$ なので $q\mid3$、すなわち $q=3$ である。
$d=3$ なら、Fermatの小定理により $x^{q-1}\equiv1\pmod q$ である。$q-1=3s+r$（$0\le r<3$）と割ると、$x$ は法 $q$ で逆元をもつので $x^r\equiv x^{q-1}(x^3)^{-s}\equiv1$ となり、$0\le r<3=d$ と位数の最小性から $r=0$ である（同じ議論の一般形は冪の余りの周期と元の位数の記事の定理「位数と指数の関係」）。よって $3\mid q-1$ である。

$x^2+1$ についての同じ形の主張（奇素数 $q\mid x^2+1$ なら $q\equiv1\pmod4$）は、$-1$ が法 $q$ の平方剰余になることの言い換えであり、平方剰余の記事の系「−1 が平方剰余となる素数」から従う。$x^2+x+1$ と $x^2+1$ はそれぞれ $1$ の原始 $3$ 乗根・原始 $4$ 乗根を根にもつ多項式（円分多項式）であり、「円分多項式の値の素因数は、合同条件で制限される」というのが両者に共通する仕組みである。

3 で割って 1 余る素数は無限に多い

3 で割って 1 余る素数の無限性

$3$ で割って $1$ 余る素数は無限に多い。同じことだが、$6$ で割って $1$ 余る素数は無限に多い。

$x^2+x+1$ に既知の素数の積を代入する

$3$ で割って $1$ 余る素数が有限個 $p_1,\dots,p_k$ しかないと仮定する（$k=0$ でもよい）。$x=3p_1\cdots p_k$ とおき、$N=x^2+x+1$ とする。$N>1$ なので $N$ は素因数 $q$ をもつ。lem-ent-cyclotomic-three により $q=3$ または $q\equiv1\pmod3$ である。
$q=3$ ではない。$3\mid x$ なので $N\equiv1\pmod 3$ だからである。したがって $q\equiv1\pmod3$ であり、仮定から $q$ はある $p_i$ に等しい。ところが $p_i\mid x$ なので $N\equiv1\pmod{p_i}$ となり、$p_i\nmid N$ である。これは $q\mid N$ に反する。よって $3$ で割って $1$ 余る素数は無限に多い。
$3$ で割って $1$ 余る素数は $2$ でないので奇数であり、$3$ で割って $1$ 余る奇数は $6$ で割って $1$ 余る。

証明の構成を実際に行う

既知の素数がない状態（$k=0$）から始めると $x=3$、$N=13$ で、素数 $13\equiv1\pmod3$ が得られる。次に $x=3\cdot13=39$ とすると $N=39^2+39+1=1561=7\cdot223$ で、$7\equiv1$、$223\equiv1\pmod 3$ の 2 つの新しい素数が得られる。どちらの素因数も、補題のとおり $3$ で割って $1$ 余っている。

残りの剰余類 $2\bmod 3$ については、多項式を使わない Euclid 型の論法がそのまま通る。

3 で割って 2 余る素数の無限性

$3$ で割って $2$ 余る素数は無限に多い。

3 倍して 1 を引く

$3$ で割って $2$ 余る素数が有限個 $p_1,\dots,p_k$ しかないと仮定し（$p_1=2$ を含む）、$N=3p_1\cdots p_k-1$ とおく。$N\ge5$ で $N\equiv2\pmod3$ である。$N$ の素因数は $3$ でなく（$N\equiv2$）、どの $p_i$ でもない（$N\equiv-1\pmod{p_i}$）。したがって仮定から、$N$ の素因数はすべて $3$ で割って $1$ 余る。ところが $3$ で割って $1$ 余る数の積は $3$ で割って $1$ 余るので、$N\equiv1\pmod3$ となり矛盾する。

この論法が $1\bmod 3$ の側で使えないのは、$2\cdot5=10\equiv1\pmod3$ のように、$2\bmod 3$ の素数の積が $1\bmod3$ になりうるからである。$1\bmod3$ の側では、素因数が「$3$ か $1\bmod 3$」に制限される数 $x^2+x+1$ を使うことで、この障害を回避した。同じ論法で、$4$ で割って $3$ 余る素数（素数の無限性の記事の命題「4 で割って 3 余る素数の無限性」）、$4$ で割って $1$ 余る素数（平方剰余の記事の命題「4 で割って 1 余る素数の無限性」）も無限に多いことが示せる。一般に、$\gcd(a,m)=1$ なら $a,a+m,a+2m,\dots$ の中に素数が無限に多くある（Dirichlet の算術級数定理、Ste17 Theorem 1.2.7、p. 14）。この一般形はこの記事では証明しない。標準的な証明は Dirichlet 指標と $L$ 関数を使う解析的なもので、初等整数論の道具の外にある。

例と反例

余りによる不可能性の証明

$x^2+y^2=4k+3$、$x^2-3y^2=-1$、$x^2+y^2+z^2=8k+7$ はどれも整数解をもたない。法 $4$、法 $3$、法 $8$ で平方数がとりうる余りを列挙すればよい（法 $8$ の平方数の余りは $0,1,4$ で、3 つの和は $7$ にならない）。どれも「法 $m$ で解がなければ整数解もない」という型で、その逆は一般に成り立たない。

次の表は、素数や合同式について成り立ちそうに見えて成り立たない推論を、条件を外した反例で示したものである。

外す条件・誤った推論	反例	成り立たなくなること
$f$ が定数でない多項式でも素数だけを値にとる	$f(n)=n^2+n+41$、$n=40$	$f(40)=41^2$ は合成数
$4$ で割って $1$ 余る素数に Euclid の論法をそのまま使う	$3\cdot7=21\equiv1\pmod4$	「$4k+1$ 型の数は $4k+1$ 型の素因数をもつ」
素数 $p$ についての $a^{p-1}\equiv1$ の逆	$341=11\cdot31$、$a=2$	$2^{340}\equiv1\pmod{341}$ だが $341$ は素数でない
補題の結論から例外 $q=3$ を外した推論「$q\mid x^2+x+1$ なら $q\equiv1\pmod3$」	$x=1$、$x^2+x+1=3$	$q\equiv1\pmod3$（$q=3$ は $3\equiv0\pmod3$）
法 $m$ で解があれば整数解がある	$x^2\equiv2\pmod 7$ は解 $3$ をもつ	$x^2=2$ の整数解の存在

反例：Fermat の小定理の逆は成り立たない

$2^{10}=1024=3\cdot341+1$ なので $2^{10}\equiv1\pmod{341}$ であり、$2^{340}=(2^{10})^{34}\equiv1\pmod{341}$ である。しかし $341=11\cdot31$ は合成数である。この例は含意「$\gcd(a,n)=1$ かつ $a^{n-1}\equiv1\pmod n$ ならば $n$ は素数」を破る。さらに、$n$ と互いに素なすべての $a$ でこの合同式が成り立つ合成数（Carmichael 数、最小は $561$）もある（既約剰余類群の記事の命題「Carmichael 関数による判定」）。

初等整数論から先へ

初等整数論の問いの多くは、道具を広げることでより深く理解される。

代数的整数論：$x^2+y^2=p$ のような方程式は、Gauss 整数環 $\mathbb Z[i]$ での分解として見ると見通しがよい（Gauss整数）。一般の代数体の整数環では素元分解の一意性が崩れ、イデアルの分解に置き換わる（数論の記事の注意「反例：一意分解は任意の整域に自動的に広がらない」）。
解析的整数論：素数の個数 $\pi(x)$ の漸近挙動（素数定理）や算術級数中の素数の分布は、ゼータ関数や $L$ 関数の解析で調べる（Riemannゼータ関数）。
$p$ 進的な見方：すべての $p^k$ を法とする合同式を同時に考えると $p$ 進整数・$p$ 進数体に至る（p進整数、p進数体）。合同式の解の持ち上げは Henselの補題になる。
群としての見方：法 $n$ の既約剰余類は群をなし、Fermat・Euler・Wilson の定理や原始根はこの群の構造の言い換えになる（既約剰余類群）。
学び始めの順序としては、除法の原理 → 最大公約数・Euclidの互除法 → 素因数分解の一意性 → 合同式 → Fermatの小定理・中国剰余定理 → 原始根・平方剰余 → 平方剰余の相互法則と進むと、各段階で前の段階の結果だけを使って証明を追える。