武蔵野個別指導塾の特徴

整数論　素数の謎から代数的整数論・素数定理へ｜武蔵野個別指導塾

公開 2026.10.13更新 2026.10.13武蔵野個別指導塾の特徴大学数学特集（解析・線形代数・代数・幾何・確率統計）

余りの条件から整数を復元する計算を出発点に、平方剰余、素数の分布、フェルマーの最終定理を結びます。RSAの小さな計算例で、合同式が暗号を支える仕組みも確かめられます。

整数論　素数の謎から代数的整数論・素数定理へ

待合室の番号から、割り切れない数を考える

病院の待合室で、呼出番号の表示を眺めながら数学のノートを開いたとします。塾で取り組んだ問題の余白には、「3で割ると2余り、5で割ると3余る整数」とだけ書いてあります。番号が順番に進むのを待つ間に、2、5、8と候補を書けば8が見つかります。けれども、これで全部でしょうか。23も38も条件に合います。一つの答えを見つける計算と、答え全体の形を言い切る数学との違いが、この短い問いに現れています。

整数論は、整数の割り切れ方、素数、整数を解とする方程式などを研究する分野です。扱う数は身近なのに、問いを少し変えると急に難しくなります。足し算や掛け算ができることと、与えられた数を素因数に分けられることは、計算の負担まで同じではありません。また、多くの例で成立する規則が、すべての整数で成立するとは限りません。

高校では、整数の性質を使って個々の問題を解く経験を積みます。大学では、その経験を定義と定理で整理し、どの条件なら解が存在するか、存在する解をどう分類できるかへ進みます。さらに、素数を数えるために対数や極限を使い、整数の方程式を調べるために新しい数の世界を作ります。整数だけを見つめて始まった問いに、解析や代数が必要になるところが整数論のおもしろさです。

ここでは余りの計算を足場にして、その広がりをたどります。最初から高度な理論の名前を覚える必要はありません。「この操作はなぜ許されるのか」を小さな数で確かめる読み方が、先の議論まで役立ちます。

高校の余りの計算を、解全体の表現へ進める

高校数学Aで触れる約数、倍数、ユークリッドの互除法は、整数論の直接の入口です。数学Iの因数分解、数学IIの複素数や対数、数学IIIの極限も、進んだ話で再び使います。単元ごとに別々だった道具が、「整数を調べる」という目的の下でつながります。

待合室の問題を最後まで解いてみましょう。3で割ると2余る整数xは、整数kを使ってx = 3k + 2と書けます。これを5で割ると3余るという条件に入れると、3k + 2と3の差が5の倍数なので、3k – 1が5の倍数になります。kを5で割った余りについて調べると、k = 2のとき3k – 1 = 5となり、条件を満たします。

ここでk = 2だけを答えにしてはいけません。kに5を足せば3k – 1には15が足され、5の倍数であることは変わりません。逆に、kの余りが0、1、3、4のときは条件を満たしません。したがって、整数tを使ってk = 2 + 5tと書けます。元に戻せば、解全体は次の形です。

x = 8 + 15t　(t ∈ ℤ)

ℤは整数全体の集合を表す記号です。t = 0、1、2なら8、23、38となり、t = -1なら-7です。負の数も整数なので、正の整数だけを求めるという条件がなければ除外しません。-7 = 3 × (-3) + 2 = 5 × (-2) + 3ですから、通常の非負の余りを使っても確かに条件に合います。

「候補を並べて当たった」という説明から、「任意の整数tに対して条件を満たし、それ以外の解はない」という説明へ移ることが大事です。大学の数学で答案に求められるのは、この抜けのなさです。答えを作る方向と、すべての答えがその形になることを示す方向を区別します。

また、割る数が変わると事情も変わります。2で割ると0余り、4で割ると1余る整数は存在しません。前者は偶数、後者は奇数だからです。余りの条件は、並べればいつでも両立するわけではありません。「3と5の組ではなぜ解けたのか」という問いから、互いに素という条件と中国剰余定理へ進みます。

合同式・互いに素・平方剰余を定義する

まず、整数a、bについて、aがbを割り切るとは、ある整数kが存在してb = akとなることです。記号ではa ∣ bと書きます。例えば3 ∣ 12は12 = 3 × 4を意味します。割り算の結果が整数になるという言い方を、整数kの存在として述べ直したものです。この形なら、負の整数も同じ定義で扱えます。

