【基礎数学(数学A)】Module 9：整数の性質(2) 一次不定方程式

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

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

前モジュールでは、整数論の根幹をなす「素因数分解」と、それに基づく約数・倍数の性質を探求しました。本モジュールでは、その知識を応用し、整数論における中心的かつ実用的なテーマである不定方程式 (Diophantine Equation)、特にその最も基本的な形である一次不定方程式の世界へと深く分け入っていきます。

通常の方程式、例えば 2x+1=5 の解は x=2 のようにただ一つに定まります。しかし、「方程式の数」よりも「未知数の数」が多い場合、その解は一つに定まらず、無数に存在するか、あるいは全く存在しないことになります。不定方程式とは、そのような方程式について、特に整数解という厳しい制約の下での解を求める問題です。鶴と亀の総数からそれぞれの数を割り出す「つるかめ算」のように、その起源は古く、我々の論理的思考力を試すための古典的な題材であり続けてきました。

本モジュールでは、ax+by=c という形の一次不定方程式を完全に攻略するための、体系的な理論と技術を学びます。その探求は、解の「存在条件」の判定から始まり、ユークリッドの互除法を応用した「一つの解（特殊解）」の発見、そして最終的に「無限に存在するすべての解（一般解）」を一つの式で表現する、という美しい論理の流れを追います。

本モジュールは、以下の学習項目を通じて、一次不定方程式の完全な解法をマスターすることを目指します。

一次不定方程式 ax+by=c の整数解: まず、問題の全体像を把握し、特殊解と一般解という基本的な概念を定義します。
ユークリッドの互除法を用いた特殊解の発見: 前モジュールで学んだユークリッドの互除法を「逆再生」することで、方程式を満たす最初の鍵となる「特殊解」を一つ見つけ出す、具体的で強力なアルゴリズムを習得します。
一般解の表現: 一つの特殊解が見つかった後、「互いに素」の性質を利用して、そこから無限に連なる全ての整数解を、一つのパラメータ k を用いて体系的に表現する方法を導出します。
連立一次不定方程式: 未知数が3つ以上、式が2つ以上ある、より複雑な連立方程式に挑み、変数を消去して既知の問題に帰着させる戦略を学びます。
係数が大きい場合の効率的な解法: ユークリッドの互除法が煩雑になるような、係数が大きい問題に対して、合同式を用いてよりスマートに解を求めるテクニックを探求します。
応用問題（文章題）: 様々な文章題を一次不定方程式としてモデル化し、現実的な制約（解が正の整数であるなど）を考慮して、適切な答えを導き出す実践力を養います。
中国の剰余定理: 複数の合同式を同時に満たす整数を求める、連立一次合同式とも言える「中国の剰余定理」を学び、これが不定方程式の理論と深く結びついていることを見ます。
ペル方程式: 一次方程式の世界から一歩踏み出し、x^2 - Dy^2 = 1 という形の二次不定方程式「ペル方程式」を紹介し、その解が持つ美しい構造に触れます。
ディオファントス方程式: 一次不定方程式が、より広範な「ディオファントス方程式」という分野の一部であることを学び、ピタゴラス数やフェルマーの最終定理といった、数学史に輝く有名な問題との繋がりを知ります。
整数解の存在条件: 全ての議論の出発点として、「そもそも、与えられた方程式 ax+by=c に整数解は存在するのか？」という最も根源的な問いに、最大公約数を用いて明確に答えるための判定法を確立します。

このモジュールを修了したとき、皆様は、一見すると捉えどころのない無限の解の海の中から、論理という名の網を用いて、その全体構造をすくい上げる技術を手にしているはずです。その技術は、皆様の代数的思考能力を、より深く、より構造的なものへと変貌させることでしょう。

1. 一次不定方程式 ax+by=c の整数解

整数論の探求において、我々が次に取り組むべきは、与えられた条件を満たす整数を見つけ出す「方程式」の問題です。特に、未知数を2つ以上含む不定方程式の中で、整数解のみを探求する問題は、ディオファントス方程式とも呼ばれ、古くから多くの数学者を魅了してきました。その最も基本的かつ重要な入り口が、一次不定方程式 (Linear Diophantine Equation) です。

1.1. 不定方程式とは

不定方程式とは、一般に、未知数の個数が方程式の個数よりも多い方程式のことを指します。

例えば、x + y = 10 という方程式を考えてみましょう。

もし、x, y が実数であれば、この式を満たす解 (x, y) の組は、座標平面上の直線 y = -x + 10 上のすべての点であり、無数に存在します。解が一つに定まらないため、「不定」と呼ばれます。

しかし、整数問題の世界では、この方程式に「x, y は整数である」という強力な制約が加わります。

この制約の下でも、x+y=10 を満たす整数解は、(0, 10), (1, 9), (11, -1) など、依然として無数に存在します。

整数解を求める不定方程式の問題の目標は、この無数に存在する解を、漏れなく重複なく、一つの形式で表現することにあります。

1.2. 一次不定方程式 `ax+by=c`

このモジュールで中心的に扱うのは、未知数 x, y に関する一次式で表される、以下の形の不定方程式です。

ax + by = c

ここで、a, b, c は整数の係数であり、x, y が求めるべき整数の未知数です。

例: 3x + 5y = 45

この方程式の整数解を一つ見つけるのは、それほど難しくないかもしれません。

例えば、x=0 とすると 5y=45 より y=9。よって、(0, 9) は一つの整数解です。

x=5 とすると 15+5y=45 より 5y=30, y=6。よって、(5, 6) も整数解です。

x=10 とすると 30+5y=45 より 5y=15, y=3。よって、(10, 3) も整数解です。

x=-5 とすると -15+5y=45 より 5y=60, y=12。よって、(-5, 12) も整数解です。

これらの解を観察すると、x が5増えると y が3減る（あるいは x が5減ると y が3増える）という、ある種の規則性が見えてきます。この規則性こそが、無限に存在する整数解の全体像を捉える鍵となります。

1.3. 特殊解と一般解

一次不定方程式の解を求めるプロセスは、大きく分けて二つのステップから構成されます。

ステップ1：特殊解を一つ見つける

特殊解 (Particular Solution) とは、与えられた方程式 ax+by=c を満たす、具体的な整数解の組 (x_0, y_0) を、とにかく何でもよいから一つ見つけ出すことです。
上の例 3x+5y=45 で言えば、(0, 9) や (5, 6) は、どちらも特殊解です。
係数が小さい場合は、勘や試行錯誤で見つけられることもありますが、係数が大きい場合には、後述するユークリッドの互除法を用いた、体系的な発見方法が必要となります。

ステップ2：一般解を導出する

一般解 (General Solution) とは、その方程式を満たすすべての整数解を、一つの整数パラメータ（通常は k）を用いて表現したものです。
特殊解 (x_0, y_0) が一つ見つかれば、それを基点として、すべての解がどのような形をしているかを明らかにすることができます。
例えば、3x+5y=45 の一般解は、特殊解 (x_0, y_0) = (10, 3) を用いると、\[\begin{cases}x = 10 – 5k \y = 3 + 3k\end{cases}\quad (k \text{は任意の整数})\]という形で表現されます。この式で、k に 0, 1, -1, 2, … と整数を代入していくことで、この方程式のすべての整数解を生成することができます。
- k=0 のとき (10, 3)
- k=1 のとき (5, 6)
- k=-1 のとき (15, 0)
- k=2 のとき (0, 9)

1.4. 整数解は常に存在するのか？

では、どのような一次不定方程式でも、必ず整数解は存在するのでしょうか？

答えは NO です。

例えば、2x + 4y = 7 という方程式を考えてみましょう。

左辺は 2(x+2y) となり、x, y がどのような整数であっても、左辺は必ず偶数になります。

一方、右辺の7は奇数です。

偶数が奇数に等しくなることはあり得ないので、この方程式を満たす整数解 (x,y) は存在しません。

