MENU
  1. トップ
  2. 基礎体系
  3. 基礎数学
  4. 基礎 数学A
  5. 【基礎 数学(数学A)】Module 8：整数の性質(1) 約数と倍数

【基礎 数学(数学A)】Module 8：整数の性質(1) 約数と倍数

当ページのリンクには広告が含まれています。

本モジュールの目的と構成

これまでのモジュールで探求してきた「場合の数・確率」や「図形の性質」が、それぞれ計数や空間認識という特定の領域を扱っていたのに対し、本モジュールから始まる「整数の性質」の探求は、数学という学問全体の最も根源的な基盤へと我々の思考を導きます。整数は、数が持つ最も純粋な姿であり、その性質を研究する整数論は、古代ギリシャのピタゴラスやユークリッドの時代から、現代の暗号理論に至るまで、人類の知性の歴史と共に歩んできました。

この分野の魅力は、一見すると「1, 2, 3, …」という単純な数の並びの中に、驚くほど深く、美しい秩序と、未だ解き明かされない謎が無限に広がっている点にあります。このモジュールで学ぶのは、単なる計算テクニックではありません。それは、具体的な数値を扱いながらも、その背後にある普遍的な法則性を見出し、厳密な論理によってそれを証明していく、数学的思考の「作法」そのものです。

本モジュールでは、この広大な整数論の世界への第一歩として、すべての基本となる「約数」と「倍数」の概念を深く掘り下げていきます。

  1. 約数と倍数、素因数分解の一意性: 約数・倍数という基本的な言語を定義し、整数論における絶対的な根幹定理である「素因数分解の一意性（算術の基本定理）」を学びます。これは、全ての整数が「素数」という原子から成り立っていることを保証するものです。
  2. 最大公約数（G.C.D.）と最小公倍数（L.C.M.）: 2つ以上の整数の間に成り立つ公的な関係性を捉えるG.C.D.とL.C.M.を学び、これらが素因数分解とどう結びつくかを探ります。
  3. ユークリッドの互除法: 巨大な数の最大公約数を、素因数分解することなく、驚くほど効率的に求めることができる古代からのアルゴリズム、ユークリッドの互除法をマスターします。
  4. 素数の性質: 整数の「原子」である素数が持つ基本的な性質、特にその無限性について、ユークリッドによる古典的で美しい証明を味わいます。
  5. 互いに素な整数の性質: 共通の約数を1しか持たない「互いに素」という関係性が、整数論においていかに重要で、強力な性質であるかを探求します。
  6. 約数の個数と総和: 素因数分解という設計図から、その整数が持つ約数の「個数」と「総和」を、場合の数の考え方を応用して計算する方法を学びます。
  7. 平方数と立方数: ある整数が平方数や立方数になるための条件を、素因数分解の指数の形から見抜く方法を習得します。
  8. フェルマーの小定理: 素数を法とする合同式の世界で成り立つ、基本的ながらも極めて強力な定理であるフェルマーの小定理を学び、その応用を見ます。
  9. メルセンヌ素数: 2^n - 1の形で表される特別な素数、メルセンヌ素数の性質と、それが完全数と深く結びついていることを紹介します。
  10. 整数問題における実験と推測: 整数問題に特有のアプローチ法として、具体的な数値で「実験」し、そこからパターンを見出して「推測」し、最終的に「証明」へと至る、科学的な探求のプロセスを学びます。

このモジュールを通じて、皆様は、数の世界が、混沌とした数の集まりではなく、素数という基本粒子によって支配された、見事な構造を持つ宇宙であることを実感するでしょう。その構造を読み解き、論理の言葉で語る能力は、皆様の数学的思考力を、より深く、より精緻なものへと進化させることを約束します。

目次

1. 約数と倍数、素因数分解の一意性

整数論の探求は、最も基本的な関係性である「割り切れる」という概念、すなわち約数 (Divisor) と倍数 (Multiple) の定義から始まります。これらの言葉は小学校以来慣れ親しんだものですが、高校数学では、その定義をより厳密に捉え直し、すべての整数の構造を支配する根源的な法則へと繋げていきます。その究極の法則が、素因数分解の一意性 (Uniqueness of Prime Factorization)、別名**「算術の基本定理 (Fundamental Theorem of Arithmetic)」**です。この定理は、整数論という壮大な建築物全体の礎石であり、その存在なくして、数の世界の秩序を語ることはできません。

1.1. 約数と倍数の厳密な定義

【定義】

2つの整数 \(a, b\) があるとき、

\[

a = bk

\]

を満たす整数 \(k\) が存在する場合、「\(b\) は \(a\) の約数である」または「\(a\) は \(b\) の倍数である」といい、記号 \(b|a\) で表す。

この定義には、いくつかの重要な注意点が含まれています。

  • 整数：\(k\) は整数でなければなりません。例えば、\(6 = 4 \times 1.5\) ですが、1.5は整数ではないので、4は6の約数ではありません。
  • 対象範囲: 高校数学の「整数の性質」では、特に断りがない限り、**正の整数（自然数）**の範囲で約数・倍数を考えることがほとんどです。しかし、定義上は負の整数や0も対象となります。
    • 負の整数: \(6 = (-2) \times (-3)\) なので、-2や-3も6の約数です。
    • 0: 任意の0でない整数 \(b\) に対して、\(0 = b \times 0\) なので、0はすべての整数の倍数です。また、0を約数とすることは通常考えません。

例: 12の正の約数は、\(12 = 1 \times 12 = 2 \times 6 = 3 \times 4\) より、{1, 2, 3, 4, 6, 12} の6個です。

1.2. 素数と合成数：整数の原子

自然数は、その約数の個数によって、3つのカテゴリーに分類されます。

  1. 1: 約数が {1} のみ、ただ1個だけの特別な数。
  2. 素数 (Prime Number): 1とその数自身の、ちょうど2個の正の約数を持つ、1より大きい自然数。(例: 2, 3, 5, 7, 11, 13, 17, 19, …)
  3. 合成数 (Composite Number): 1とその数自身以外にも約数を持つ、1より大きい自然数。すなわち、正の約数が3個以上ある数。(例: 4, 6, 8, 9, 10, 12, …)

この分類において、素数が極めて重要な役割を果たします。素数は、それ以上約数に分解できない、いわば整数の世界の「原子」のような存在です。そして、すべての合成数は、これらの素数という原子がいくつか組み合わさってできた「分子」であると見なすことができます。この考え方を定式化したのが、素因数分解です。

1.3. 素因数分解の一意性（算術の基本定理）

素因数分解 (Prime Factorization) とは、ある合成数を、素数の積の形で表現することです。

例えば、72を素因数分解してみましょう。

\(72 = 2 \times 36 = 2 \times 2 \times 18 = 2 \times 2 \times 2 \times 9 = 2 \times 2 \times 2 \times 3 \times 3 = 2^3 \times 3^2\)

このとき、どのような順序で分解を進めても、最終的に現れる素数の種類（2と3）と個数（2が3個、3が2個）は、常に同じになります。この当たり前のように思える事実こそが、整数論の根幹をなす、自明ではない偉大な定理です。

【算術の基本定理 (Fundamental Theorem of Arithmetic)】

すべての1より大きい整数は、素数の積として（積の順序を除いて）一意に表すことができる。

この定理の深遠な意味

  • 一意性 (Uniqueness): この定理の核心は「一意に」という部分にあります。これにより、すべての整数は、素因数分解という、いわば固有の「DNA」や「指紋」を持つことが保証されます。72という数は、\(2^3 \times 3^2\) という素数の構成以外では絶対に作れない、宇宙でただ一つの存在なのです。
  • 構造の保証: この定理があるからこそ、我々は整数の性質を、その構成要素である素数の性質に還元して、体系的に議論することができます。最大公約数や最小公倍数の計算、約数の個数や総和の公式など、この後に続く整数論のほとんどすべてのトピックが、この算術の基本定理という土台の上に築かれています。
  • 非自明性: 私たちが普段扱う数の世界（有理整数環）では、この定理は当たり前に成り立ちます。しかし、大学で学ぶ代数学では、\(a+b\sqrt{-5}\) のような「整数」の世界を考えると、そこでは素因数分解の一意性が成り立たない（例えば \(6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})\) のように、2通りの分解が存在する）場合があることが知られています。このことからも、我々の整数の世界が持つこの「一意性」という性質が、いかに特別で幸運なものであるかが分かります。

証明の概略

この定理の証明は、「存在証明（必ず素因数分解できること）」と「一意性証明（その分解がただ一通りであること）」の二段階に分かれます。

  1. 存在証明: 背理法（あるいは数学的帰納法の一種である無限降下法）によって示すことができます。もし素因数分解できない最小の合成数 \(n\) が存在すると仮定すると、\(n=ab\) と分解でき、\(a, b\) は \(n\) より小さいので素因数分解できるはず。すると、\(n\) も素因数分解できてしまい、矛盾する。
  2. 一意性証明: こちらの方がより高度です。「ユークリッドの補題」（もし素数 \(p\) が積 \(ab\) を割り切るならば、\(p\) は \(a\) または \(b\) の少なくとも一方を割り切る）という重要な性質を先に証明し、それを利用します。もしある数が2通りに素因数分解できたと仮定し（\(p_1 p_2 \dots = q_1 q_2 \dots\)）、両辺を一つの素数で次々と割っていくと、最終的に矛盾が導かれます。

算術の基本定理は、これからの整数論の議論のすべてにおいて、我々が呼吸をする空気のように、常に暗黙の前提として存在し続けます。ある整数の問題で行き詰まったとき、「まず素因数分解してみる」という行動は、その問題の構造を明らかにするための、最も基本的かつ強力な第一歩となるのです。

2. 最大公約数（G.C.D.）と最小公倍数（L.C.M.）