次に、整数m ≧ 2を固定します。整数a、bについてm ∣ (a – b)が成り立つとき、aとbはmを法として合同であるといい、a ≡ b (mod m)と書きます。言葉では、mで割った余りが同じという意味です。例えば17 ≡ 2 (mod 5)は、17 – 2 = 15が5の倍数であることを表します。ここで合同記号を等号と取り違えないでください。17と2は異なる整数ですが、5で割った余りだけを見ると区別されません。

法を固定すれば、合同式は足したり掛けたりできます。a ≡ b (mod m)、c ≡ d (mod m)なら、a + c ≡ b + d (mod m)、ac ≡ bd (mod m)です。掛け算については、ac – bd = a(c – d) + d(a – b)と変形すると、右辺の両項がmの倍数であることから説明できます。単に計算の約束を増やしたのではなく、割り切れるという定義から規則が出てきます。

一方、普通の等式のように自由に割ることはできません。2 × 1 ≡ 2 × 4 (mod 6)ですが、1と4は6を法として合同ではありません。両辺にある2を消すには、追加の条件が必要です。この制限が、整数論の多くのつまずきの出発点になります。

正の整数a、bの最大公約数gcd(a, b)は、aとbの両方を割り切る正の整数のうち最大のものです。gcd(a, b) = 1のとき、aとbは互いに素であるといいます。両方が素数であるという意味ではありません。例えば8と15はどちらも合成数ですが、互いに素です。素数とは、1より大きい整数で、正の約数が1と自分自身しかないものです。「素数」と「互いに素」は、一つの数の性質と二つの数の関係という違いがあります。

整数aに対し、au ≡ 1 (mod m)を満たす整数uがあれば、uを法mにおけるaの逆元と呼びます。逆元が存在する条件はgcd(a, m) = 1です。例えば3 × 2 = 6 ≡ 1 (mod 5)なので、法5で3の逆元は2です。これを掛ければ3k ≡ 1 (mod 5)からk ≡ 2 (mod 5)が得られます。先ほどの候補調べは、逆元によって短い計算になります。

オイラー関数φ(n)は、正の整数nに対して、1 ≦ k ≦ nの範囲でgcd(k, n) = 1となる整数kの個数です。記号では次のように書けます。

φ(n) = |{k ∈ ℤ : 1 ≦ k ≦ n, gcd(k, n) = 1}|

縦棒は集合の要素の個数を表しています。n = 12なら該当するのは1、5、7、11なのでφ(12) = 4です。素数pについては1からp – 1までがすべてpと互いに素ですから、φ(p) = p – 1となります。φは素数の個数を数える関数ではなく、与えた整数と互いに素な数を数える関数です。

平方剰余も定義しておきましょう。奇素数pとpで割り切れない整数aについて、x² ≡ a (mod p)を満たす整数xが存在するとき、aを法pの平方剰余といいます。存在しなければ平方非剰余です。法7で0から6までを二乗した余りは、順に0、1、4、2、2、4、1です。したがって、0を除く平方剰余の余りは1、2、4で、3、5、6は平方非剰余です。

実数の世界なら、正の数には平方根があります。しかし、整数の余りの世界では、aが正であることは平方根の存在を保証しません。方程式を解く前に、どの数の世界で解を求めるのかを明らかにする必要があります。ここに、整数論から代数へ進む入口があります。

中国剰余定理と平方剰余の相互法則を使う

中国剰余定理の二つの法の場合を述べます。正の整数m、nがm ≧ 2、n ≧ 2、gcd(m, n) = 1を満たすとき、任意の整数a、bについて、x ≡ a (mod m)、x ≡ b (mod n)を同時に満たす整数xが存在し、その解は法mnで一意です。「一意」は整数の解が一つだけという意味ではなく、二つの解の差が必ずmnの倍数になるという意味です。

存在の鍵は、互いに素なら整数u、vを使ってum + vn = 1と表せることです。これはユークリッドの互除法を逆にたどると得られるベズーの等式です。この等式があれば、次の整数を作れます。

x = avn + bum