この例から、解が存在するためには、係数 a, b と定数 c の間に、何らかの「割り切れる」関係が必要であることが示唆されます。この「整数解の存在条件」を厳密に規定するのが、係数 a, b の最大公約数です。このテーマについては、後のセクションで詳しく掘り下げます。

一次不定方程式の探求は、この「解は存在するのか？」「存在するなら、一つどうやって見つけるのか？」「そして、すべての解はどう表現できるのか？」という三つの問いに、論理的かつ体系的に答えていく知的な旅です。その旅の最も重要な道具となるのが、前モジュールで学んだユークリッドの互除法と、互いに素な整数の性質なのです。

2. ユークリッドの互除法を用いた特殊解の発見

一次不定方程式 ax+by=c を解くための第一歩は、とにかく何でもよいので、具体的な解を一つ見つけ出す「特殊解」の探求です。係数が小さければ x=1, 2, ... と代入して勘で見つけることも可能ですが、67x + 24y = 1 のような方程式では、試行錯誤は現実的ではありません。このような状況で、特殊解を機械的かつ確実に見つけ出すための、極めて強力なアルゴリズムが、ユークリッドの互除法とその応用である拡張ユークリッド互除法です。

2.1. なぜユークリッドの互除法が使えるのか？

ユークリッドの互除法は、2つの整数 a, b の最大公約数 d = G.C.D.(a,b) を求めるためのアルゴリズムでした。その計算過程は、

\[ a = bq_1 + r_1 \]

\[ b = r_1q_2 + r_2 \]

\[ r_1 = r_2q_3 + r_3 \]

\[ \vdots \]

という一連の割り算の等式から成り立っています。

これらの等式を「余り r」について変形すると、

\[ r_1 = a – bq_1 \]

\[ r_2 = b – r_1q_2 \]

\[ r_3 = r_1 – r_2q_3 \]

\[ \vdots \]

となります。

最後の0ではない余りが最大公約数 d です。この最後の式から出発し、余りの式を下から上へと次々に代入していくと、最終的に d を a と b の整数係数の線形結合、すなわち

ax + by = d

の形で表現することができます。このときの x, y が、この方程式の特殊解となります。このプロセスを、しばしば拡張ユークリッド互除法 (Extended Euclidean Algorithm) と呼びます。

2.2. 特殊解の発見アルゴリズム

ax+by = G.C.D.(a,b) の特殊解を見つける手順は、以下の通りです。

ステップ1：ユークリッドの互除法を実行する

a と b に対して、ユークリッドの互除法を最後まで実行し、最大公約数 d を求めます。
その際、途中の割り算の等式 (a = bq+r) をすべて記録しておきます。

ステップ2：「余り=」の形に変形する

ステップ1で得られた等式のうち、余りが0になった最後の式を除くすべての式を、「余り = (割られる数) – (割る数) × (商)」の形に変形します。

ステップ3：下から上へ代入を繰り返す（バック・サブスティテューション）

最大公約数 d が現れた式（最後から2番目の等式）から出発します。
その式に含まれる「余り」を、一つ上の段の「余り=…」の式で置き換えます。
式を a と b の線形結合の形 (...)a + (...)b に整理します。
この代入と整理の操作を、一番上の段の式（最初の割り算）まで、繰り返し続けます。

ステップ4：特殊解の読み取り

最終的に得られた d = (...)a + (...)b の形の式から、a の係数が x、b の係数が y の特殊解となります。

2.3. ケーススタディ：`177x + 52y = 1`

問題: 一次不定方程式 177x + 52y = 1 の整数解を一つ求めよ。

まず、G.C.D.(177, 52) が1になることを確認する必要があります。（もし1でなければ、右辺が1の方程式に解はありません。）

ステップ1：ユークリッドの互除法

(A) 177 = 52 \times 3 + 21
(B) 52 = 21 \times 2 + 10
(C) 21 = 10 \times 2 + 1
(D) 10 = 1 \times 10 + 0最後の0ではない余りは1なので、G.C.D.(177, 52) = 1。したがって、この方程式には整数解が存在します。

ステップ2：「余り=」の形へ

(A’) 21 = 177 - 52 \times 3
(B’) 10 = 52 - 21 \times 2
(C’) 1 = 21 - 10 \times 2

ステップ3：下から上へ代入

出発点: 式(C’)から始めます。1 = 21 – 10 \times 2
代入1回目: 式(C’)の 10 を、式(B’)を使って置き換えます。1 = 21 – (52 – 21 \times 2) \times 2（注意: (52 – 21 \times 2) 全体を一つの塊として扱うのがコツです。）式を 177 と 52 ではなく、21 と 52 の線形結合の形に整理します。1 = 21 – 2 \times 52 + (21 \times 2) \times 21 = 1 \cdot 21 – 2 \cdot 52 + 4 \cdot 211 = 5 \cdot 21 – 2 \cdot 52
代入2回目: 今得られた式の 21 を、式(A’)を使って置き換えます。1 = 5 \times (177 – 52 \times 3) – 2 \cdot 52式を 177 と 52 の線形結合の形に整理します。1 = 5 \cdot 177 – (5 \times 3) \cdot 52 – 2 \cdot 521 = 5 \cdot 177 – 15 \cdot 52 – 2 \cdot 521 = 5 \cdot 177 – 17 \cdot 52

ステップ4：特殊解の読み取り

最終的に、1 = 177 \times 5 + 52 \times (-17) という形が得られました。
これを元の方程式 177x + 52y = 1 と比較すると、x = 5, y = -17
したがって、特殊解の一つは (x, y) = (5, -17) です。

検算:

177 \times 5 + 52 \times (-17) = 885 – 884 = 1。確かに成り立っています。

2.4. 一般的な方程式 `ax+by=c` への拡張

ここまでの手順で求められるのは、ax+by=d (ただし d=G.C.D.(a,b)) の形の特殊解です。

では、右辺が d の倍数 c ( c=kd ) である、より一般的な方程式 ax+by=c の特殊解はどうやって見つければよいでしょうか。

答えは非常にシンプルです。

まず、ユークリッドの互除法を用いて、ax + by = d の特殊解 (x’, y’) を見つけます。ax’ + by’ = d
この式の両辺を k = c/d 倍します。(ax’ + by’) \times k = d \times ka(kx’) + b(ky’) = kda(kx’) + b(ky’) = c
したがって、ax+by=c の特殊解 (x_0, y_0) は、x_0 = kx’ = (c/d)x’y_0 = ky’ = (c/d)y’となります。

例題: 177x + 52y = 3 の特殊解を一つ求めよ。

我々は既に 177x + 52y = 1 の特殊解が (x', y') = (5, -17) であることを見つけています。
d=1, c=3 なので、k = c/d = 3。
両辺を3倍すればよいので、特殊解はx_0 = 3x’ = 3 \times 5 = 15y_0 = 3y’ = 3 \times (-17) = -51
よって、特殊解の一つは (x, y) = (15, -51) です。

ユークリッドの互除法を用いた特殊解の発見は、一見すると回りくどい計算に見えるかもしれませんが、どんなに係数が大きくとも、必ず機械的な手順で解にたどり着ける、極めて信頼性の高いアルゴリズムです。この「最初の鍵」を見つける技術をマスターすることが、一次不定方程式を完全に攻略するための、最も重要なステップとなります。

3. 一般解の表現

一次不定方程式 ax+by=c の特殊解 (x_0, y_0) を一つ見つけることに成功したら、次の目標は、この方程式を満たすすべての整数解を、一つの統一された形で表現する一般解 (General Solution) を導出することです。無限に存在する解の全体像を、整数パラメータ k を用いて記述することで、我々はこの不定方程式を「解ききった」と言うことができます。この一般解を導出するプロセスは、「互いに素」な整数の性質が中心的な役割を果たす、美しい論理の展開です。

3.1. 一般解の導出プロセス

出発点

与えられた方程式: \(ax + by = c \quad \cdots ①\)
我々が見つけた特殊解 (x_0, y_0) は、この方程式を満たすので、\(ax_0 + by_0 = c \quad \cdots ②\)

思考のフレームワーク