2つ以上の整数が与えられたとき、それらの数に共通する性質を調べることは、整数問題の基本です。その中でも、約数と倍数という観点から最も重要な関係性を記述するのが、最大公約数 (Greatest Common Divisor, G.C.D.) と最小公倍数 (Least Common Multiple, L.C.M.) です。これらの概念は、分数の約分や、異なる周期を持つ事象が次に同時に起こるタイミングを計算するなど、実用的な場面でも頻繁に登場します。ここでは、G.C.D.とL.C.M.を素因数分解の観点から深く理解し、それらの間に成り立つ美しい関係性を探求します。

2.1. G.C.D.とL.C.M.の定義

公約数 (Common Divisor) と 公倍数 (Common Multiple)

  • 公約数: 2つ以上の整数に共通する約数。(例: 12と18の公約数は {1, 2, 3, 6})
  • 公倍数: 2つ以上の整数に共通する倍数。(例: 4と6の公倍数は {12, 24, 36, …})

この公約数・公倍数の中で、特別な意味を持つのが「最大」のものと「最小」のものです。

最大公約数 (G.C.D.)

  • 定義: 公約数のうち、最大のもの。
  • 記号: G.C.D.(a, b) や (a, b) と書く。
  • (例: G.C.D.(12, 18) = 6)

最小公倍数 (L.C.M.)

  • 定義: 正の公倍数のうち、最小のもの。
  • 記号: L.C.M.(a, b) や [a, b] と書く。
  • (例: L.C.M.(4, 6) = 12)

2.2. 素因数分解を用いたG.C.D.とL.C.M.の計算

算術の基本定理により、すべての整数は素数の積で一意に表せます。この素因数分解を用いると、G.C.D.とL.C.M.の構造が非常に明確になります。

2つの自然数 A, B の素因数分解が、

\[ A = p^a q^b r^c \cdots \]

\[ B = p^x q^y r^z \cdots \]

と与えられているとします。（ここで、指数 a, x などは0以上の整数とします。例えば、Bが素因数pを持たない場合は x=0 と考えます。）

G.C.D.の求め方

  • AとBの公約数は、Aの約数であり、かつ、Bの約数でなければなりません。
  • ある素数 \(p\) に注目したとき、公約数に含まれる \(p\) の指数は、Aの指数 \(a\) を超えることはできず、かつ、Bの指数 \(x\) を超えることもできません。
  • そのような指数のうち最大のものは、\(a\) と \(x\) のうち小さい方になります。これを \(\min(a, x)\) と書きます。
  • この議論が、すべての素因数について言えます。
  • したがって、最大公約数は、各素因数の指数として、両者に含まれる指数のうち小さい方（min）をとって掛け合わせたものになります。\[\text{G.C.D.}(A, B) = p^{\min(a, x)} q^{\min(b, y)} r^{\min(c, z)} \cdots\]

L.C.M.の求め方

  • AとBの公倍数は、Aの倍数であり、かつ、Bの倍数でなければなりません。
  • ある素数 \(p\) に注目したとき、公倍数に含まれる \(p\) の指数は、Aを割り切るために少なくとも \(a\) 以上である必要があり、かつ、Bを割り切るために少なくとも \(x\) 以上である必要があります。
  • そのような指数のうち最小のものは、\(a\) と \(x\) のうち大きい方になります。これを \(\max(a, x)\) と書きます。
  • したがって、最小公倍数は、各素因数の指数として、両者に含まれる指数のうち大きい方（max）をとって掛け合わせたものになります。\[\text{L.C.M.}(A, B) = p^{\max(a, x)} q^{\max(b, y)} r^{\max(c, z)} \cdots\]

例題：素因数分解による計算

A=180, B=168 のG.C.D.とL.C.M.を求めよ。

  1. 素因数分解:
    • \(180 = 18 \times 10 = (2 \times 3^2) \times (2 \times 5) = 2^2 \times 3^2 \times 5^1\)
    • \(168 = 2 \times 84 = 2^2 \times 42 = 2^3 \times 21 = 2^3 \times 3^1 \times 7^1\)
  2. 指数の比較:
    • 2の指数: Aは2, Bは3 → \(\min(2,3)=2, \max(2,3)=3\)
    • 3の指数: Aは2, Bは1 → \(\min(2,1)=1, \max(2,1)=2\)
    • 5の指数: Aは1, Bは0 → \(\min(1,0)=0, \max(1,0)=1\)
    • 7の指数: Aは0, Bは1 → \(\min(0,1)=0, \max(0,1)=1\)
  3. G.C.D.とL.C.M.の計算:
    • G.C.D.(180, 168) = \(2^{\min(2,3)} \times 3^{\min(2,1)} \times 5^{\min(1,0)} \times 7^{\min(0,1)}\)= \(2^2 \times 3^1 \times 5^0 \times 7^0 = 4 \times 3 = 12\)
    • L.C.M.(180, 168) = \(2^{\max(2,3)} \times 3^{\max(2,1)} \times 5^{\max(1,0)} \times 7^{\max(0,1)}\)= \(2^3 \times 3^2 \times 5^1 \times 7^1 = 8 \times 9 \times 5 \times 7 = 2520\)

2.3. G.C.D.とL.C.M.の間の重要な関係式

2つの自然数 \(A, B\) と、そのG.C.D. \(G\) および L.C.M. \(L\) の間には、非常に美しく、重要な関係式が成り立ちます。

【定理】

2つの自然数 \(A, B\) について、

\[

AB = \text{G.C.D.}(A, B) \times \text{L.C.M.}(A, B)

\]

が成り立つ。

証明（素因数分解を用いる）

この定理は、前述の指数 \(\min, \max\) を用いると、鮮やかに証明できます。

  • \(A = p^a \dots\), \(B = p^x \dots\)
  • \(\text{G.C.D.}(A,B) = p^{\min(a,x)} \dots\)
  • \(\text{L.C.M.}(A,B) = p^{\max(a,x)} \dots\)

両辺の、ある一つの素因数 \(p\) の指数に着目します。

  • 左辺 \(AB\) の \(p\) の指数: \(a+x\)
  • 右辺 \(G \cdot L\) の \(p\) の指数: \(\min(a,x) + \max(a,x)\)

ここで、任意の2つの非負整数 \(a, x\) について、\(a+x = \min(a,x) + \max(a,x)\) が常に成り立ちます。（例えば、\(a \ge x\) ならば、\(a+x = x + a = \min(a,x) + \max(a,x)\) となる。）

この関係が、すべての素因数の指数について成り立つため、両辺の素因数分解は完全に一致します。

したがって、\(AB = GL\) が証明されました。

この関係式の応用

この定理により、A, B, G, L のうち3つが分かれば、残りの1つを計算することができます。特に、G.C.D.を（後述のユークリッドの互除法などで）求めた後に、L.C.M.を計算する際に便利です。

\[

L = \frac{AB}{G}

\]

例題: A=180, B=168 の場合

  • G.C.D.(180, 168) = 12
  • \(L.C.M.(180, 168) = \frac{180 \times 168}{12} = 15 \times 168 = 2520\)となり、先ほどの素因数分解による計算結果と一致します。

注意: この \(AB=GL\) という関係式は、2つの整数の場合にのみ成り立ちます。3つ以上の整数 A, B, C に対しては、\(ABC = \text{G.C.D.}(A,B,C) \times \text{L.C.M.}(A,B,C)\) は一般に成り立たないので注意が必要です。

素因数分解は、G.C.D.とL.C.M.の「正体」を、指数のレベルで明確に暴き出すための、強力な分析ツールです。この視点を持つことで、これらの概念が単なる計算の対象ではなく、整数の根源的な構造を反映したものであることが深く理解できるでしょう。

3. ユークリッドの互除法

最大公約数（G.C.D.）を求める最も基本的な方法は、それぞれの数を素因数分解し、共通する素因数の指数を比較することです。しかし、与えられた数が非常に大きい場合、その素因数分解を実行すること自体が、極めて困難、あるいは事実上不可能になることがあります。このような状況で、2つの整数の最大公約数を驚くほど高速かつ効率的に求めることができる、古代から伝わる強力なアルゴリズムがユークリッドの互除法 (Euclidean Algorithm) です。

3.1. ユークリッドの互除法の原理

ユークリッドの互除法は、以下の極めてシンプルかつエレガントな原理に基づいています。

【互除法の原理】

2つの自然数 \(a, b\) (\(a \ge b\)) があるとき、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\) とする。すなわち、

\[ a = bq + r \quad (0 \le r < b) \]

このとき、\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しい。

\[

\text{G.C.D.}(a, b) = \text{G.C.D.}(b, r)

\]

この原理がなぜ強力なのか？

この等式は、「\((a,b)\) のG.C.D.を求める」という問題を、「より小さい数の組 \((b,r)\) のG.C.D.を求める」という問題に、答えを変えることなく置き換えることができる、ということを意味します。

この操作を繰り返し適用していくと、扱う数の組はどんどん小さくなっていき、最終的には非常に簡単な組のG.C.D.を求める問題に帰着するのです。

原理の証明

この原理がなぜ成り立つのかを証明します。

目標：「\(a, b\) の公約数の集合」と「\(b, r\) の公約数の集合」が完全に一致することを示す。