法mではumが0、vnが1に合同なのでxはaに合同です。法nではvnが0、umが1に合同なのでxはbに合同です。二つの余りを別々に受け持つ項を足すことで解を作れました。

m = 3、n = 5では2 × 3 + (-1) × 5 = 1です。a = 2、b = 3を入れると、x = 2 × (-1) × 5 + 3 × 2 × 3 = 8となります。また、二つの解x、yがあればx – yは3でも5でも割り切れ、3と5が互いに素なので15で割り切れます。これが先ほど得たx = 8 + 15tという形の理由です。

互いに素という仮定を外すと、解の存在と周期を見直す必要があります。例えばx ≡ 1 (mod 4)、x ≡ 3 (mod 6)はx = 9で両立しますが、周期は24ではなく最小公倍数12です。一般には、二つの余りa、bがgcd(m, n)を法として合同であることが両立の条件となり、両立すれば解は最小公倍数を法として一意になります。解けない場合だけでなく、解けても周期が変わる場合に注意してください。

もう一つ、平方剰余の相互法則を見ます。奇素数pと整数aに対して、ルジャンドル記号(a/p)を、p ∣ aなら0、aが法pの平方剰余なら1、平方非剰余なら-1と定義します。この括弧つきの記号は分数の割り算を表しているのではありません。

相異なる奇素数p、qについて、平方剰余の相互法則は次を主張します。

(p/q)(q/p) = (-1)の ((p – 1)(q – 1)/4) 乗

指数は整数です。pとqの両方が4で割ると3余るとき、右辺は-1です。それ以外の場合は1になります。つまり、pが法qで平方剰余かという問いと、qが法pで平方剰余かという問いが、単純な符号の規則で結びつきます。平方剰余を一つずつ列挙する計算を、別の法での判定へ移せることに力があります。

例えばp = 3、q = 7なら両方とも4で割ると3余ります。7 ≡ 1 (mod 3)なので(7/3) = 1です。相互法則から(3/7) = -1となり、x² ≡ 3 (mod 7)には整数解がありません。先ほどの二乗の余りの一覧とも一致します。

これに対してp = 5、q = 11では右辺は1です。11 ≡ 1 (mod 5)なので(11/5) = 1であり、(5/11) = 1とわかります。実際、4² = 16 ≡ 5 (mod 11)です。7² = 49も同じ余りなので、法11での解は4と7です。実数での平方根の正負に対応して、法11では4と-4に合同な二つの解が現れます。

相互法則そのものの証明には準備が要りますが、計算で使う前に「異なる奇素数」という仮定と、符号が変わる条件を必ず確認しましょう。p = qやp = 2をそのまま代入することはできません。定理を覚えるときに、結論の式だけを切り離さない姿勢がここで必要になります。

素因数分解の先に広がる、方程式と素数の歴史

整数論には、大きく二つの方向があります。一つは、個々の整数や方程式の構造を詳しく調べる方向です。もう一つは、整数を広い範囲で見て、素数がどれほど現れるかを調べる方向です。前者からは代数的整数論、後者からは解析的整数論へ道が延びています。

普通の正の整数では、1より大きい数は素数の積に分解でき、その分解は因子の順序を除いて一意です。しかし、方程式を因数分解するために扱う数を広げると、この性質がそのまま残るとは限りません。複素数zが整数係数のモニック多項式、つまり最高次の係数が1の多項式の根であるとき、zを代数的整数と呼びます。記号では、ある正の整数nと整数a₀、…、aₙ₋₁が存在し、zのn乗 + aₙ₋₁ × zの(n – 1)乗 + … + a₀ = 0が成り立つということです。式の途中には、nより小さい各次数の項が入ります。

例えば√2はz² – 2 = 0を満たすので代数的整数です。普通の整数もこの定義に含まれます。複素数iもi² + 1 = 0を満たすので代数的整数です。整数という語の意味を単に拡大するのではなく、整数係数の方程式との関係を保つように新しい対象を定義しているのです。

因数分解の違いは、a + b√(-5)という形の数だけを集めた世界で見えます。ここでa、bは整数です。この世界では6に二つの分解があります。

6 = 2 × 3 = (1 + √(-5))(1 – √(-5))