差をとって定数項cを消去する:式①から式②を辺々引き算します。\((ax + by) – (ax_0 + by_0) = c – c\)\(a(x – x_0) + b(y – y_0) = 0\)この式を移項すると、\[ a(x – x_0) = -b(y – y_0) \quad \cdots ③ \]この式は、特殊解 (x_0, y_0) と、任意の他の解 (x, y) との間に成り立つ、普遍的な関係を表しています。
最大公約数で両辺を割る:a と b の最大公約数を d = G.C.D.(a,b) とします。a = da’, b = db’ と書けます。ここで、a’ と b’ は互いに素です。この表現を式③に代入します。\(da'(x – x_0) = -db'(y – y_0)\)両辺を d で割ると、\[ a'(x – x_0) = -b'(y – y_0) \quad \cdots ④ \]
「互いに素」の性質を適用する:式④は、「a’ と (x-x_0) の積」が「-b’ と (y-y_0) の積」と等しいことを示しています。ここで、a’ と b’ は互いに素なので、共通の素因数を持ちません。
- 等式 a'(x-x_0) = -b'(y-y_0) の左辺は a' の倍数です。したがって、右辺も a' の倍数でなければなりません。
- a' と b' は互いに素なので、a' が -b' を割り切ることはありません（符号は関係ない）。
- したがって、「互いに素な整数の性質」より、a' は残りの (y-y_0) の方を割り切らなければなりません。
- よって、y – y_0 は a’ の倍数であると言えます。これを整数パラメータ k を用いて表現すると、\[ y – y_0 = ka’ \quad (k \text{は任意の整数}) \]\[ y = y_0 + ka’ \]
xについての表現を導出する:y – y_0 = ka’ という関係を、式④に代入します。\(a'(x – x_0) = -b'(ka’)\)両辺の a’ を（a’は0ではないので）割ると、\(x – x_0 = -kb’\)\[ x = x_0 – kb’ \]
一般解の完成:a’ = a/d, b’ = b/d を元の a, b で書き戻して、一般解の公式が得られます。

【一次不定方程式の一般解】

一次不定方程式 ax+by=c が整数解を持つとき（すなわち c が d=G.C.D.(a,b) の倍数であるとき）、その特殊解の一つを (x_0, y_0) とすると、すべての整数解（一般解）は、任意の整数 k を用いて、

\begin{cases}

x = x_0 – \frac{b}{d}k \

y = y_0 + \frac{a}{d}k

\end{cases}

\quad (k \text{は任意の整数})

と表される。

注意:

x の係数 -(b/d) と y の係数 (a/d) の符号は、片方がマイナスで片方がプラスになります。どちらにマイナスをつけても構いませんが、通常はこの形が用いられます。（x = x_0 + (b/d)k, y = y_0 - (a/d)k も正しい一般解です。）
特に、a と b が互いに素である場合、d=1 なので、一般解はよりシンプルな形になります。\[\begin{cases}x = x_0 – bk \y = y_0 + ak\end{cases}\quad (k \text{は任意の整数})\]

3.2. ケーススタディ：`177x + 52y = 1` の一般解

問題: 一次不定方程式 177x + 52y = 1 のすべての整数解を求めよ。

思考プロセス

特殊解の確認:前セクションで、ユークリッドの互除法を用いて、この方程式の特殊解の一つが (x_0, y_0) = (5, -17) であることを見つけました。
G.C.D.の確認:G.C.D.(177, 52) = 1。したがって、d=1 です。
一般解の公式に代入:a=177, b=52, d=1 および x_0=5, y_0=-17 を公式に代入します。\[\begin{cases}x = 5 – \frac{52}{1}k \y = -17 + \frac{177}{1}k\end{cases}\quad (k \text{は任意の整数})\]\[\begin{cases}x = 5 – 52k \y = -17 + 177k\end{cases}\quad (k \text{は任意の整数})\]これが、求める一般解です。

一般解の検証

この一般解が、本当に元の方程式を満たしているか、代入して確認してみましょう。

177(5 – 52k) + 52(-17 + 177k)

= 177 \cdot 5 – 177 \cdot 52k – 52 \cdot 17 + 52 \cdot 177k

= (177 \cdot 5 – 52 \cdot 17) – (177 \cdot 52 – 52 \cdot 177)k

= (885 – 884) – 0 \cdot k

= 1

確かに、k の値によらず、常に1となり、方程式を満たしていることが分かります。

3.3. 特殊解の選び方と一般解の表現

一般解の表現は、最初に選ぶ特殊解によって見た目が変わることがあります。しかし、それらが表現する解の集合は、全く同じものです。

例: 3x + 5y = 45

特殊解1: (x_0, y_0) = (10, 3)
- G.C.D.(3, 5) = 1 なので、d=1。
- 一般解：x = 10 – 5ky = 3 + 3k
特殊解2: (x_0, y_0) = (0, 9)
- これを基点に一般解を求めると、x = 0 – 5m = -5my = 9 + 3m （パラメータには別の文字 m を使っておく）

これら2つの表現は、一見すると異なります。しかし、例えば前者の式で k=2 とすると、x=10-10=0, y=3+6=9 となり、後者の m=0 の場合に一致します。

一般に、パラメータ k と m の間には m = k-2 という関係があり、k がすべての整数値をとれば、m もすべての整数値をとるため、両者が生成する解の集合は全く同じになります。

したがって、特殊解はどのような方法で見つけても構いません。勘で見つけようが、ユークリッドの互除法を使おうが、最終的に導かれる一般解は、本質的に同じものになるのです。

一般解の導出は、一次不定方程式の探求におけるゴールです。それは、無限に散らばっているように見えた整数解たちが、実は特殊解という一つの「基準点」から、(-b/d, a/d) という一定の「ベクトル」で等間隔に、整然と並んでいる、美しい構造を持っていることを明らかにします。

4. 連立一次不定方程式

これまでは、未知数が2つの一次不定方程式 ax+by=c を扱ってきました。しかし、問題によっては、未知数が3つ以上になったり、複数の不定方程式を同時に満たす解を求めたりする必要が生じます。このような状況で登場するのが、連立一次不定方程式 (Systems of Linear Diophantine Equations) です。未知数が3つで方程式が2つ、といった場合が典型です。

この問題を解くための基本的な戦略は、変数を一つ消去して、我々が既に解き方を知っている未知数が2つの一次不定方程式に帰着させることです。

4.1. 基本的な解法プロセス

未知数が3つ x, y, z で、方程式が2つある、以下の形の連立一次不定方程式を考えます。

\begin{cases}

a_1x + b_1y + c_1z = d_1 & \cdots ① \

a_2x + b_2y + c_2z = d_2 & \cdots ②

\end{cases}

解法のステップ

ステップ1：一つの変数を消去する
- 通常の連立一次方程式を解くときと同様に、①式と②式を定数倍して足し引きすることで、x, y, z のうち最も消去しやすい変数を一つ選び、消去します。
- 例えば、z を消去すると、x と y だけからなる新しい一次不定方程式 Ax + By = C が得られます。
ステップ2：2変数の方程式を解く
- 得られた Ax + By = C という形の一次不定方程式を、これまでのモジュールで学んだ方法で解きます。
- まず、整数解が存在するかどうかを確認します（C が G.C.D.(A,B) の倍数であるか）。
- 存在する場合、特殊解 (x_0, y_0) を見つけ、そこから一般解を導出します。
- この一般解は、整数パラメータ k を用いて、x = x_0 – (B/d)ky = y_0 + (A/d)k (ただし d=G.C.D.(A,B))という形で表現されます。
ステップ3：消去した変数を求める
- ステップ2で得られた x と y の一般解（k を含んだ式）を、元の連立方程式①または②のどちらか一方に代入します。
- 代入した式を、消去した変数（この場合は z）について解きます。
- これにより、z もまた、パラメータ k を用いた式で表現されます。
ステップ4：一般解の完成
- x, y, z のそれぞれを k の式で表現したものが、元の連立一次不定方程式の一般解となります。

4.2. ケーススタディ