もし集合が一致するならば、その中の最大元（最大公約数）も当然一致するはずです。

  1. ステップ1：「\(a, b\) の公約数は、\(b, r\) の公約数でもある」ことを示す。
    • \(d\) を \(a, b\) の任意の公約数とする。
    • \(a = da’, b = db’\) と書ける（\(a’, b’\) は整数）。
    • \(a=bq+r\) を変形して \(r = a-bq\)。
    • この式に \(a=da’, b=db’\) を代入すると、\(r = da’ – (db’)q = d(a’ – b’q)\)
    • \(a’, b’, q\) はすべて整数なので、\((a’-b’q)\) も整数。
    • したがって、\(d\) は \(r\) の約数である。
    • \(d\) はもともと \(b\) の約数でもあったので、\(d\) は \(b\) と \(r\) の公約数である。
  2. ステップ2：「\(b, r\) の公約数は、\(a, b\) の公約数でもある」ことを示す。
    • \(d’\) を \(b, r\) の任意の公約数とする。
    • \(b = d’b”, r = d’r”\) と書ける（\(b”, r”\) は整数）。
    • \(a=bq+r\) の式にこれらを代入すると、\(a = (d’b”)q + d’r” = d'(b”q + r”)\)
    • \(b”, q, r”\) はすべて整数なので、\((b”q+r”)\) も整数。
    • したがって、\(d’\) は \(a\) の約数である。
    • \(d’\) はもともと \(b\) の約数でもあったので、\(d’\) は \(a\) と \(b\) の公約数である。
  3. 結論:ステップ1と2から、2つの数の組 \((a,b)\) と \((b,r)\) は、全く同じ公約数の集合を持つことが示された。よって、その最大公約数も等しくなる。\(\text{G.C.D.}(a, b) = \text{G.C.D.}(b, r)\)。

（証明終）

3.2. ユークリッドの互除法のアルゴリズム

互除法の原理を、具体的な計算手順（アルゴリズム）に落とし込むと、以下のようになります。

アルゴリズム

  1. 2つの自然数 \(a, b\) (\(a \ge b\)) を用意する。
  2. \(a\) を \(b\) で割り、余り \(r\) を求める。
  3. もし余り \(r\) が 0 ならば、そのときの割る数 \(b\) が求める最大公約数である。計算を終了する。
  4. もし余り \(r\) が 0 でないならば、\(a\) の位置に \(b\) を、\(b\) の位置に \(r\) を置き換えて、ステップ2に戻る。

このプロセスは、余りが必ず元の割る数より小さくなるため、有限回で必ず終了します（余りが0になる）。

例題：G.C.D.(899, 391) を求める

素因数分解しようとすると、どちらの数も大きな素数で割れるか試す必要があり、非常に時間がかかります。ユークリッドの互除法を適用してみましょう。

  • ステップ1: 899 を 391 で割る。\(899 = 391 \times 2 + 117\)(余り 117。0ではない) → G.C.D.(899, 391) = G.C.D.(391, 117)
  • ステップ2: 391 を 117 で割る。\(391 = 117 \times 3 + 30\)(余り 30。0ではない) → G.C.D.(391, 117) = G.C.D.(117, 30)
  • ステップ3: 117 を 30 で割る。\(117 = 30 \times 3 + 27\)(余り 27。0ではない) → G.C.D.(117, 30) = G.C.D.(30, 27)
  • ステップ4: 30 を 27 で割る。\(30 = 27 \times 1 + 3\)(余り 3。0ではない) → G.C.D.(30, 27) = G.C.D.(27, 3)
  • ステップ5: 27 を 3 で割る。\(27 = 3 \times 9 + 0\)(余り 0。計算終了！)
  • 結論:余りが0になったときの割る数は 3 でした。したがって、G.C.D.(899, 391) = 3 です。（実際、\(899 = 29 \times 31, 391 = 17 \times 23\)なので、G.C.Dは…おっと、計算ミスか？計算の再検証\(899 = 2 \times 391 + 117\) (OK)\(391 = 3 \times 117 + 30 \implies 351+30=381\) … 間違い発見！\(391 = 3 \times 117 + 40\)\(391 = 117 \times 3 + 40\)\(3 \times 117 = 351\)\(391 – 351 = 40\) … 余りは40やり直し
  • ステップ1: \(899 = 391 \times 2 + 117\)
  • ステップ2: \(391 = 117 \times 3 + 40\)
  • ステップ3: \(117 = 40 \times 2 + 37\)
  • ステップ4: \(40 = 37 \times 1 + 3\)
  • ステップ5: \(37 = 3 \times 12 + 1\)
  • ステップ6: \(3 = 1 \times 3 + 0\)
  • 結論: 最後の0でない余り、すなわち余りが0になったときの割る数は 1。よって、G.C.D.(899, 391) = 1。これらは互いに素です。（899=29×31, 391=17×23。素因数分解は合っていた。共通素因数はないのでG.C.D.は1。最初の計算ミスが問題でした。）この例は、手計算の際にいかにミスが起こりやすいか、そして互除法がいかに機械的に進められるかを示しています。

3.3. 互除法の応用：一次不定方程式へ

ユークリッドの互除法の計算過程を逆にたどることで、一次不定方程式 \(ax+by=G.C.D.(a,b)\) の整数解を一つ見つけることができます。これは、次モジュールで学ぶ重要なトピックへの橋渡しとなります。

例：\(40x + 37y = G.C.D.(40,37) = 3\) ではない、\(G.C.D.(40,37)=1\)

\(40x + 37y = 1\) の整数解を一つ見つける。

互除法の計算過程から、

\(40 = 37 \times 1 + 3 \implies 3 = 40 – 37 \times 1\)

\(37 = 3 \times 12 + 1 \implies 1 = 37 – 3 \times 12\)

この \(1 = 37 – 3 \times 12\) の式の「3」に、上の式 \(3 = 40 – 37 \times 1\) を代入する。

\(1 = 37 – (40 – 37 \times 1) \times 12\)

\(1 = 37 – 12 \times 40 + 12 \times 37\)

\(1 = 40 \times (-12) + 37 \times (1+12) = 40 \times (-12) + 37 \times 13\)

したがって、\(x=-12, y=13\) が、\(40x+37y=1\) の解の一つとなることが分かります。

ユークリッドの互除法は、単にG.C.D.を求める高速なアルゴリズムであるだけでなく、その計算過程自体が、整数に関する豊かな情報を内包しています。その応用範囲の広さと理論的な重要性から、整数論における最も基本的で美しいアルゴリズムの一つとされています。

4. 素数の性質

素数は、整数論における主役であり、すべての整数を構成する基本的な「原子」です。その振る舞いや分布は、単純な定義からは想像もつかないほど、複雑で神秘的な性質を秘めています。古代ギリシャの時代から現代に至るまで、数学者たちは素数の謎に魅了され続けてきました。このセクションでは、素数が持つ基本的な性質、特にその数が無限に存在することの証明と、合成数の積との関係について深く探求します。

4.1. 素数の無限性

素数は、数が大きくなるにつれて、その出現頻度が徐々に低くなっていきます。1から100までには25個の素数が存在しますが、901から1000までの間には14個しかありません。では、このまま数を大きくしていけば、いつかは最後の素数が現れ、それ以上の素数は存在しなくなるのでしょうか？この根源的な問いに対して、古代ギリシャの数学者ユークリッドは、**「素数は無限に存在する」**という感動的な証明を与えました。

【定理】素数は無限に存在する。

証明（ユークリッドによる背理法）

  1. 仮定:まず、結論を否定し、「素数の個数は有限である」と仮定します。もし有限個であるならば、そのすべての素数をリストアップすることができるはずです。その素数を小さい方から順に \(p_1, p_2, p_3, \dots, p_n\) とします。\(p_n\) が、この世に存在する「最大の素数」であると仮定します。
  2. 新しい数の構築:次に、この仮定から矛盾を導き出すために、新しい巨大な数 \(N\) を以下のように作ります。\[N = (p_1 \times p_2 \times p_3 \times \cdots \times p_n) + 1\]これは、「存在するすべての素数を掛け合わせ、それに1を足した数」です。
  3. 新しい数 \(N\) の性質を考察する:この数 \(N\) は、1より大きい整数なので、算術の基本定理により、必ず何らかの素数で割り切れるはずです。その素数を \(p\) とします。ところで、我々の仮定によれば、この世に存在する素数は \({p_1, p_2, \dots, p_n}\) のリストに含まれているものしかありません。したがって、\(N\) を割り切る素数 \(p\) も、このリストの中のどれか一つ（例えば \(p_k\)）でなければなりません。
  4. 矛盾の導出:もし、\(p_k\) が \(N\) を割り切るとしたら、どうなるでしょうか。
    • \(N = (p_1 \times \dots \times p_k \times \dots \times p_n) + 1\)
    • \(p_k\) は、積の部分 \((p_1 \times \dots \times p_n)\) を明らかに割り切ります（因数に含まれているので）。
    • もし \(p_k\) が \(N\) 全体も割り切るのであれば、その差である \(N – (p_1 \times \dots \times p_n)\) も割り切れるはずです。
    • ところが、その差は 1 です。
    • これは、「素数 \(p_k\) が 1 を割り切る」ことを意味しますが、素数は2以上の整数なので、これは矛盾です。
  5. 結論:矛盾が生じた原因は、最初の「素数の個数は有限である」という仮定が誤っていたことにあります。したがって、その仮定は棄却され、素数は無限に存在することが証明されました。

（証明終）

この証明の美しさは、最大の素数 \(p_n\) を仮定した上で、それよりも大きい「かもしれない」新しい素数の存在可能性（\(N\)自身が素数であるか、\(N\)を割る未知の素数が存在する）を示すことで、有限性の仮定を打ち破る点にあります。

4.2. エラトステネスの篩

素数が無限にあることは分かりましたが、具体的にある数までの素数をリストアップするにはどうすればよいでしょうか。そのための古代からの素朴で効率的なアルゴリズムが、**エラトステネスの篩（ふるい）**です。

アルゴリズム (100までの素数を見つける場合)

  1. 2から100までの整数をすべて書き出す。
  2. 最初の素数である 2 を残し、その倍数（4, 6, 8, …）をすべて消す。
  3. 次に残っている数のうち最小のもの、すなわち 3 を素数として残し、その倍数（6, 9, 12, …）をすべて消す。
  4. 次に残っている数のうち最小のもの、すなわち 5 を素数として残し、その倍数（10, 15, 20, …）をすべて消す。
  5. この操作を、\(\sqrt{100}=10\) 以下の素数（この場合は7まで）について繰り返す。
  6. 最終的に消されずに残った数が、100以下のすべての素数となる。

なぜ \(\sqrt{n}\) までで十分なのか？

もし、ある合成数 \(k\) (\(k \le n\)) があるとします。\(k=ab\) と因数分解できるとき、\(a, b\) の両方が \(\sqrt{k}\) より大きいことはありえません（もしそうなら積は \(k\) を超えてしまう）。したがって、\(a, b\) の少なくとも一方は \(\sqrt{k} \le \sqrt{n}\) を満たします。

これは、**「n以下の合成数は、必ず\(\sqrt{n}\)以下の素因数を持つ」**ことを意味します。

よって、\(\sqrt{n}\) までの素数の倍数をすべて篩い落とせば、残るのは素数だけになるのです。

4.3. ユークリッドの補題

算術の基本定理の「一意性」を証明する上で、鍵となる重要な性質があります。

【ユークリッドの補題】

素数 \(p\) と、2つの整数 \(a, b\) がある。

もし、\(p\) が積 \(ab\) を割り切るならば（\(p|ab\)）、\(p\) は \(a\) を割り切るか、または \(b\) を割り切る（\(p|a\) または \(p|b\)）。

この性質の重要性

これは、素数が「それ以上分解できない」という性質を、割り算の言葉で表現したものです。

例えば、6は素数ではないので、\(6 | 4 \times 9\) (6は36を割り切る) ですが、6は4を割り切らず、9も割り切りません。

一方、素数3は、\(3 | 4 \times 9\) (3は36を割り切る) であり、この場合、3は9を割り切っています。

この補題は、\(p\) が積 \(ab\) の中に入り込んで、\(a\) か \(b\) のどちらかの素因数として現れない限り、積全体を割り切ることはできない、ということを主張しています。これは、素因数分解の一意性から直感的に明らかですが、厳密には、この補題を先に証明し、それを使って一意性を証明するという順序をとります。

素数の性質は、整数論のあらゆる側面に浸透しています。その無限性は数の世界の果てしない広がりを保証し、ユークリッドの補題はその構造の堅固さを保証します。素数の分布に見られる規則性と不規則性の間の深淵な謎は、現代数学における最大の挑戦の一つ（リーマン予想など）として、今なお多くの数学者を魅了し続けているのです。

5. 互いに素な整数の性質

整数論において、「素数」が個々の数の基本的な性質を決定づける「原子」であるとすれば、「互いに素 (Coprime / Relatively Prime)」という概念は、2つ以上の整数の間の関係性を記述する上で、極めて重要な役割を果たします。共通の素因数を一つも持たない、というこの単純な関係が、驚くほど多くの豊かで強力な性質を生み出します。この「互いに素」という概念を深く理解し、その性質を自在に使いこなすことは、整数問題を解く上での思考の解像度を格段に向上させます。

5.1. 互いに素の定義

【定義】

2つの整数 \(a, b\) の最大公約数 (G.C.D.) が 1 であるとき、\(a\) と \(b\) は互いに素であるという。

\[

\text{G.C.D.}(a, b) = 1

\]

素因数分解による解釈

この定義は、素因数分解の言葉で言い換えると、「\(a\) と \(b\) は、共通の素因数を一つも持たない」ということと完全に同値です。

  • 例: \(12 = 2^2 \times 3\) と \(35 = 5 \times 7\)。共通の素因数がないので、G.C.D.(12, 35) = 1。よって、12と35は互いに素です。
  • 例: \(15 = 3 \times 5\) と \(21 = 3 \times 7\)。共通の素因数3を持つので、G.C.D.(15, 21) = 3。よって、15と21は互いに素ではありません。

注意点

  • 「互いに素」である2つの数は、それぞれが素数である必要は全くありません。上記の例のように、12も35も合成数ですが、互いに素です。
  • 素数 \(p\) と、\(p\) の倍数でない任意の整数 \(a\) は、常に互いに素です。

5.2. 互いに素な整数の基本性質

互いに素という関係は、割り算に関するいくつかの強力な推論を可能にします。

【性質1】（ユークリッドの補題の一般化）

整数 \(a, b, c\) がある。

もし、\(a\) と \(b\) が互いに素であり、かつ \(a\) が積 \(bc\) を割り切るならば（\(a|bc\)）、\(a\) は \(c\) を割り切る（\(a|c\)）。

証明（算術の基本定理を用いる）

  1. \(a|bc\) なので、ある整数 \(k\) を用いて \(bc = ak\) と書ける。
  2. この等式の両辺を素因数分解する。
  3. \(a\) の素因数分解に現れる任意の素数 \(p\) を考える。\(bc = ak\) なので、\(p\) は積 \(bc\) の素因数でもある。
  4. ユークリッドの補題より、素数 \(p\) は \(b\) または \(c\) のいずれかを割り切る。
  5. ここで、仮定「\(a\) と \(b\) は互いに素」であるから、\(a\) と \(b\) は共通の素因数を持たない。
  6. したがって、\(p\) は \(b\) の素因数ではあり得ない。
  7. よって、\(p\) は \(c\) の素因数でなければならない。
  8. この議論は、\(a\) を構成するすべての素因数 \(p\) について成り立つ。
  9. したがって、\(a\) の素因数分解の全体が、\(c\) の素因数分解の中に（指数の分も含めて）含まれていることになる。
  10. これは、\(a\) が \(c\) を割り切ることを意味する。

（証明終）

この性質は非常に強力です。例えば、「\(5x=7y\) で、x, yが整数のとき、xは7の倍数である」といった推論は、5と7が互いに素であることから、この性質によって保証されます。

【性質2】

整数 \(a, b\) が互いに素であるとき、\(a+b\) と \(ab\) も互いに素である。

証明（背理法）

  1. \(a+b\) と \(ab\) が互いに素でないと仮定する。
  2. すると、\(a+b\) と \(ab\) は、ある素数 \(p\) を公約数として持つはずである。
  3. \(p | (a+b)\) であり、かつ \(p | ab\)。
  4. \(p|ab\) であり、\(p\) は素数なので、ユークリッドの補題より \(p|a\) または \(p|b\) の少なくとも一方が成り立つ。
  5. ケースa: \(p|a\) の場合このとき、\(a = pk\)（kは整数）と書ける。\(p | (a+b)\) であったから、\(a+b\) も \(p\) で割り切れる。\(b = (a+b) – a\) と書けるが、\(a+b\) も \(a\) も \(p\) の倍数なので、その差である \(b\) も \(p\) の倍数でなければならない。したがって、\(p|a\) かつ \(p|b\) となる。これは、\(a\) と \(b\) が公約数 \(p\) (\(\ge 2\)) を持つことを意味し、\(a, b\) が互いに素であるという最初の仮定に矛盾する。
  6. ケースb: \(p|b\) の場合全く同様の議論で、\(p|a\) も導かれ、やはり矛盾する。
  7. したがって、最初の仮定「\(a+b\) と \(ab\) が互いに素でない」は誤りである。
  8. よって、\(a+b\) と \(ab\) は互いに素である。

（証明終）

5.3. 一次不定方程式との関係

「互いに素」という概念は、次モジュールで学ぶ一次不定方程式 \(ax+by=c\) の解の存在と深く関わっています。

【ベズーの等式】

2つの整数 \(a, b\) が互いに素であるための必要十分条件は、

\[

ax + by = 1

\]

を満たす整数解 \(x, y\) が存在することである。

この定理は、\(a, b\) の最大公約数が、\(ax+by\) の形で書ける最小の正の整数であることを主張しています（一般化されたベズーの等式）。したがって、G.C.D.が1であれば、1をその形で表現できる、ということになります。この整数解 \(x, y\) は、ユークリッドの互除法を逆にたどることで具体的に見つけることができます。

この定理は、\(a, b\) が互いに素であれば、それらの線形結合（整数倍の和）によって、最小の単位である「1」を作り出すことができる、ということを意味しており、「互いに素」という関係の構造的な強さを示しています。

「互いに素」は、整数論における「独立」や「直交」のような、基本的ながらも非常に重要な関係性を表す概念です。2つの数の間に共通の素因数という「しがらみ」が一切ない状態であり、そのクリーンな関係性が、割り算や方程式に関する多くの明快な結論を導き出すのです。整数問題を解く際には、登場する数のペアが「互いに素」であるかどうかを常に意識することが、問題の本質を見抜くための重要な鍵となります。

6. 約数の個数と総和

ある自然数が与えられたとき、その構造を理解する一つの方法は、その数がどのような約数を持っているかを調べることです。特に、「約数は全部で何個あるのか？」そして「それらの約数をすべて足し合わせると、いくつになるのか？」という二つの問いは、整数問題において頻出するだけでなく、その解法が素因数分解と場合の数の積の法則を見事に結びつける、美しい応用例となっています。

6.1. 約数の個数の求め方

ある自然数 \(N\) の正の約数の個数を求めるための鍵は、その数の素因数分解です。

思考のフレームワーク

  1. 素因数分解:まず、自然数 \(N\) を素因数分解します。\[N = p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_k^{a_k}\]ここで、\(p_1, p_2, \dots\) は互いに異なる素数、\(a_1, a_2, \dots\) はそれぞれ1以上の整数（指数）です。
  2. 約数の構造:\(N\) の任意の約数は、\(N\) を構成している素因数 \(p_1, p_2, \dots\) 以外を因数に持つことはできません。したがって、\(N\) の約数は、必ず以下の形で表されます。\[d = p_1^{b_1} p_2^{b_2} p_3^{b_3} \cdots p_k^{b_k}\]ここで、各指数 \(b_i\) は、元の指数 \(a_i\) を超えることはできません。すなわち、\(0 \le b_1 \le a_1, \quad 0 \le b_2 \le a_2, \quad \dots, \quad 0 \le b_k \le a_k\)となります。（指数が0の場合は、その素因数が1であることを意味します。）
  3. 場合の数の積の法則を適用:一つの約数 \(d\) を作ることは、各素因数 \(p_i\) の指数 \(b_i\) を、許された範囲から一つずつ選んでいく、一連の独立した選択プロセスと見なすことができます。
    • 素因数 \(p_1\) の指数 \(b_1\) の選び方:\(0, 1, 2, \dots, a_1\) の中から選ぶので、\((a_1+1)\) 通り。
    • 素因数 \(p_2\) の指数 \(b_2\) の選び方:\(0, 1, 2, \dots, a_2\) の中から選ぶので、\((a_2+1)\) 通り。
    • …
    • 素因数 \(p_k\) の指数 \(b_k\) の選び方:\(0, 1, 2, \dots, a_k\) の中から選ぶので、\((a_k+1)\) 通り。これらの選択は互いに独立しているので、積の法則により、約数の総数はこれらの選択肢の数をすべて掛け合わせることで得られます。

【約数の個数の公式】

自然数 \(N\) が \(N = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\) と素因数分解されるとき、その正の約数の個数は、

\[

(a_1+1)(a_2+1)\cdots(a_k+1)

\]

となる。

例題：72の約数の個数

  1. 素因数分解: \(72 = 8 \times 9 = 2^3 \times 3^2\)
  2. 指数の確認: 素因数2の指数は3, 素因数3の指数は2。
  3. 公式の適用:約数の個数 = \((3+1)(2+1) = 4 \times 3 = 12\) 個。

実際に書き出してみると、

  • 2の指数が0: \(3^0=1, 3^1=3, 3^2=9\)
  • 2の指数が1: \(2\cdot3^0=2, 2\cdot3^1=6, 2\cdot3^2=18\)
  • 2の指数が2: \(4\cdot3^0=4, 4\cdot3^1=12, 4\cdot3^2=36\)
  • 2の指数が3: \(8\cdot3^0=8, 8\cdot3^1=24, 8\cdot3^2=72\)となり、確かに \(4 \times 3 = 12\) 個の約数が存在することが確認できます。

6.2. 約数の総和の求め方

約数の総和を求める際も、基本的な考え方は同じですが、今度は多項式の展開というアイデアを利用します。

思考のフレームワーク

\(N = p_1^{a_1} p_2^{a_2}\) の場合を考えてみましょう。

\(N\) のすべての約数は、\(p_1\) のべき乗（\(p_1^0, p_1^1, \dots, p_1^{a_1}\)）と、\(p_2\) のべき乗（\(p_2^0, p_2^1, \dots, p_2^{a_2}\)）から、それぞれ一つずつ選んで掛け合わせたものです。

では、以下の2つの多項式の積を展開すると、どのような項が現れるでしょうか。

\[

(p_1^0 + p_1^1 + \cdots + p_1^{a_1})(p_2^0 + p_2^1 + \cdots + p_2^{a_2})

\]

分配法則を用いてこの式を展開すると、最初の括弧の各項と、二番目の括弧の各項が、一度ずつすべて掛け合わされた項の和となります。

その各項は、\(p_1^i p_2^j\) (ただし \(0 \le i \le a_1, 0 \le j \le a_2\)) という形をしています。

これは、まさしく \(N\) のすべての約数のリストそのものです。

したがって、この多項式の展開結果そのものが、\(N\) の約数の総和に等しくなります。

この考え方は、素因数がいくつあっても同様に拡張できます。

【約数の総和の公式】

自然数 \(N\) が \(N = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}\) と素因数分解されるとき、その正の約数の総和は、