積が等しいだけなら普通の整数でも起こりますが、この場合は両方とも、単位を除いてさらに分解できない因子への分解です。それを確かめる道具がN(a + b√(-5)) = a² + 5b²というノルムです。ノルムは積に対して掛け算になり、単位のノルムは1です。2、3、1 + √(-5)のノルムは順に4、9、6ですが、ノルムが2または3になるこの形の数はありません。これにより、それぞれを単位でない二因子の積にはできないと確かめられます。

整数の世界で使えた素因数分解の論法を、そのまま持ち込めない理由が見えます。代数的整数論では、数そのものに加えてイデアルという集合を扱い、因数分解の構造を捉え直します。代数体の整数環では、非零イデアルが素イデアルの積に一意に分解できるという形で、分解の規則を取り戻します。対象を広げた結果、使う言葉も作り直す必要があるのです。

フェルマーの最終定理は、整数n > 2に対し、xのn乗 + yのn乗 = zのn乗を満たす正の整数x、y、zは存在しないという主張です。n = 2なら3² + 4² = 5²が成立しますが、指数を大きくすると同じ種類の正整数解はなくなります。この定理への歩みでは、個々の指数の方程式を調べるだけでなく、因数分解を扱う数の世界や、他の数学的対象との結びつきが重要になりました。

決着の中心となった研究は、有理数体上の楕円曲線の大きなクラスについてモジュラー性を証明し、その対象に半安定な曲線が含まれることからフェルマーの最終定理を導いています（Wiles, 1995）。ここでの楕円曲線は、楕円の輪郭そのものではなく、適切な条件を満たす三次方程式で表される曲線です。整数解の候補を大量に調べ尽くしたのではなく、解があれば生じる数学的構造の性質を通じて、不可能であることを示した点に大きな転換があります。

一方、素数を余りごとに分ける問いにも長い発展があります。正の整数a、dが互いに素なら、a、a + d、a + 2d、…という等差数列には無限に多くの素数が含まれる、というのがディリクレの定理です。例えば5k + 2の形には2、7、17、37などの素数があります。例が続くだけでは無限性の証明にはなりません。この定理と指標という概念の歴史を扱った研究は、1837年の証明を起点に、指標が数学の説明の中でどう使われるかを検討しています（Avigad・Morris, 2014）。余りを分類する初等的な問いが、より抽象的な道具の発展につながりました。

素数を数える見通しと、暗号で使う逆向きの計算

素数が無限にあることから、次は「どの程度の割合で現れるか」が気になります。実数x ≧ 2に対し、π(x)をx以下の素数の個数とします。πという文字を使いますが、ここでは円周率とは別の記号です。素数定理は、自然対数logを用いて、次の極限が成り立つと述べます。

π(x)/(x/log x) → 1　(x → ∞)

これはπ(x) = x/log xという等式ではありません。両者の比が1に近づくという漸近的な主張です。例えば100以下の素数は25個で、100/log 100は約21.71です。1000以下では168個に対して約144.76となります。有限の範囲では差があるため、この式をそのまま正確な個数として使わないでください。比が1に近づくという主張だけから、差が0に近づくとはいえないことも大切です。

この定理から、1から大きな整数Nまでの整数を一様に一つ選ぶとき、その数が素数である確率π(N)/Nは、1/log Nと比を取ると1に近づくとわかります。ただし、隣り合う整数が独立に素数になるという意味ではありません。偶数や特定の素数の倍数には明らかな制約があります。個々の配置の複雑さを残したまま、全体の割合について見通しを与えるのが素数定理です。

余りによる分類と、全体の個数の評価は異なる問題です。先ほどの等差数列の定理は、互いに素な条件を満たす特定の列に素数が無限にあると保証します。それだけで各列の有限範囲の個数が同じだと結論することはできません。指標の歴史を扱う研究を読む際にも、何を分類する道具なのかと、どの分布の主張を証明するのかを区別すると、研究の問いが見えやすくなります（Avigad・Morris, 2014）。

情報分野では、合同式が暗号の基本計算になります。RSAの仕組みを、小さな整数で追ってみます。異なる素数p = 5、q = 11を選び、n = pq = 55とします。1から55までで5または11の倍数を除くと、φ(55) = 55 – 11 – 5 + 1 = 40です。指数e = 3と、3d ≡ 1 (mod 40)を満たすd = 27を選びます。実際に3 × 27 = 81 = 1 + 2 × 40です。