問題: 次の連立方程式を満たす整数 x, y, z の組をすべて求めよ。

\begin{cases}

3x + 2y + z = 1 & \cdots ① \

5x + 3y + 2z = 4 & \cdots ②

\end{cases}

思考プロセス

ステップ1：変数の消去

z の係数が1と2なので、z を消去するのが最も簡単そうです。
①式を2倍して、②式から引きます。
- 2 \times ①: 6x + 4y + 2z = 2
- ②: 5x + 3y + 2z = 4
(2 \times ①) – ②:(6x – 5x) + (4y – 3y) + (2z – 2z) = 2 – 4\[ x + y = -2 \quad \cdots ③ \]x と y に関する、非常にシンプルな一次不定方程式が得られました。

ステップ2：2変数の方程式を解く

方程式は x+y=-2。これは 1 \cdot x + 1 \cdot y = -2 です。
a=1, b=1 なので、G.C.D.(1, 1) = 1。右辺の-2は1の倍数なので、整数解は存在します。
特殊解を見つけます。これは勘で簡単に見つかります。例えば、x_0=0 とすると y_0=-2。特殊解は (0, -2)。
一般解を導出します。d=1 なので、a’=1, b’=1。任意の整数 k を用いて、x = x_0 – bk = 0 – 1 \cdot k = -ky = y_0 + ak = -2 + 1 \cdot k = k-2したがって、x と y の一般解は、\[\begin{cases}x = -k \y = k – 2\end{cases}\quad (k \text{は任意の整数})\]

ステップ3：消去した変数 z を求める

x=-k, y=k-2 を、元の式のより簡単な方、①式 3x+2y+z=1 に代入します。3(-k) + 2(k-2) + z = 1-3k + 2k – 4 + z = 1-k – 4 + z = 1
z について解きます。z = k + 5

ステップ4：一般解の完成

x, y, z のすべての解をまとめます。\[\begin{cases}x = -k \y = k – 2 \z = k + 5\end{cases}\quad (k \text{は任意の整数})\]これが、求める一般解です。

検算

得られた一般解を、使わなかった方の式、②式 5x+3y+2z=4 に代入して、恒等的に成り立つかを確認します。5(-k) + 3(k-2) + 2(k+5)= -5k + 3k – 6 + 2k + 10= (-5+3+2)k + (-6+10)= 0 \cdot k + 4 = 4
左辺は常に4となり、右辺と一致します。したがって、この一般解は正しいことが検証できました。

4.3. 解が存在しないケース

連立方程式を解く過程で、解が存在しないこともあり得ます。

例:

\begin{cases}

2x + 4y + 6z = 3 \

\dots

\end{cases}

この場合、①式の左辺は 2(x+2y+3z) となり、常に偶数です。一方、右辺は3で奇数です。したがって、この時点でこの連立方程式に整数解は存在しないことが分かります。

また、変数を消去した結果として得られる Ax+By=C という方程式が、整数解を持たない条件（C が G.C.D.(A,B) の倍数でない）を満たしてしまう場合も、元の連立方程式は解を持ちません。

連立一次不定方程式の解法は、新しい特別な理論を必要とするわけではありません。それは、基本的な連立方程式の「変数消去」という戦略と、2変数の一次不定方程式の一般解を求める技術という、既知の二つのツールを論理的に組み合わせることで達成されます。この「既知の問題に帰着させる」という思考法は、数学のあらゆる分野で通用する、極めて強力な問題解決のメタ戦略なのです。

5. 係数が大きい場合の効率的な解法

ユークリッドの互除法を逆にたどって特殊解を見つける方法は、理論的に美しく、常に解に到達できる万能なアルゴリズムです。しかし、与えられた方程式 ax+by=c の係数 a, b が非常に大きくなると、互除法のステップ数が多くなり、逆代入（バック・サブスティテューション）の計算が非常に煩雑で、計算ミスを犯しやすくなります。

このような状況で、より計算量が少なく、スマートに特殊解を見つけるための効率的な手法が、合同式 (Modular Arithmetic) を利用するアプローチです。

5.1. 合同式を用いた解法の原理

一次不定方程式 ax+by=c は、「ax を b で割ると、c と同じ余りになる」という関係に読み替えることができます。（厳密には ax-c = -by なので、ax-c は b の倍数）。

これを合同式で表現すると、

ax \equiv c \pmod{b}

となります。これは、未知数 x に関する一次合同式です。

解法の流れ

一次合同式に変換:与えられた不定方程式 ax+by=c を、係数の絶対値が小さい方の数を法とする合同式に変換します。例えば |b| < |a| ならば、ax \equiv c \pmod{b} を考えます。
一次合同式を解く:この合同式を満たす整数 x を一つ見つけます。ここでも、係数が大きい場合は、合同式の性質（両辺を定数倍したり、法を小さくしたり）を駆使します。
特殊解の片方を見つける:ステップ2で、例えば x \equiv x_0 \pmod{b} という解が得られたとします。これは、x = bk + x_0（kは整数）と書けることを意味します。最も簡単な解として、x_0 を特殊解のx成分とします。
もう片方の解を求める:見つけた x_0 を、元の不定方程式 ax_0+by=c に代入し、y について解くことで、特殊解のy成分 y_0 を求めます。
一般解を導出:得られた特殊解 (x_0, y_0) を基に、通常の手順で一般解を求めます。

この方法の利点は、ユークリッドの互除法のように、多くのステップを遡って代入を繰り返す必要がなく、比較的小さな数の世界（法 b の剰余類）で計算を進められる点にあります。

5.2. ケーススタディ：`177x + 52y = 1` (再訪)

前セクションでユークリッドの互除法で解いたこの問題を、合同式を用いて解いてみましょう。

問題: 177x + 52y = 1

思考プロセス

合同式への変換:係数の小さい 52 を法として考えます。177x + 52y \equiv 1 \pmod{52}52y は 52 で割り切れるので、52y \equiv 0 \pmod{52} です。したがって、177x \equiv 1 \pmod{52}
合同式の係数を小さくする:177 は 52 よりも大きいので、177 を 52 で割った余りに置き換えます。177 = 52 \times 3 + 21 なので、177 \equiv 21 \pmod{52}。よって、合同式は21x \equiv 1 \pmod{52}となります。
一次合同式を解く:この合同式を満たす x を見つけたい。21x – 1 が 52 の倍数になる x です。試行錯誤（x=1, 2, …）でも見つかるかもしれませんが、ここでもう一段階、合同式のテクニックを使います。21x \equiv 1 \pmod{52}この式を x について解きたいのですが、21 の逆数を mod 52 で見つけるのは大変です。そこで、この合同式を、法と係数を入れ替えるような操作を考えます。21x – 1 = 52k （kは整数）これを、k についての mod 21 の合同式と見なします。-1 \equiv 52k \pmod{21}52 = 21 \times 2 + 10 なので、52 \equiv 10 \pmod{21}。-1 \equiv 10k \pmod{21}10k \equiv -1 \equiv 20 \pmod{21}10 と 21 は互いに素なので、両辺を 10 で割ることができます。k \equiv 2 \pmod{21}これは、k = 21m + 2（mは整数）と書けることを意味します。
特殊解の片方を見つける:k の最も簡単な値として、m=0 のときの k=2 を採用します。この k=2 を、21x – 1 = 52k の式に戻します。21x – 1 = 52 \times 2 = 10421x = 105x = 5これで、特殊解のx成分 x_0 = 5 が見つかりました。
もう片方の解を求める:x=5 を、元の不定方程式 177x + 52y = 1 に代入します。177 \times 5 + 52y = 1885 + 52y = 152y = 1 – 885 = -884y = -884 / 52 = -17よって、特殊解のy成分 y_0 = -17 が見つかりました。

結論:

特殊解は (x, y) = (5, -17) となり、ユークリッドの互除法を用いた結果と一致します。

この後の一般解を求める手順は、前セクションと同じです。

5.3. 合同式解法のメリットと使い分け