\[

(1+p_1+p_1^2+\cdots+p_1^{a_1})(1+p_2+p_2^2+\cdots+p_2^{a_2})\cdots(1+p_k+p_k^2+\cdots+p_k^{a_k})

\]

となる。

各括弧の中は、初項1、公比\(p_i\)、項数\((a_i+1)\)の等比数列の和なので、公式 \(\frac{a(r^n-1)}{r-1}\) を用いて、より簡潔な形で表現することもできます。

\[

\frac{p_1^{a_1+1}-1}{p_1-1} \cdot \frac{p_2^{a_2+1}-1}{p_2-1} \cdots \frac{p_k^{a_k+1}-1}{p_k-1}

\]

例題：72の約数の総和

  1. 素因数分解: \(72 = 2^3 \times 3^2\)
  2. 公式の適用（展開前の形）:総和 = \((2^0+2^1+2^2+2^3)(3^0+3^1+3^2)\)= \((1+2+4+8)(1+3+9)\)= \(15 \times 13 = 195\)
  3. 公式の適用（等比数列の和の形）:総和 = \(\frac{2^{3+1}-1}{2-1} \cdot \frac{3^{2+1}-1}{3-1}\)= \(\frac{16-1}{1} \cdot \frac{27-1}{2} = 15 \cdot \frac{26}{2} = 15 \times 13 = 195\)