平文を表す整数をm = 7とし、暗号文cをm³を55で割った余りとして作ります。

7³ = 343 = 6 × 55 + 13

したがってc = 13です。復号では13の27乗を55で割った余りを求めます。大きな整数を全部書かなくても、二乗するたびに余りを取れます。13² ≡ 4、13⁴ ≡ 16、13⁸ ≡ 36、13¹⁶ ≡ 31 (mod 55)です。27 = 16 + 8 + 2 + 1なので、求める余りは31 × 36 × 4 × 13を55で割った余りとなり、7に戻ります。

なぜ戻るのでしょうか。整数aとn ≧ 2が互いに素なら、aのφ(n)乗 ≡ 1 (mod n)というオイラーの定理が成り立ちます。これは、nと互いに素な余り全体にaを掛けると、同じ集合が並べ替わることから証明できます。掛けた前後の全要素の積を比べ、各要素の逆元で消去すれば、aのφ(n)乗だけが残ります。

今回のm = 7は55と互いに素なので、復号の計算は7の81乗、すなわち7 × (7の40乗)²に合同です。括弧内が1に合同なため7へ戻ります。55と互いに素でない平文についても、法5と法11に分けて、それぞれ0の場合と非零の場合を調べ、中国剰余定理で結べば復号を説明できます。ここでも、法を分けてから戻す考え方が働きます。

この小さい設定では55の素因数分解がすぐにわかるため、秘密を守る用途には使えません。実際のRSAには大きな数の選択や符号化などの条件があり、この計算だけで暗号方式の安全性を論じることはできません。また、「素因数分解が難しそうだから、どの使い方でも安全」という結論にもなりません。RSAへのある攻撃案を検討した論文は、その提案された攻撃が非常に非実用的で、分析に誤りがあると論じています（Rivest, 1979）。特定の攻撃を退ける主張と、あらゆる攻撃への安全性の主張を区別することも、数学を応用するときの読み方です。

計算の成功と証明の完成を分けて学ぶ

整数論では、手が動くことが強みになる一方で、試した例だけで満足しやすい面もあります。法7の平方剰余をすべて調べれば、その法については結論が出ます。しかし、法を任意の奇素数に変えた相互法則は、一つの表だけでは証明できません。調べている範囲が有限で尽くせるのか、すべての整数を相手にしているのかを、最初に判断します。

初等整数論の概念を探究するコンピュータ環境を扱った研究では、視覚的な表現や実験の機会が、数の基本概念への理解や捉え方にどう関わるかが検討されています（Sinclair・Zazkis・Liljedahl, 2004）。対象は小学校教員を目指す教職課程の学生であり、高校生全般や大学の整数論の証明学習に同じ結果がそのまま当てはまるとは限りません。それでも、数を並べて関係を観察する活動と、その関係を言葉にする活動を結ぶという視点は、学習の手順を考える材料になります。

取り組む順序は、次のように具体化できます。

問題に出る数の範囲を書きます。「xは整数」「法は奇素数」「二つの法は互いに素」などを、計算を始める前に横へ置きます。条件を見失ったら、式変形を増やすよりここへ戻ります。
小さな法について余りの表を作ります。法7なら0から6までで十分です。負の整数や大きな整数もこのどれかと合同なので、表で何を尽くせたのかを説明します。
観察を命題に直します。「二乗の余りが少ない」だけで終えず、「法7で非零の平方剰余は1、2、4」と、対象と結論を特定します。その後で、法を変えたときにも成立しそうな部分を分けます。
各変形の理由を書きます。合同式で共通因子を消したら、その因子と法が互いに素かを確認します。条件が抜けていたら、法6で2を消す例のように、反例を一つ作って原因を確かめます。
答えを元の条件に戻します。中国剰余定理の問題なら両方の余りを確認し、さらに周期を加えた全解を述べます。検算と全解の証明を別々に完成させます。