メリット:
- 計算量の削減: 特に係数が大きい場合、扱う数の大きさを法の大きさまで抑えることができるため、計算が格段に楽になる。
- 見通しの良さ: 互除法のように、多くの式を遡って代入する必要がなく、一つの合同式を解くことに集中できる。
- 理論的な整合性: 不定方程式の問題が、本質的には合同式（剰余類）の問題と等価であることを明確に示している。
使い分け:
- 係数が小さい場合: 勘で見つけるか、互除法のステップ数が少ないので、どちらでもよい。
- 係数が大きい場合: 合同式を用いる方が、計算ミスが少なく、効率的であることが多い。
- ax+by=G.C.D.(a,b) の形を直接求めたい場合: 拡張ユークリッド互除法は、この形を直接導出するのに適している。

合同式を用いた解法は、一見すると抽象的に見えるかもしれませんが、その根底にあるのは「大きな数の問題を、余りに注目することで、小さな数の問題へとすり替える」という、整数論における強力な問題解決の思想です。このテクニックを習得することで、一次不定方程式に対するアプローチの幅が大きく広がります。

6. 応用問題（文章題）

一次不定方程式は、抽象的な数式としてだけでなく、様々な現実世界の状況をモデル化し、その解を見つけるための実践的なツールとしても機能します。買い物、量の配分、カレンダーの問題など、整数という制約が自然に現れる文章題の多くが、一次不定方程式として定式化できます。

このセクションでは、文章題を解くための一般的なプロセスを学び、特に、数学的な解（一般解）の中から、問題の文脈に合った現実的な解（例えば、個数や人数が正の整数であるなど）を絞り込む作業が重要になることを見ます。

6.1. 文章題を解くためのプロセス

ステップ1：問題の定式化
- 問題文を注意深く読み、未知数を特定する。通常、求めたい2つの量（個数、回数など）を x, y と置く。
- 問題文中の関係性（合計金額、総数など）を読み取り、x, y を用いて ax+by=c という形の一次不定方程式を立てる。
ステップ2：方程式の一般解を求める
- これまでに学んだ方法（ユークリッドの互除法または合同式）を用いて、特殊解を一つ見つける。
- その特殊解を基に、整数パラメータ k を用いた一般解を導出する。
ステップ3：文脈上の制約条件を適用する
- 文章題では、多くの場合、未知数 x, y は単なる整数ではなく、正の整数（x > 0, y > 0）や0以上の整数（x \ge 0, y \ge 0）といった、追加の制約を満たす必要がある。
- 一般解の x と y の式に対して、これらの不等式の制約を適用し、パラメータ k がとりうる値の範囲を絞り込む。
ステップ4：具体的な解を求める
- ステップ3で定まった範囲内の整数 k の値を、一般解の式に代入することで、問題の条件を満たすすべての具体的な解の組 (x, y) を求める。
- 問題が「解をすべて求めよ」と問うているのか、「解の組の個数を求めよ」と問うているのか、あるいは「特定の条件下での解を求めよ」と問うているのかに注意する。

6.2. ケーススタディ：買い物の問題

問題: 1本190円の大根と1本80円のきゅうりを何本か買い、代金の合計がちょうど2000円になるようにしたい。大根ときゅうりは、それぞれ少なくとも1本は買うものとするとき、考えられる組み合わせをすべて求めよ。

ステップ1：定式化

大根の本数を x 本、きゅうりの本数を y 本とする。
代金の合計に関する方程式は、190x + 80y = 2000
式を簡略化するため、両辺を10で割る。19x + 8y = 200
文脈上の制約条件は、それぞれ少なくとも1本は買うので、x \ge 1, y \ge 1

ステップ2：一般解を求める

19x + 8y = 200 の整数解を求める。

合同式を用いるのが効率的である。法を8とする。

19x + 8y \equiv 200 \pmod{8}

19 \equiv 3 \pmod{8}

8y \equiv 0 \pmod{8}

200 = 8 \times 25 \implies 200 \equiv 0 \pmod{8}

したがって、合同式は

3x \equiv 0 \pmod{8}

ここで、3と8は互いに素なので、この合同式が成り立つためには x が8で割り切れなければならない。

x \equiv 0 \pmod{8}

よって、x は8の倍数である。これを整数 k を用いて、

x = 8k と書ける。

x = 8k を元の不定方程式 19x + 8y = 200 に代入する。

19(8k) + 8y = 200

両辺を8で割る。

19k + y = 25

y について解く。

y = 25 – 19k

したがって、一般解は

\begin{cases}

x = 8k \

y = 25 – 19k

\end{cases}

\quad (k \text{は任意の整数})

ステップ3：制約条件の適用

x \ge 1 と y \ge 1 の条件から、k の範囲を絞り込む。

x \ge 1:8k \ge 1 \implies k \ge 1/8
y \ge 1:25 – 19k \ge 124 \ge 19kk \le 24/19 \approx 1.26k は整数なので、この2つの不等式 k \ge 1/8 と k \le 1.26… を同時に満たす k は、k = 1

ステップ4：具体的な解を求める

定まった k の値、k=1 を一般解の式に代入する。

k=1 のとき**:x = 8 \times 1 = 8y = 25 – 19 \times 1 = 6解の組は (x, y) = (8, 6)。

結論

考えられる組み合わせは、

「大根8本、きゅうり6本」の1通りである。

この例が示すように、応用問題の核心は、しばしば一般解を求めた後の「絞り込み」のプロセスにあります。数学的に導出された無限の解の候補の中から、問題の文脈というフィルターを通して、現実的に意味のある有限個の解を選び出す。この最終ステップこそが、数学を現実世界の問題解決に結びつける重要な架け橋なのです。

7. 中国の剰余定理

連立一次不定方程式が、複数の一次式を同時に満たす整数解を探す問題であったのに対し、整数論には、複数の「割り算の余り（剰余）」に関する条件を同時に満たす整数を探す、という有名な問題があります。この種の問題を解くための、強力で美しい理論が、中国の剰余定理 (Chinese Remainder Theorem) です。この定理は、その名の通り、古代中国の数学書「孫子算経」にその原型が見られる、歴史の古い問題に由来しています。

7.1. 問題の起源：「孫子の問題」

「孫子算経」には、以下のような問題が記されています。

今有物不知其数、三三数之賸二、五五数之賸三、七七数之賸二、問物幾何？

（今、数を知らない物がある。3で割ると2余り、5で割ると3余り、7で割ると2余る。その数はいくつか？）

これを現代の合同式の言葉で書き直すと、

\begin{cases}

x \equiv 2 \pmod{3} \

x \equiv 3 \pmod{5} \

x \equiv 2 \pmod{7}

\end{cases}

という、未知数 x に関する連立一次合同式を解く問題となります。

中国の剰余定理は、このような連立一次合同式に、いつ解が存在し、その解がどのような性質を持つかを保証するものです。

7.2. 中国の剰余定理

【定理】

\(m_1, m_2, \dots, m_k\) を、互いに素な（どの2つをとっても最大公約数が1である）正の整数とする。

このとき、任意の整数 \(b_1, b_2, \dots, b_k\) に対して、連立一次合同式

\begin{cases}

x \equiv b_1 \pmod{m_1} \

x \equiv b_2 \pmod{m_2} \

\vdots \

x \equiv b_k \pmod{m_k}

\end{cases}

は、\(M = m_1 m_2 \cdots m_k\) を法として、ただ一つの解を持つ。

（すなわち、解は x ≡ x_0 (mod M) の形で一意に定まる）

この定理の重要なポイントは、法となる \(m_i\) が互いに素であるという条件です。この条件が満たされていれば、解は必ず存在し、かつ mod M で一意に定まる、という非常に強力な結果を保証します。

7.3. 定理の解法：一次不定方程式への帰着

中国の剰余定理は、その解を直接求めるアルゴリズムも存在しますが、高校数学の範囲では、連立合同式を一次不定方程式の問題へと段階的に帰着させて解くのが一般的です。

孫子の問題 \(x \equiv 2 \pmod{3}, x \equiv 3 \pmod{5}, x \equiv 2 \pmod{7}\) を解く