どちらの計算方法でも、答えは 195 となります。

完全数との関連

約数の総和は、完全数 (Perfect Number) の概念と密接に関わっています。

完全数とは、「その数自身を除く約数の和が、その数自身と等しくなる」自然数のことです。これは、「約数の総和が、その数自身の2倍になる」ことと同値です。

  • 例: 6の約数は1, 2, 3, 6。
    • 自身を除く約数の和: \(1+2+3=6\)
    • 約数の総和: \(1+2+3+6=12 = 2 \times 6\)よって、6は完全数です。
  • \(N = 2^{p-1}(2^p-1)\) の形で、\(2^p-1\) が素数（メルセンヌ素数）であるとき、Nは完全数になることが知られています（ユークリッド・オイラーの定理）。

約数の個数と総和の公式は、素因数分解という数の「設計図」から、その数が持つ重要な量的性質を導き出すための、エレガントで強力な手法です。その導出過程は、整数論が、場合の数や数列といった他の数学分野と、いかに美しく連携しているかを見事に示しています。

7. 平方数と立方数

整数の中でも、ある整数を2乗（平方）または3乗（立方）して得られる数は、平方数 (Perfect Square) および立方数 (Perfect Cube) として、特別な性質を持っています。これらの数を見分け、またある数を操作してこれらの数を作り出す問題は、整数問題の典型的なパターンの一つです。その判別の鍵は、やはり素因数分解にあります。ある数の素因数分解の「指数の形」を調べることで、その数が平方数や立方数であるか、あるいはそうなるために何が必要かを、完全に明らかにすることができます。

7.1. 平方数の性質と素因数分解

平方数とは、ある整数 \(k\) を用いて \(k^2\) の形で表される数のことです。

(例: \(1=1^2, 4=2^2, 9=3^2, 16=4^2, 25=5^2, \dots\))

素因数分解との関係

平方数の素因数分解には、非常に明快な特徴があります。

例えば、\(144 = 12^2 = (2^2 \times 3)^2 = (2^2)^2 \times 3^2 = 2^4 \times 3^2\)。

\(900 = 30^2 = (2 \times 3 \times 5)^2 = 2^2 \times 3^2 \times 5^2\)。

これらの例から分かるように、ある数の素因数分解におけるすべての素因数の指数が、偶数になっています。これは偶然ではありません。

【平方数であるための条件】

ある自然数 \(N\) が平方数であるための必要十分条件は、\(N\) を素因数分解したときの、すべての素因数の指数が偶数（0も含む）であることである。

証明

  • (\(\implies\)) \(N\) が平方数ならば、指数はすべて偶数である。\(N\) が平方数なので、ある自然数 \(k\) が存在して \(N=k^2\) と書ける。\(k\) の素因数分解を \(k = p_1^{a_1} p_2^{a_2} \cdots\) とする。すると、\(N = k^2 = (p_1^{a_1} p_2^{a_2} \cdots)^2 = p_1^{2a_1} p_2^{2a_2} \cdots\) となる。各指数は \(2a_1, 2a_2, \dots\) となり、すべて2の倍数、すなわち偶数である。
  • (\(\impliedby\)) 指数がすべて偶数ならば、\(N\) は平方数である。\(N\) の素因数分解を \(N = p_1^{2a_1} p_2^{2a_2} \cdots\) とする（指数はすべて偶数）。指数法則により、\(N = (p_1^{a_1})^2 (p_2^{a_2})^2 \cdots = (p_1^{a_1} p_2^{a_2} \cdots)^2\) と書ける。ここで、\(k = p_1^{a_1} p_2^{a_2} \cdots\) とおけば、\(k\) は自然数であり、\(N=k^2\) となる。したがって、\(N\) は平方数である。

応用例題1：平方数になるための乗算

252に、できるだけ小さい自然数 \(n\) を掛けて、ある自然数の平方にしたい。\(n\) の値を求めよ。

思考プロセス

  1. 目標の分析:\(252 \times n = (\text{自然数})^2\) となる \(n\) を見つけたい。これは、\(252n\) の素因数分解の指数が、すべて偶数になるように \(n\) を決めればよい、という問題。
  2. 素因数分解:まず、252を素因数分解する。\(252 = 2 \times 126 = 2^2 \times 63 = 2^2 \times 3^2 \times 7^1\)
  3. 指数のチェック:
    • 2の指数：2（偶数）→ OK
    • 3の指数：2（偶数）→ OK
    • 7の指数：1（奇数）→ これを偶数にする必要がある。
  4. \(n\) の決定:7の指数を偶数にするためには、もう一つ7を掛けて、指数を \(1+1=2\) にすればよい。他の素因数の指数は既に偶数なので、これ以上何かを掛ける必要はない。したがって、掛けるべき最小の自然数 \(n\) は、\(7^1=7\)。答え：\(n=7\)
  5. 検算:\(252 \times 7 = (2^2 \times 3^2 \times 7^1) \times 7^1 = 2^2 \times 3^2 \times 7^2 = (2 \times 3 \times 7)^2 = 42^2\)となり、確かに平方数になっている。