高校生のうちは、互除法を計算して最大公約数を出すだけでなく、その計算を逆にたどってベズーの等式を作る練習ができます。また、「互いに素なら逆元がある」の逆向きも考えてみてください。au – 1がmの倍数なら、aとmの公約数は1も割り切るため、正の公約数は1しかありません。定理の言葉を片道の手順として覚えず、条件どうしの関係として捉える練習になります。

塾で講師が確かめたいのは、答えの数字だけではありません。途中の「両辺を割る」という一行で、普通の等式と合同式が混ざっていないか、整数解と正整数解が入れ替わっていないかを読みます。生徒が自分の式を説明できるところまで戻り、その一行の根拠を補ってから先へ進めると、難しい記号が増えても考える場所を見失いにくくなります。

ご家庭では、お子さまのノートにすぐ正答が並ばなくても、「どの条件を確かめているのか」を聞く余地を持てます。余りの表を作り直したり、反例によって予想を修正したりする時間にも意味があります。新しい問題数だけを進み具合の物差しにせず、以前は理由を書けなかった操作を説明できるようになったかに目を向けると、学習の変化を具体的に捉えられます。

ここで手が止まるなら、止まった単元まで一緒に戻ります。武蔵境の数学塾（1 対 1）／お問い合わせ

素数・証明・進学前の準備についての三つの問い

素数を見つけるには、すべての小さい数で割るのですか

整数N > 1が合成数なら、√N以下の素因数を持ちます。N = abでa、bがともに√Nより大きければab > Nとなるので、少なくとも一方は√N以下であり、その因子の素因数も√N以下だからです。例えば97なら√97 < 10なので、2、3、5、7で割り切れないことを確かめれば素数と判断できます。これは小さい数で有効な方法で、大きな数の判定には計算量を考えた別の工夫が必要になります。

素数定理があれば、次の素数は正確に予測できますか

素数定理は個数の漸近的な割合を述べるので、ある整数の直後の素数を指定する公式ではありません。「100までにいくつあるか」と「97の次は何か」は別の問いです。整数論では、存在、個数、具体的な構成を分けると、定理が答える範囲を読み取りやすくなります。暗号でも、素数が十分にあるという見通しと、実際に候補を作って判定する手順の両方が必要です。

大学に入る前に高度な理論まで覚えるべきですか

まずは余り、最大公約数、因数分解を、理由とともに使えることを目指してください。逆元を求める計算や、小さな法で平方剰余を列挙する活動なら、高校の知識から始められます。大学の専門的な内容の配当は課程によって異なりますが、集合、写像、証明の読み書きは、多くの理系学部で1〜2年の学びを支えます。先の名前を急いで集めるより、仮定を確かめて結論へ進む経験を重ねるほうが、その後の理論を読む土台になります。

整数論の魅力は、余りを書き出す身近な計算と、まだ見えない大きな構造との距離にあります。3で割ると2余るという条件は、合同式になり、中国剰余定理になり、暗号の復号を説明する道具にもなりました。素因数分解の確かさを問い直すと代数的整数論へ進み、素数の現れ方を問うと極限や対数が必要になりました。

病院の待合室でノートを閉じる前に、8という答えの横へ「8 + 15t、tは整数」と書き足してみてください。一つ見つけた答えを、漏れのない説明に変えるその一行から、大学の整数論は始まります。

あわせて読む（数学の地図・高校数学の単元解説）

数学の地図第15回約数と倍数から整数論、暗号へ

参考文献

Andrew Wiles（1995）「Modular Elliptic Curves and Fermat’s Last Theorem」The Annals of Mathematics. https://doi.org/10.2307/2118559
Jeremy Avigad・Rebecca Morris（2014）「The concept of “character’’ in Dirichlet’s theorem on primes in an arithmetic progression」Archive for History of Exact Sciences. https://doi.org/10.1007/s00407-013-0126-0
Ronald L. Rivest（1979）「Critical remarks on “Critical remarks on some public-key cryptosystems’’ by T. Herlestam」BIT. Nordisk Tidskrift for Informationsbehandling. https://doi.org/10.1007/bf01930859
Nathalie Sinclair・Rina Zazkis・Peter Liljedahl（2004）「Number Worlds: Visual and Experimental Access to Elementary Number Theory Concepts」International Journal of Computers for Mathematical Learning. https://doi.org/10.1023/b:ijco.0000021780.01416.61