ステップ1：最初の合同式を不定方程式の形に直す

x ≡ 2 (mod 3) は、ある整数 k を用いて、

x = 3k + 2

と書ける。

ステップ2：次の合同式に代入する

この x の表現を、2番目の合同式 x ≡ 3 (mod 5) に代入します。

3k + 2 ≡ 3 (mod 5)

3k ≡ 1 (mod 5)

これは、k に関する一次合同式です。

3k-1 が5の倍数になる k を探します。k=2 のとき 3*2-1=5 となるので、k=2 は解の一つです。

一般解は、3k ≡ 1 \equiv 6 (mod 5)。3と5は互いに素なので3で割って k ≡ 2 (mod 5)。

したがって、ある整数 l を用いて、

k = 5l + 2

と書けます。

ステップ3：元の変数 x を更新する

k の表現を、x = 3k+2 の式に戻します。

x = 3(5l + 2) + 2

x = 15l + 6 + 2

x = 15l + 8

この式 x = 15l + 8 は、最初の2つの合同式 x ≡ 2 (mod 3) と x ≡ 3 (mod 5) を同時に満たすすべての整数を表しています。（実際に、15l+8 を3で割ると2余り、5で割ると3余ることが確認できます。）

これは、x ≡ 8 (mod 15) と同値です。

ステップ4：最後の合同式に代入する

更新された x の表現を、3番目の合同式 x ≡ 2 (mod 7) に代入します。

15l + 8 ≡ 2 (mod 7)

15 \equiv 1 (mod 7) なので、

1 \cdot l + 8 \equiv 2 (mod 7)

l + 1 \equiv 2 (mod 7) （8を7で割った余りは1）

l \equiv 1 (mod 7)

したがって、ある整数 m を用いて、

l = 7m + 1

と書けます。

ステップ5：最終的な解を求める

l の表現を、x = 15l + 8 の式に戻します。

x = 15(7m + 1) + 8

x = 105m + 15 + 8

x = 105m + 23

結論

求める整数 x は、任意の整数 m を用いて x = 105m + 23 と表されます。

これは、合同式で書けば x ≡ 23 (mod 105) となり、法 105 = 3 \times 5 \times 7 に関して、ただ一つの解に定まるという定理の内容と一致しています。

問題が「（正の）最小の数はいくつか」と問うていれば、m=0 として x=23 が答えとなります。

検算

23を3で割ると、23 = 3 \times 7 + 2 → 余り2 (OK)
23を5で割ると、23 = 5 \times 4 + 3 → 余り3 (OK)
23を7で割ると、23 = 7 \times 3 + 2 → 余り2 (OK)

中国の剰余定理が扱う問題は、一見すると単なる数当てパズルのように見えますが、その理論は、整数の合同関係の構造を深く探るものであり、現代では暗号理論（特にRSA暗号の内部計算）やコンピュータ科学など、様々な分野で重要な応用を持っています。不定方程式の解法と合同式の操作を組み合わせることで、このような複雑な条件を満たす整数を体系的に見つけ出すことができるのです。

8. ペル方程式

これまで我々が扱ってきたのは、ax+by=c という形の一次不定方程式でした。しかし、ディオファントス方程式の世界は、次数が2以上の非線形な方程式へと、さらに奥深く広がっています。その中でも、特に有名で、豊かな数学的構造を持つのがペル方程式 (Pell’s Equation) です。この方程式は、その単純な見た目とは裏腹に、その解の構造が無理数や連分数と深く結びついており、整数論の美しさを示す格好の例となっています。

8.1. ペル方程式の定義

【定義】

\(D\) を、平方数ではない正の整数とする。このとき、

x^2 – Dy^2 = 1

という形の二変数二次不定方程式をペル方程式という。

この方程式の整数解 \((x, y)\) を求めることが目標となる。

例

\(D=2\) の場合: \(x^2 – 2y^2 = 1\)
\(D=3\) の場合: \(x^2 – 3y^2 = 1\)
\(D=5\) の場合: \(x^2 – 5y^2 = 1\)

自明な解

どのような \(D\) に対しても、y=0 とすれば x^2=1 となり、x=±1。

したがって、\((x, y) = (\pm 1, 0)\) は、常にペル方程式の整数解です。これを自明な解 (Trivial solution) と呼びます。

ペル方程式の探求の面白さは、この自明な解以外の非自明な解、特に x, y がともに正の整数である解を見つけ出すことにあります。

なぜ \(D\) は平方数ではないのか？

もし \(D\) が平方数、例えば \(D=k^2\) であったとすると、方程式は

x^2 – (ky)^2 = 1

(x-ky)(x+ky) = 1

となります。x, y, k は整数なので、x-ky と x+ky も整数です。

積が1になる2つの整数の組は (1, 1) と (-1, -1) しかありません。

x-ky=1, x+ky=1 を解くと、y=0, x=1。
x-ky=-1, x+ky=-1 を解くと、y=0, x=-1。となり、自明な解しか存在しません。したがって、非自明な解を探求するためには、Dが平方数でないことが本質的な条件となります。

8.2. ペル方程式の解の構造

ペル方程式の解の集合は、驚くほど美しい構造を持っています。

最小解の存在

まず、ラグランジュによって証明された重要な事実として、「\(D\) が平方数でなければ、ペル方程式は必ず非自明な整数解を持つ」ということがあります。

したがって、x, y がともに正の整数である解が、少なくとも一つは存在します。

そのような正の整数解のうち、x の値が最小となる解（それに伴い y の値も最小となる）を、最小解 (Fundamental Solution) と呼び、\((x_1, y_1)\) と書きます。

最小解からの無限の解の生成

ペル方程式のすべての解は、この最小解 \((x_1, y_1)\) から、まるで種から木が育つように、すべて生成することができます。その生成メカニズムは、一見すると奇妙な、無理数を用いた式で記述されます。

方程式 \(x^2 – Dy^2 = 1\) の左辺は、\((x – y\sqrt{D})(x + y\sqrt{D}) = 1\) と因数分解できます。

この形から、\(x+y\sqrt{D}\) という形の数を考えます。

【定理】

ペル方程式 \(x^2 – Dy^2 = 1\) の最小解を \((x_1, y_1)\) とする。

このとき、すべての正の整数解 \((x_n, y_n)\) は、以下の式から生成される。

x_n + y_n\sqrt{D} = (x_1 + y_1\sqrt{D})^n \quad (n = 1, 2, 3, \dots)

右辺の (x_1 + y_1√D)^n を展開し、整数部分 + (整数)√D の形に整理したとき、その整数部分が x_n、√D の係数が y_n となります。

例：\(x^2 – 2y^2 = 1\)

最小解の探索:y=1 のとき x^2 = 3 (xは整数でない)y=2 のとき x^2 = 1 + 2(2^2) = 9 \implies x=3したがって、最小解は \((x_1, y_1) = (3, 2)\) です。
他の解の生成:
- n=2:x_2 + y_2\sqrt{2} = (3+2\sqrt{2})^2= 3^2 + 2(3)(2\sqrt{2}) + (2\sqrt{2})^2= 9 + 12\sqrt{2} + 8 = 17 + 12\sqrt{2}したがって、次の解は \((x_2, y_2) = (17, 12)\)。検算: \(17^2 – 2(12^2) = 289 – 2(144) = 289 – 288 = 1\)。
- n=3:x_3 + y_3\sqrt{2} = (3+2\sqrt{2})^3= (17+12\sqrt{2})(3+2\sqrt{2})= 51 + 34\sqrt{2} + 36\sqrt{2} + 24(2)= 51 + 48 + 70\sqrt{2} = 99 + 70\sqrt{2}したがって、3番目の解は \((x_3, y_3) = (99, 70)\)。

このように、一度最小解を見つけてしまえば、あとは機械的な計算で、次々と大きな解を無限に生成していくことができます。

8.3. 最小解の見つけ方

ペル方程式の理論の難しい部分は、実はこの「最小解」を体系的に見つける方法にあります。それは、\(\sqrt{D}\) の連分数展開という、高校数学の範囲を超える高度な理論と結びついています。