7.2. 立方数の性質と素因数分解

立方数とは、ある整数 \(k\) を用いて \(k^3\) の形で表される数のことです。

(例: \(1=1^3, 8=2^3, 27=3^3, 64=4^3, 125=5^3, \dots\))

平方数の場合と全く同様の議論により、立方数とその素因数分解の指数との間にも、明確な関係が成り立ちます。

【立方数であるための条件】

ある自然数 \(N\) が立方数であるための必要十分条件は、\(N\) を素因数分解したときの、すべての素因数の指数が3の倍数（0も含む）であることである。

証明: 平方数の場合と同様に、\(N=k^3\) とおき、\(k\) を素因数分解することで容易に証明できる。

\(k = p_1^{a_1} \cdots \implies N = k^3 = p_1^{3a_1} \cdots\)。指数はすべて3の倍数となる。

応用例題2：立方数になるための除算

\(n\)は自然数とする。\(540/n\) がある自然数の立方数となるような \(n\) をすべて求めよ。

思考プロセス

  1. 目標の分析:\(\frac{540}{n} = k^3\) (kは自然数) となる \(n\) を探す。これは、分数 \(\frac{540}{n}\) を約分して整数にした結果、その素因数分解の指数がすべて3の倍数になるように、分母の \(n\) を決めればよい、という問題。
  2. 素因数分解:まず、分子の540を素因数分解する。\(540 = 54 \times 10 = (2 \times 3^3) \times (2 \times 5) = 2^2 \times 3^3 \times 5^1\)
  3. 指数のチェックと \(n\) の役割:\(\frac{2^2 \times 3^3 \times 5^1}{n}\) の指数がすべて3の倍数になるようにしたい。
    • 3の指数：3（3の倍数）→ このまま残したい。
    • 2の指数：2（3の倍数でない）→ 邪魔なので、\(n\) で約分して消し去りたい。指数を0にするには、\(n\) は \(2^2\) を因数に持つ必要がある。
    • 5の指数：1（3の倍数でない）→ 邪魔なので、\(n\) で約分して消し去りたい。指数を0にするには、\(n\) は \(5^1\) を因数に持つ必要がある。
    • このように、指数が3の倍数になっていない素因数を、\(n\) を使って「掃除」するイメージ。
  4. 最小の \(n\) を見つける:指数が中途半端な \(2^2\) と \(5^1\) をすべて約分で消すためには、\(n = 2^2 \times 5^1 = 20\) とすればよい。このとき、\(\frac{540}{20} = 27 = 3^3\) となり、確かに立方数になる。
  5. 他の可能性を探る:問題は「\(n\) をすべて求めよ」である。\(n = 2^2 \times 5^1 = 20\) は、\(\frac{540}{n} = 3^3\) となるケースだった。もし、残る立方数が \(1^3=1\) でもよいならどうだろうか。\(\frac{540}{n} = 1\) となるには、\(n=540\) であればよい。\(n=540 = 2^2 \times 3^3 \times 5^1\) の場合、\(540/n=1=1^3\) となり、これも条件を満たす。これ以外に、結果が立方数になるような \(n\) は存在するか？\(n\) は540の約数でなければ、\(540/n\) が整数にならない。\(n\) が、\(2^2 \times 5^1\) という「邪魔な部分」を因数に含んでいないと、それらが約分されずに残ってしまい、結果は立方数にならない。\(n\) は \(2^2 \times 5^1\) を因数に持ち、かつ540の約数である必要がある。\(n = 2^2 \cdot 5^1 \cdot 3^k\) (k=0,1,2,3) という形が考えられる。
    • \(n = 2^2 \cdot 5^1 \cdot 3^0 = 20 \implies 540/n = 3^3\)
    • \(n = 2^2 \cdot 5^1 \cdot 3^1 = 60 \implies 540/n = 3^2\) (ダメ)
    • \(n = 2^2 \cdot 5^1 \cdot 3^2 = 180 \implies 540/n = 3^1\) (ダメ)
    • \(n = 2^2 \cdot 5^1 \cdot 3^3 = 540 \implies 540/n = 1 = 1^3\)答え：\(n = 20, 540\)

この平方数・立方数の問題は、素因数分解というツールがいかに強力であるかを端的に示しています。整数の「形」に関する条件は、その素因数分解における「指数の形」に関する条件へと、常に翻訳することができるのです。

8. フェルマーの小定理

17世紀のフランスの数学者ピエール・ド・フェルマーは、「数論の父」とも呼ばれ、数多くの深遠な定理や予想を残しました。その中でも、フェルマーの小定理 (Fermat’s Little Theorem) は、初等整数論における最も基本的で、美しく、そして強力な定理の一つです。この定理は、素数を法とする合同式の世界において、整数のべき乗が驚くほどシンプルな振る舞いをすることを示しています。現代では、巨大な数の素数判定や、公開鍵暗号（RSA暗号）の理論的基礎としても応用される、極めて重要な定理です。

8.1. フェルマーの小定理の主張

フェルマーの小定理には、2つの同値な表現があります。

【フェルマーの小定理】

\(p\) を素数とする。

  1. \(a\) を \(p\) で割り切れない整数とするとき、\[a^{p-1} \equiv 1 \pmod{p}\]
  2. 任意の整数 \(a\) について、\[a^p \equiv a \pmod{p}\]

形式1と2の関係

  • 1 \(\implies\) 2:形式1の式 \(a^{p-1} \equiv 1 \pmod{p}\) の両辺に \(a\) を掛けると、\(a^p \equiv a \pmod{p}\) となり、形式2が得られます。これは \(a\) が \(p\) で割り切れない場合に成り立ちます。もし \(a\) が \(p\) で割り切れる場合（\(a \equiv 0 \pmod{p}\)）、形式2の左辺は \(a^p \equiv 0^p \equiv 0 \pmod{p}\)、右辺は \(a \equiv 0 \pmod{p}\) となり、やはり \(a^p \equiv a \pmod{p}\) が成り立ちます。したがって、形式1が正しければ、形式2はすべての整数 \(a\) について成り立ちます。
  • 2 \(\implies\) 1:形式2の式 \(a^p – a \equiv 0 \pmod{p}\) は、\(a(a^{p-1}-1)\) が \(p\) で割り切れることを意味します。ここで、もし \(a\) が \(p\) で割り切れないならば、\(a\) と素数 \(p\) は互いに素です。したがって、「互いに素な整数の性質」より、\(a^{p-1}-1\) の方が \(p\) で割り切れることになります。すなわち、\(a^{p-1} \equiv 1 \pmod{p}\) が成り立ちます。

8.2. 定理の証明

この美しい定理には、いくつかの証明方法がありますが、ここでは高校数学の範囲で理解できる、組み合わせ論的な証明（首飾り勘定）のアイデアと、合同式の性質を用いた証明の二つを紹介します。

証明1：合同式の性質を用いる証明

証明の道具: 合同式の基本的な性質、二項定理

  1. 証明の目標:任意の整数 \(a\) について \(a^p \equiv a \pmod{p}\) を示す。数学的帰納法で証明するのが一般的だが、ここでは別の方法を試みる。まず、\(a^{p-1} \equiv 1 \pmod{p}\) (ただし \(a\) は \(p\) で割り切れない) を示す。
  2. 集合を考える:\(p\) で割って1, 2, …, \(p-1\) のいずれかの余りが出る数の集合 \(S = {1, 2, 3, \dots, p-1}\) を考える。
  3. 集合の元にaを掛ける:この集合の各元に、\(p\) と互いに素な整数 \(a\) を掛けて、\(\pmod{p}\) での値を考えた集合 \(aS = {a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)}\) を作る。
  4. aSとSの関係を調べる:
    • \(aS\) の元はすべて0ではない: もし \(ak \equiv 0 \pmod{p}\) (\(k \in S\)) となると、\(p|ak\)。\(p\)は素数で\(p\)は\(a\)を割り切らないので、\(p|k\)となるが、\(k\)は1からp-1の数なので矛盾。
    • \(aS\) の元はすべて異なる: もし \(ak \equiv aj \pmod{p}\) (\(k \neq j\)) となると、\(a(k-j) \equiv 0 \pmod{p}\)。\(a\)と\(p\)は互いに素なので、\(k-j \equiv 0 \pmod{p}\) となるが、\(k, j\) は1からp-1の異なる数なので、その差がpの倍数になることはない。矛盾。
  5. 結論:したがって、集合 \(aS \pmod{p}\) は、集合 \(S\) の元の並べ替えに過ぎない。\({a \cdot 1, \dots, a \cdot (p-1)} \equiv {1, \dots, p-1} \pmod{p}\)この2つの集合の、すべての元の積をとると、それらも \(\pmod{p}\) で等しくなるはず。\((a \cdot 1)(a \cdot 2)\cdots(a \cdot (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}\)\(a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}\)\(p\) は素数なので、\((p-1)!\) は \(p\) と互いに素である。したがって、合同式の両辺を \((p-1)!\) で割ることができる。\(a^{p-1} \equiv 1 \pmod{p}\)

証明2：首飾り勘定（組み合わせ論的証明）のアイデア

  • 問題設定: \(a\) 種類の色を使って、\(p\) 個のビーズを円形に並べて首飾りを作る方法を考える。（ただし、回転して同じになるものは1通りと数える）
  • 数え方1（バーンサイドの補題/直接勘定）:\(p\) 個のビーズを一列に並べる方法は \(a^p\) 通り。このうち、すべてが同じ色になる \(a\) 通り（単色の首飾り）は、回転させても1通りにしかならない。残りの \(a^p-a\) 通りは、すべて異なる色を含む。これらは、\(p\) が素数であるため、回転させると \(p\) 通りの異なる列を生み出す。したがって、首飾りの総数は、\(a + \frac{a^p-a}{p}\) 通りとなる。
  • 数え方2（自明な事実）:首飾りの数は、当然ながら整数でなければならない。
  • 結論:\(\frac{a^p-a}{p}\) が整数である、ということは、\(p\) が \(a^p-a\) を割り切ることを意味する。すなわち、\(a^p – a \equiv 0 \pmod{p}\)、つまり \(a^p \equiv a \pmod{p}\) が成り立つ。

8.3. 定理の応用：巨大なべき乗の余り

フェルマーの小定理の最も直接的な応用は、巨大なべき乗の数を、素数を法として計算する際に、その指数を小さくすることです。

例題

\(13^{100}\) を 17 で割った余りを求めよ。

思考プロセス

  1. 定理の適用条件を確認:
    • 法である 17 は素数である。
    • 底である 13 は、17 で割り切れない。
    • したがって、フェルマーの小定理が使える。
  2. 定理を適用する:\(p=17, a=13\) なので、\(13^{17-1} \equiv 1 \pmod{17}\)すなわち、\(13^{16} \equiv 1 \pmod{17}\)
  3. 指数の分解:求めたい指数 100 を、定理で使える指数 16 で割る。\(100 = 16 \times 6 + 4\)
  4. 合同式の計算:\(13^{100} = 13^{16 \times 6 + 4} = (13^{16})^6 \times 13^4\)\(\pmod{17}\) の世界で考えると、\((13^{16})^6 \times 13^4 \equiv (1)^6 \times 13^4 \equiv 13^4 \pmod{17}\)これで、計算すべき指数が100から4へと、劇的に小さくなった。
  5. 残りの計算:\(13 \equiv -4 \pmod{17}\) を利用すると、計算が楽になる。\(13^4 \equiv (-4)^4 = ((-4)^2)^2 = 16^2 \pmod{17}\)\(16 \equiv -1 \pmod{17}\) なので、\(16^2 \equiv (-1)^2 = 1 \pmod{17}\)
  6. 結論:\(13^{100} \equiv 1 \pmod{17}\)したがって、余りは 1 である。

フェルマーの小定理は、一見すると計算不可能な巨大なべき乗の問題を、合同式の性質を巧みに利用して、手計算可能な範囲にまで引きずり下ろすための、エレガントで強力なツールなのです。

9. メルセンヌ素数

素数の世界には、特定の美しい形をした数の系列が存在し、その中から多くの素数が見出されてきました。その中でも、古くから数学者たちを魅了し、現代においても巨大素数の探求の最前線となっているのが、メルセンヌ数と、その中から生まれるメルセンヌ素数 (Mersenne Prime) です。この数は、17世紀のフランスの神学者・数学者であるマラン・メルセンヌにその名を由来し、理論的にも完全数との深い結びつきを持つ、非常に重要な数です。

9.1. メルセンヌ数の定義

【定義】

自然数 \(n\) に対して、

\[

M_n = 2^n – 1

\]

の形で表される数をメルセンヌ数という。

そして、メルセンヌ数 \(M_n\) が素数であるとき、それをメルセンヌ素数と呼ぶ。

具体例

  • \(n=1: M_1 = 2^1 – 1 = 1\) （素数ではない）
  • \(n=2: M_2 = 2^2 – 1 = 3\) （メルセンヌ素数）
  • \(n=3: M_3 = 2^3 – 1 = 7\) （メルセンヌ素数）
  • \(n=4: M_4 = 2^4 – 1 = 15 = 3 \times 5\) （合成数）
  • \(n=5: M_5 = 2^5 – 1 = 31\) （メルセンヌ素数）
  • \(n=6: M_6 = 2^6 – 1 = 63 = 3^2 \times 7\) （合成数）
  • \(n=7: M_7 = 2^7 – 1 = 127\) （メルセンヌ素数）
  • \(n=11: M_{11} = 2^{11} – 1 = 2047 = 23 \times 89\) （合成数）

9.2. メルセンヌ数が素数となるための必要条件

上の例を見ると、\(M_n\) が素数となるのは、\(n=2, 3, 5, 7, \dots\) のように、指数 \(n\) 自身が素数である場合に限られているように見えます。そして、\(n=4, 6\) のように指数 \(n\) が合成数の場合には、\(M_n\) も合成数になっています。この観察は、実は一般的に成り立つ重要な性質です。

【定理】

メルセンヌ数 \(M_n = 2^n – 1\) が素数であるならば、その指数 \(n\) もまた素数でなければならない。

証明（対偶法）

この定理の対偶、すなわち「指数 \(n\) が合成数ならば、\(M_n = 2^n-1\) も合成数である」を証明します。

  1. 仮定:\(n\) を 1 より大きい合成数とする。
  2. 合成数の性質:\(n\) は合成数なので、1 と \(n\) 以外の約数を持つ。すなわち、\(n = ab\) となるような、\(1 < a, b < n\) を満たす整数 \(a, b\) が存在する。
  3. 因数分解の公式を利用:\(M_n = 2^n – 1 = 2^{ab} – 1\)ここで、\(x = 2^a\) とおくと、\(M_n = (2^a)^b – 1 = x^b – 1\)多項式 \(x^b-1\) は、常に \((x-1)\) を因数に持つ。\[ x^b – 1 = (x-1)(x^{b-1} + x^{b-2} + \cdots + x + 1) \]
  4. 元の数に戻して考察:\(x=2^a\) を代入すると、\(2^{ab}-1 = (2^a-1)(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1)\)
  5. 各因数の大きさを評価する:
    • 第1の因数: \(2^a-1\)仮定より \(a>1\) なので、\(2^a > 2\)、よって \(2^a-1 > 1\)。
    • 第2の因数: \((2^{a(b-1)} + \cdots + 1)\)仮定より \(b>1\) なので、この和は明らかに1より大きい。
  6. 結論:\(M_n = 2^n – 1\) は、1より大きい2つの整数 \((2^a-1)\) と \((\dots)\) の積で表すことができた。したがって、\(M_n\) は合成数である。対偶が真であることが証明されたので、元の命題も真である。

（証明終）

注意：逆は成り立たない

この定理は、\(M_n\) が素数であるための必要条件を与えますが、十分条件ではありません。

つまり、「\(n\) が素数ならば、\(M_n\) も素数である」は偽です。

最初の反例は、\(n=11\) (素数) の場合で、\(M_{11} = 2047 = 23 \times 89\) となり、合成数です。

この定理は、メルセンヌ素数を探す際に、調査すべき候補を「指数が素数のものだけ」に絞り込むことを可能にする、非常に重要な指針となります。

9.3. メルセンヌ素数と完全数

メルセンヌ素数が特別な注目を集めるもう一つの理由は、完全数 (Perfect Number) との間に存在する、古くから知られた美しい関係です。

完全数の定義: その数自身を除く正の約数の和が、その数自身に等しくなる自然数。（例：\(6 = 1+2+3\)）

これは、「正の約数の総和が、その数自身の2倍になる」ことと同値です。

【ユークリッド・オイラーの定理】

正の偶数 \(N\) が完全数であるための必要十分条件は、\(N\) が

\[

N = 2^{p-1}(2^p-1)

\]

の形で表され、かつ \(2^p-1\) がメルセンヌ素数であることである。

証明の概略（十分性の証明）

もし \(M_p = 2^p-1\) が素数であるならば、\(N=2^{p-1}M_p\) の約数の総和 \(\sigma(N)\) を計算してみる。

\(2^{p-1}\) と \(M_p\) は互いに素なので、約数の総和はそれぞれの約数の総和の積となる。

  • \(\sigma(2^{p-1}) = 1+2+\dots+2^{p-1} = \frac{2^p-1}{2-1} = 2^p-1 = M_p\)
  • \(M_p\) は素数なので、その約数は 1 と \(M_p\) のみ。\(\sigma(M_p) = 1+M_p = 1+(2^p-1) = 2^p\)したがって、\(\sigma(N) = \sigma(2^{p-1})\sigma(M_p) = (2^p-1) \cdot 2^p = M_p \cdot 2^p\)これは、元の数 \(N = 2^{p-1}M_p\) のちょうど2倍である。\(\sigma(N) = 2N\)よって、Nは完全数である。

この定理により、新しいメルセンヌ素数を発見することは、新しい（偶数の）完全数を発見することと完全に同値であることが分かります。

  • \(p=2\) → \(M_2=3\) (素数) → 完全数 \(2^{1}(2^2-1) = 2 \times 3 = 6\)
  • \(p=3\) → \(M_3=7\) (素数) → 完全数 \(2^{2}(2^3-1) = 4 \times 7 = 28\)
  • \(p=5\) → \(M_5=31\) (素数) → 完全数 \(2^{4}(2^5-1) = 16 \times 31 = 496\)

巨大素数の探求

メルセンヌ数は、その特殊な形から、素数性を判定するための効率的なアルゴリズム（リュカ–レーマー・テスト）が存在します。このため、コンピューターを用いた巨大素数の探索プロジェクト（GIMPS: Great Internet Mersenne Prime Search）では、メルセンヌ素数がターゲットとされており、現在知られている最大の素数は、ほとんどがメルセンヌ素数です。