したがって、大学受験レベルでは、

最小解が、試行錯誤で見つけられる程度の小さな値である。
最小解が与えられていて、次の解を求める。
ペル方程式の解の構造に関する知識を問う。といった形での出題がほとんどです。

ペル方程式は、一次不定方程式とは全く異なる、非線形の豊かな構造を持っています。その解が、整数論の問題でありながら、無理数 \(\sqrt{D}\) の代数的な性質と深く結びついているという事実は、数学の異なる分野がいかにして互いに影響し合い、より深い理論を形成していくかを示す、美しい一例と言えるでしょう。

9. ディオファントス方程式

このモジュールで我々が中心的に学んできた一次不定方程式 ax+by=c は、より広大で多様なディオファントス方程式 (Diophantine Equation) の世界への、最初の入り口に過ぎません。ディオファントス方程式とは、その名の通り、古代ギリシャの数学者ディオファントスに由来する、整数解（あるいは有理数解）のみを求める多項式方程式の総称です。一次方程式に限らず、二次、三次、あるいはそれ以上の次数の、また未知数が3つ以上の、ありとあらゆる方程式が含まれます。

このセクションでは、一次不定方程式という我々の現在地を、より広い数学の地図の上に位置づけ、その周辺に広がる有名で歴史的な問題に触れることで、整数論の奥深さと豊かさを概観します。

9.1. ディオファントス方程式の定義と難しさ

【定義】

係数が整数であるような多項式方程式について、その整数解を求める問題、またはその方程式そのものをディオファントス方程式と呼ぶ。

一般的な形:

\(P(x_1, x_2, \dots, x_n) = 0\)

ここで \(P\) は整数係数の多項式であり、\(x_1, x_2, \dots, x_n\) は整数の未知数。

ディオファントス問題の難しさ

一次不定方程式 ax+by=c については、我々は

解が存在するための必要十分条件（cがG.C.D.(a,b)の倍数）
解が存在する場合に、すべての解を求めるアルゴリズムを完全に確立することができました。

しかし、方程式の次数が2以上になると、状況は一変します。

一般的な解法が存在しない: 次数や変数の数が増えると、すべての解を見つけ出す統一的なアルゴリズムは、一般には存在しません。
解の存在判定の困難さ: 与えられた方程式に整数解が一つでも存在するのか、それとも全く存在しないのかを判定すること自体が、極めて困難な問題（一般には決定不能な問題）となります。これは、ヒルベルトの第10問題として知られ、1970年にユーリ・マチャセビッチによって否定的に解決されました。
個別の問題ごとのアプローチ: したがって、非線形のディオファントス方程式の研究は、方程式の「種類」ごと（ペル方程式、楕円曲線など）に、固有の数学理論を駆使して、個別に取り組むことが基本となります。

9.2. 有名なディオファントス方程式の例

1. ピタゴラス方程式（ピタゴラス数）

x^2 + y^2 = z^2

この方程式は、直角三角形の3辺の長さを与える整数の組（ピタゴラス数）を求める問題に対応します。

この方程式には、(3, 4, 5), (5, 12, 13) といった解が無数に存在します。

そして、そのすべての「原始ピタゴラス数」（x, y, z が互いに素である解）は、互いに素な整数 m, n (m>n, 一方が偶数で他方が奇数) を用いて、

\begin{cases}

x = m^2 – n^2 \

y = 2mn \

z = m^2 + n^2

\end{cases}

というパラメトリックな形で、完全に記述できることが知られています。これは、二次ディオファントス方程式が、完全に解ける幸福な例の一つです。

2. ペル方程式

x^2 – Dy^2 = 1

前セクションで見たように、この方程式の解もまた、最小解と無理数 √D を用いて、美しい構造を持つことが分かっています。

3. フェルマーの最終定理

x^n + y^n = z^n \quad (n \ge 3)

17世紀にフェルマーが「この方程式は、nが3以上の整数のとき、自明な解（x,y,zのいずれかが0）以外に整数解を持たない。私は真に驚くべき証明を見つけたが、この余白はそれを書くには狭すぎる」という有名な書き込みを残した問題です。

ピタゴラス方程式の指数を、2から3以上に変えただけで、解の性質は劇的に変化し、非自明な解が一切存在しなくなります。

この予想は、350年以上にわたって多くの数学者の挑戦を退け続け、最終的に1995年にアンドリュー・ワイルズによって、楕円曲線やモジュラー形式といった、現代数学の最先端の理論を駆使して完全に証明されました。この物語は、ディオファントス方程式がいかに深く、豊かな数学的背景を持っているかを示す、象徴的なエピソードです。

4. ウェアリングの問題

「すべての自然数は、4個の平方数の和で表せるか？」「9個の立方数の和で表せるか？」といった、自然数をべき乗数の和で表現する問題です。

例えば、すべての自然数は4つの平方数の和で表せる（ラグランジュの四平方定理）ことが証明されています。

7 = 2^2 + 1^2 + 1^2 + 1^2

15 = 3^2 + 2^2 + 1^2 + 1^2

9.3. 一次不定方程式の位置づけ

この広大なディオファントス方程式の世界において、我々が学んできた一次不定方程式 ax+by=c は、以下のような点で、特別な位置を占めています。

完全な解法: 解の存在条件から一般解の導出まで、完全なアルゴリズムが存在する、数少ない「幸福な」方程式の一つです。
基礎: ユークリッドの互除法や合同式といった、一次不定方程式を解くための道具は、より高度な非線形の問題を考える上でも、基本的な言語や思考法として不可欠な役割を果たします。
入り口: 一次不定方程式の探求は、整数解を求めるという問題の本質、すなわち、連続的な実数の世界とは異なる、離散的で構造的な整数の世界の面白さと難しさを、最初に体験させてくれる、最適な入門となります。

ディオファントス方程式の探求は、個々のパズルを解く楽しみと、その背後にある巨大な数学的構造を発見する喜びが同居する、数学の中でも特に魅力的な分野です。一次不定方程式のマスターは、その豊かで奥深い世界への扉を開く、最初の鍵となるのです。

10. 整数解の存在条件

一次不定方程式 ax+by=c の探求を始めるにあたり、すべての議論の出発点となる、最も根源的な問いがあります。それは、「そもそも、この方程式に整数解は存在するのか？」という問いです。やみくもに特殊解を探し始める前に、解が存在するかどうかを確実に判定できなければ、我々の努力は徒労に終わるかもしれません。この存在条件を判定するための鍵を握るのが、係数 a と b の最大公約数 (G.C.D.) です。

10.1. 存在条件の定理

【定理】

整数係数の一次不定方程式

ax + by = c

が整数解 (x, y) を持つための必要十分条件は、定数項 c が、x の係数 a と y の係数 b の最大公約数 d = G.C.D.(a, b) で割り切れることである。

\text{整数解が存在する} \iff c \text{ は } \text{G.C.D.}(a, b) \text{ の倍数である}

この定理は、方程式を一目見ただけで、解が存在するかどうかを即座に判定することを可能にする、非常に強力なツールです。

例

6x + 9y = 21
- a=6, b=9。G.C.D.(6, 9) = 3。
- c=21。21は3で割り切れる（21 = 3 × 7）。
- したがって、この方程式には整数解が存在する。
10x - 15y = 24
- a=10, b=-15。G.C.D.(10, -15) = G.C.D.(10, 15) = 5。
- c=24。24は5で割り切れない。
- したがって、この方程式には整数解は存在しない。
177x + 52y = 1
- a=177, b=52。G.C.D.(177, 52) = 1。
- c=1。1は1で割り切れる。
- したがって、この方程式には整数解が存在する。（特に、係数が互いに素である場合、G.C.D.(a,b)=1 なので、右辺 c がどのような整数であっても、必ず解が存在します。）

10.2. 存在条件の証明