なお、「奇数の完全数は存在するか？」という問いは、古代ギリシャ時代から未解決の、整数論における最も有名な未解決問題の一つです。

10. 整数問題における実験と推測

整数問題は、他の数学分野の問題と比較して、定型的で万能な解法が存在しないことが多い、という特徴があります。複雑な方程式や不等式を解くというよりは、整数の持つ離散的で構造的な性質（割り切れる、余りが等しい、偶数か奇数か、など）を手がかりに、論理の網を少しずつ、しかし着実に張り巡らせていくような思考が求められます。このような問題に立ち向かう上で、極めて重要かつ有効なアプローチが、「まず具体的な数値で実験し、そこから法則性を推測し、最終的にそれを証明する」という、科学的な探求のプロセスです。

10.1. なぜ「実験」が有効なのか

整数は、我々が具体的に操作できる、最も身近な数学的対象です。この「具体性」こそが、実験というアプローチを有効にする最大の理由です。

  • パターンの発見: 抽象的な文字式（\(n\) や \(k\)）のままでは見えにくい法則性も、\(n=1, 2, 3, 4, \dots\) と具体的な値を代入して計算してみることで、その背後にある規則性（周期性、特定の数で割り切れる、など）が浮かび上がってくることがあります。
  • 問題の構造理解: 実験を通じて、問題がどのような性質を問うているのか、どの定理が使えそうか、といった問題の「手触り」を掴むことができます。
  • 反例の発見: 立てた推測が間違っている場合、実験はそれを打ち砕く「反例」を効率的に見つけ出してくれます。
  • 証明への道筋: 発見されたパターンが「なぜ」成り立つのかを考察する過程で、証明に必要な論理の糸口（例えば、数学的帰納法が使えそうだ、など）が見つかることがよくあります。

10.2. 実験と推測のプロセス

整数問題に対する実験的アプローチは、以下の4つのステップからなるサイクルとして捉えることができます。

ステップ1：実験 (Experiment)

  • 問題文中の変数（通常は自然数 \(n\)）に、小さい値から順番に代入して、具体的な値を計算してみます。
  • \(n=1, 2, 3, 4, 5, 6\) あたりまで、面倒くさがらずに計算してみることが重要です。
  • 計算結果は、見やすいように表などに整理します。

ステップ2：観察と推測 (Observe & Conjecture)

  • 計算結果のリストを注意深く観察し、そこに潜むパターンや法則性を探します。
    • 一の位の数字が周期的に変化していないか？
    • 結果は常に特定の数の倍数になっていないか？
    • 結果は常に奇数、または偶数ではないか？
    • 結果が平方数や立方数になっていないか？
  • 見つけ出したパターンに基づいて、「おそらく、すべてのnについて〜が成り立つだろう」という**推測（予想, Conjecture）**を立てます。

ステップ3：証明 (Proof)

  • 立てた推測が、本当にすべての（あるいは指定された範囲の）整数について成り立つのかを、数学的に厳密に証明します。
  • 証明に用いる道具は、このモジュールで学んできた様々なツールです。
    • 合同式（剰余類）: 周期性や余りに関する問題で絶大な威力を発揮します。
    • 数学的帰納法: 「すべての自然数nについて」という形の命題を証明するための標準的な手法です。
    • 素因数分解、互いに素の性質、各種定理

ステップ4：検証 (Verify)

  • 証明が完了した後も、自分の論理に誤りがないか、特殊なケース（\(n=1\)など）でも成り立つかなどを再検証します。

10.3. ケーススタディ：\(n^3 – n\) の性質

問題: すべての整数 \(n\) に対して、\(n^3 – n\) は 6 の倍数であることを証明せよ。

アプローチ1：因数分解による直接証明（知識があれば可能）

\(n^3 – n = n(n^2 – 1) = n(n-1)(n+1) = (n-1)n(n+1)\)

これは、連続する3つの整数の積である。

  • 連続する2つの整数の中には、必ず偶数（2の倍数）が1つ含まれる。
  • 連続する3つの整数の中には、必ず3の倍数が1つ含まれる。
  • 2と3は互いに素なので、連続する3つの整数の積は、\(2 \times 3 = 6\) の倍数である。（証明終）これは非常にエレガントな証明ですが、この因数分解に気づかなかったり、連続整数の積の性質を知らなかったりした場合、どうすればよいでしょうか。そこで、実験的アプローチが活きてきます。

アプローチ2：実験と推測からの証明

ステップ1：実験

\(f(n) = n^3-n\) として、\(n\) に小さい整数を代入してみる。

  • \(n=1: f(1) = 1^3 – 1 = 0\)
  • \(n=2: f(2) = 2^3 – 2 = 8 – 2 = 6\)
  • \(n=3: f(3) = 3^3 – 3 = 27 – 3 = 24\)
  • \(n=4: f(4) = 4^3 – 4 = 64 – 4 = 60\)
  • \(n=5: f(5) = 5^3 – 5 = 125 – 5 = 120\)
  • \(n=0: f(0) = 0^3 – 0 = 0\)
  • \(n=-1: f(-1) = (-1)^3 – (-1) = -1 + 1 = 0\)
  • \(n=-2: f(-2) = (-2)^3 – (-2) = -8 + 2 = -6\)

ステップ2：観察と推測

計算結果のリスト {…, -6, 0, 0, 6, 24, 60, 120, …} を見ると、すべてが 6 の倍数になっているように見えます。

推測: 「すべての整数 \(n\) に対して、\(n^3 – n\) は 6 の倍数である」

ステップ3：証明

この推測を証明する。アプローチ1の因数分解に気づけばそれがベストだが、ここでは数学的帰納法で証明してみよう。（対象を自然数に限定して証明する）

[I] \(n=1\) のとき

\(1^3-1=0\) は6の倍数なので、成り立つ。

[II] \(n=k\) のとき、\(k^3-k\) が6の倍数であると仮定する。

すなわち、\(k^3-k = 6m\)（mは整数）と書ける。

[III] \(n=k+1\) のときを調べる。

\((k+1)^3 – (k+1)\)

\(= (k^3 + 3k^2 + 3k + 1) – (k+1)\)

\(= k^3 + 3k^2 + 2k\)

ここで、仮定 \(k^3-k=6m\) を使いたいので、式を \((k^3-k)\) が現れるように変形する。

\(= (k^3-k) + 3k^2 + 3k\)

\(= 6m + 3k^2 + 3k\) （仮定を代入）

\(= 6m + 3k(k+1)\)

この式全体が6の倍数であることを示したい。\(6m\) は既に6の倍数なので、残りの \(3k(k+1)\) が6の倍数であればよい。

  • ここで、\(k(k+1)\) は連続する2つの整数の積なので、必ず偶数（2の倍数）である。
  • したがって、\(k(k+1) = 2j\)（jは整数）と書ける。
  • よって、\(3k(k+1) = 3(2j) = 6j\) となり、6の倍数である。
  • 6の倍数と6の倍数の和は、やはり6の倍数である。したがって、\((k+1)^3 – (k+1)\) は6の倍数である。

[結論]

[I], [II], [III] より、すべての自然数 \(n\) について、\(n^3-n\) は6の倍数であることが示された。（負の整数と0については、個別に確認済み）

整数問題の探求は、定理や公式を適用するだけの受動的な活動ではありません。自ら手を動かして数を調べ、その中に潜むパターンという「自然の声」を聞き、それを論理という言語で厳密に表現していく、能動的で創造的なプロセスなのです。この「実験と推測」という姿勢は、未知の問題に遭遇したときに、自分自身で解法への道を切り拓いていくための、最も信頼できるコンパスとなります。

Module 8：整数の性質(1) 約数と倍数の総括：素数が織りなす数の宇宙

本モジュールを通じて、我々は数学の最も根源的な対象である「整数」の世界を探求し、その構造を支配する基本的な法則を解き明かしてきました。その中心に鎮座していたのは、算術の基本定理、すなわち「すべての整数は、素数という原子の積として一意に分解される」という、宇宙の真理にも似た壮大な定理でした。

この定理を羅針盤として、我々は整数の性質を、その構成要素である素因数の言葉で読み解いてきました。「約数」とは素因数という部品のサブセットであり、その「個数」や「総和」は、各素因数の指数の組み合わせによって決まる、場合の数の問題へと姿を変えました。「最大公約数」と「最小公倍数」は、2つの数の素因数分解図を重ね合わせたときに、共通する部分（指数の最小値）と、全体を覆う部分（指数の最大値）として、その構造が明快に理解されました。

巨大な数の素因数分解が困難であるという現実的な壁に対しては、古代ギリシャから伝わるユークリッドの互除法が、割り算の余りだけに着目して最大公約数を効率的に求める、驚くほどエレガントなアルゴリズムを提供してくれました。

さらに我々は、整数論の主役である「素数」そのものの性質へと分け入り、その数が無限に存在することの美しい証明に触れ、「互いに素」という関係性が、割り算の推論においていかに強力な役割を果たすかを見ました。そして、フェルマーの小定理は、素数を法とする合同式の世界では、数のべき乗が美しい周期性を持つことを示し、現代暗号理論にも繋がる深い洞察を与えてくれました。

このモジュールで一貫して流れていたのは、「整数に関する問題は、素数の性質に関する問題に還元できる」という基本思想です。そして、その還元が困難な未知の問題に対しては、「実験と推測」という科学的なアプローチが、突破口を開くための有効な手段となることを学びました。

我々が探求したこの世界は、混沌とした数の集まりなどではなく、素数という基本法則によって支配され、厳密な論理によってその秩序が保証された、精緻な「数の宇宙」です。この宇宙の構造を理解し、その言語を操る能力は、次なる一次不定方程式や合同式といった、より高度な整数論の探求への、確かな礎となることでしょう。

基礎数学 基礎 数学A
目次