この定理は「必要十分条件」であるため、証明は二つの方向性（「\(\implies\）」と「\(\impliedby\）」）を示す必要があります。

証明1：必要条件（解が存在する \(\implies\) d|c）

仮定:ax+by=c が、ある整数解 (x_0, y_0) を持つと仮定する。すなわち、ax_0 + by_0 = c が成り立つ。
G.C.D.の性質:d = G.C.D.(a,b) なので、d は a の約数であり、かつ b の約数でもある。したがって、ある整数 a’, b’ を用いて、a=da’, b=db’ と書ける。
代入と結論:これらの表現を、仮定の式に代入する。(da’)x_0 + (db’)y_0 = cd(a’x_0 + b’y_0) = ca’, x_0, b’, y_0 はすべて整数なので、a’x_0 + b’y_0 も整数である。この式は、c が d の倍数であることを、その定義そのものによって示している。したがって、d|c である。

（証明終）

証明2：十分条件（d|c \(\implies\) 解が存在する）

この証明は、ユークリッドの互除法がもたらす重要な帰結であるベズーの等式に基づいています。

ベズーの等式:任意の整数 a, b に対して、その最大公約数 d = G.C.D.(a,b) は、a と b の線形結合として、ax’ + by’ = dを満たすような整数 (x’, y’) が必ず存在する。（この (x’, y’) は、拡張ユークリッド互除法によって具体的に見つけることができるのでした。）

仮定:c が d = G.C.D.(a,b) の倍数であると仮定する。したがって、ある整数 k を用いて、c = kd と書ける。
ベズーの等式を適用:ベズーの等式により、ax’ + by’ = d を満たす整数 x’, y’ が存在する。
式の変形と結論:この等式の両辺を k 倍する。k(ax’ + by’) = kda(kx’) + b(ky’) = kd仮定 c=kd を代入すると、a(kx’) + b(ky’) = cここで、x_0 = kx’, y_0 = ky’ とおけば、k, x’, y’ はすべて整数なので、x_0, y_0 も整数である。したがって、ax+by=c を満たす整数解 (x_0, y_0) が存在することが示された。

（証明終）

10.3. 幾何学的な解釈

一次不定方程式 ax+by=c は、x, y が実数ならば、座標平面上で一本の直線を表します。

この直線上に、x 座標と y 座標がともに整数となる点、すなわち格子点 (Lattice Point) が存在するかどうか、というのが、この問題の幾何学的な意味です。

ax+by=c を変形すると、y = -\frac{a}{b}x + \frac{c}{b}。

この直線が格子点を通るかどうかは、係数 a, b, c の公約数の関係に支配されます。

2x+4y=7 の場合:G.C.D.(2,4)=2。7は2の倍数ではない。解は存在しない。この直線 y = -1/2 x + 7/4 は、どの格子点も通らない。
6x+9y=21 の場合:G.C.D.(6,9)=3。21は3の倍数。解は存在する。この方程式は、両辺を3で割ると 2x+3y=7 と同値になる。この直線 y = -2/3 x + 7/3 は、無数の格子点を通る（例えば (2,1) など）。

整数解の存在条件は、不定方程式の理論全体における「門番」の役割を果たします。この判定法によって、解が存在しない無駄な計算を避け、解が存在する場合にのみ、特殊解、そして一般解を求めるという、確かな道筋へと進むことができるのです。

Module 9：整数の性質(2) 一次不定方程式の総括：無限の解を構造化する技法

本モジュールにおいて、我々は整数論の古典的でありながら中心的なテーマ、一次不定方程式 ax+by=c の完全な攻略法を体系的に学びました。その探求は、闇雲に解を探すのではなく、まず「解は存在するのか」という根源的な問いから始まりました。整数解の存在条件が、係数 a, b の最大公約数が定数項 c を割り切ることである、という厳然たる法則が、我々の探求のすべての出発点となりました。

解の存在が保証された後、我々は無限に広がる解の海の中から、最初の足がかりとなる「特殊解」を一つ釣り上げるための、二つの強力な釣竿を手にしました。一つは、ユークリッドの互除法を逆再生するという、いかなる大物（巨大な係数）でも確実に釣り上げることができる、機械的で信頼性の高いアルゴリズム。もう一つは、合同式を用いて、大きな数の問題を小さな剰余の世界の問題へと変換し、よりスマートに解を捉える、洗練された技法でした。

そして、一つの特殊解 (x_0, y_0) という確かな大地に立った我々は、そこから無限に広がるすべての解、すなわち「一般解」の全体像を明らかにしました。「互いに素」という整数の基本的な性質を駆使することで、すべての解が、基準点である特殊解から (-b/d, a/d) という一定の間隔で、規則正しく格子状に分布しているという、美しい構造が明らかになりました。

この基本理論を核として、我々はさらにその応用範囲を広げました。連立一次不定方程式は「変数消去」によって既知の問題に帰着させ、様々な応用問題は、現実の制約を不等式として課すことで、無限の一般解の中から有限個の現実解を絞り込む、というプロセスを学びました。中国の剰余定理は、この不定方程式の理論が、連立合同式という形で、さらに複雑な条件を Elegantly に解決できることを示してくれました。最後に、ペル方程式やディオファントス方程式への言及は、我々がマスターした一次方程式の理論が、さらに広大で豊かな非線形の世界へと続く、重要な第一歩であることを示唆してくれました。

このモジュールを通じて我々が習得したのは、単なる方程式の解法パターンではありません。それは、無限に存在する解という、一見すると捉えどころのない対象を、最大公約数、互いに素、合同式といった整数の基本構造を用いて分析し、パラメータ k を用いてその全体像を完全に記述しきる、「無限の解を構造化する技法」です。この技法は、代数的な問題解決能力の中核をなし、より高度な数学の世界を探求するための、確固たる自信と論理的基盤を我々に与えてくれるのです。

【基礎 数学(数学A)】Module 9：整数の性質(2) 一次不定方程式

1. 一次不定方程式 ax+by=c の整数解

1.1. 不定方程式とは

1.2. 一次不定方程式 ax+by=c

1.3. 特殊解と一般解

1.4. 整数解は常に存在するのか？

2. ユークリッドの互除法を用いた特殊解の発見

2.1. なぜユークリッドの互除法が使えるのか？

2.2. 特殊解の発見アルゴリズム

2.3. ケーススタディ：177x + 52y = 1

2.4. 一般的な方程式 ax+by=c への拡張

3. 一般解の表現

3.1. 一般解の導出プロセス

3.2. ケーススタディ：177x + 52y = 1 の一般解

3.3. 特殊解の選び方と一般解の表現

4. 連立一次不定方程式

4.1. 基本的な解法プロセス

4.2. ケーススタディ

4.3. 解が存在しないケース

5. 係数が大きい場合の効率的な解法

5.1. 合同式を用いた解法の原理

5.2. ケーススタディ：177x + 52y = 1 (再訪)

5.3. 合同式解法のメリットと使い分け

6. 応用問題（文章題）

6.1. 文章題を解くためのプロセス

6.2. ケーススタディ：買い物の問題

7. 中国の剰余定理

7.1. 問題の起源：「孫子の問題」

7.2. 中国の剰余定理

7.3. 定理の解法：一次不定方程式への帰着

8. ペル方程式

8.1. ペル方程式の定義

8.2. ペル方程式の解の構造

8.3. 最小解の見つけ方

9. ディオファントス方程式

9.1. ディオファントス方程式の定義と難しさ

9.2. 有名なディオファントス方程式の例

9.3. 一次不定方程式の位置づけ

10. 整数解の存在条件

10.1. 存在条件の定理

10.2. 存在条件の証明

10.3. 幾何学的な解釈

Module 9：整数の性質(2) 一次不定方程式の総括：無限の解を構造化する技法

【基礎数学(数学A)】Module 9：整数の性質(2) 一次不定方程式

1.2. 一次不定方程式 `ax+by=c`

2.3. ケーススタディ：`177x + 52y = 1`

2.4. 一般的な方程式 `ax+by=c` への拡張

3.2. ケーススタディ：`177x + 52y = 1` の一般解

5.2. ケーススタディ：`177x + 52y = 1` (再訪)