ディオファントス方程式

The simplest linear Diophantine equation takes the form $${\displaystyle ax+by=c,}$$ where a, b and c are given integers. The solutions are described by the following theorem:

This Diophantine equation has a solution (where x and y are integers) if and only ifcis a multiple of the greatest common divisor ofaandb. Moreover, if(x, y)is a solution, then the other solutions have the form(x + kv, y − ku), wherekis an arbitrary integer, anduandvare the quotients ofaandb(respectively) by the greatest common divisor ofaandb.

Proof: If d is this greatest common divisor, Bézout's identity asserts the existence of integers e and f such that ae + bf = d. If c is a multiple of d, then c = dh for some integer h, and (eh, fh) is a solution. On the other hand, for every pair of integers x and y, the greatest common divisor d of a and b divides ax + by. Thus, if the equation has a solution, then c must be a multiple of d. If a = ud and b = vd, then for every solution (x, y), we have $${\displaystyle {\begin{aligned}a(x+kv)+b(y-ku)&=ax+by+k(av-bu)\\&=ax+by+k(udv-vdu)\\&=ax+by,\end{aligned}}}$$ showing that (x + kv, y − ku) is another solution. Finally, given two solutions such that $${\displaystyle ax_{1}+by_{1}=ax_{2}+by_{2}=c,}$$ one deduces that $${\displaystyle u(x_{2}-x_{1})+v(y_{2}-y_{1})=0.}$$ As u and v are coprime, Euclid's lemma shows that v divides x₂ − x₁, and thus that there exists an integer k such that both $${\displaystyle x_{2}-x_{1}=kv,\quad y_{2}-y_{1}=-ku.}$$ Therefore, $${\displaystyle x_{2}=x_{1}+kv,\quad y_{2}=y_{1}-ku,}$$ which completes the proof.

The Chinese remainder theorem describes an important class of linear Diophantine systems of equations: let ${\displaystyle n_{1},\dots ,n_{k}}$ be kpairwise coprime integers greater than one, ${\displaystyle a_{1},\dots ,a_{k}}$kは任意の整数であり、N は積である。${\displaystyle n_{1}\cdots n_{k}.}$中国剰余定理は、以下の線形ディオファントス方程式系がただ一つの解を持つことを主張する。${\displaystyle (x,x_{1},\dots ,x_{k})}$0 ≤ x < Nであり、他の解はxにNの倍数を加えることによって得られる。 $${\displaystyle {\begin{aligned}x&=a_{1}+n_{1}\,x_{1}\\&\;\;\vdots \\x&=a_{k}+n_{k}\,x_{k}\end{aligned}}}$$

より一般的には、線形ディオファントス方程式のすべての系は、体上の線形方程式の系を解くために簡約行階段形を使用するのと同様の方法で、その行列のスミス正規形を計算することによって解くことができます。行列表記を使用すると、線形ディオファントス方程式のすべての系は次のように書くことができます 。$${\displaystyle AX=C,}$$ ここで、Aはm × nの整数行列、Xはn ×1 の未知数列行列、 Cはm ×1の整数列行列である。

Aの Smith 標準形の計算により、それぞれm × mとn × nの次元を持つ 2 つのユニモジュラー行列(つまり、整数上で可逆であり、行列式が ±1 である行列) UとV が得られ、行列は次のようになります。 $${\displaystyle B=[b_{i,j}]=UAV}$$ は、iがある整数kより大きくない場合にb _i,iがゼロではなく、他のすべての要素がゼロであるようなものである。したがって、解くべきシステムは次のように書き換えることができる。 $${\displaystyle B(V^{-1}X)=UC.}$$V ⁻¹ Xの要素をy _i、D = UCの要素をd _i とすると、次のシステムが得られる。 $${\displaystyle {\begin{aligned}&b_{i,i}y_{i}=d_{i},\quad 1\leq i\leq k\\&0y_{i}=d_{i},\quad k<i\leq n.\end{aligned}}}$$

このシステムは、次の意味で与えられたシステムと同等です。整数の列行列xが与えられたシステムの解であるのは、By = Dとなるような整数の列行列yに対してx = Vyである場合のみです。

したがって、このシステムは、 i ≤ kの場合にb _{i,i が}d _iを割り切り、i > kの場合にd _i = 0 である場合に限り解を持つ。この条件が満たされる場合、与えられたシステムの解は次のようになる。 $${\displaystyle V\,{\begin{bmatrix}{\frac {d_{1}}{b_{1,1}}}\\\vdots \\{\frac {d_{k}}{b_{k,k}}}\\h_{k+1}\\\vdots \\h_{n}\end{bmatrix}}\,,}$$ ここで、h _{k +1}、 …、h _nは任意の整数である。

エルミート標準形は、線形ディオファントス方程式の連立方程式を解くためにも使用できます。ただし、エルミート標準形は直接解を与えるものではありません。エルミート標準形から解を得るには、いくつかの線形方程式を順次解く必要があります。それにもかかわらず、リチャード・ジッペルは、スミス標準形は「線形ディオファントス方程式を解くために実際に必要なものよりもやや多い。方程式を対角形式に還元する代わりに、それを三角形にするだけでよく、これをエルミート標準形と呼ぶ。エルミート標準形は、スミス標準形よりも計算がはるかに簡単である」と書いています。^{[ 6 ]}

整数線形計画法は、不等式も含む線形システムの整数解（ある意味で最適解）を見つけることに相当します。したがって、線形ディオファントス方程式のシステムはこの文脈では基本であり、整数計画法の教科書には通常、線形ディオファントス方程式のシステムが扱われています。^{[ 7 ]}

2次同次ディオファントス方程式は解きやすい。標準的な解法は2段階で進む。まず、1つの解を見つけるか、解が存在しないことを証明する。解が見つかったら、すべての解を導き出す。

解が存在しないことを証明するには、方程式を p を法として簡約すればよい。例えば、ディオファントス方程式

${\displaystyle x^{2}+y^{2}=3z^{2},}$

自明な解(0, 0, 0)以外に解はありません。実際、x、y、z を最大公約数で割ると、互いに素であると仮定できます。法 4 の平方数は 0 と 1 に合同です。したがって、等式の左辺は 0、1、または 2 に合同であり、右辺は 0 または 3 に合同です。したがって、等式はx、y、z がすべて偶数で、互いに素でない場合にのみ成立します。したがって、唯一の解は自明な解(0, 0, 0)です。これは、半径 の円上に有理点が存在しないことを示しています。$\displaystyle {\sqrt {3}}}$原点を中心とする。

より一般的に言えば、ハッセの原理は、2次の同次ディオファントス方程式が整数解を持つかどうかを判定し、存在する場合には解を計算することを可能にする。

非自明な整数解が分かっている場合、他のすべての解は次のようにして求めることができる。

ディオファントス分析で問われる質問には以下のようなものがある。

1. 何か解決策はありますか？
2. 目視で簡単に見つけられるもの以外に、何か解決策はありますか？
3. 解は有限個存在するのか、それとも無限個存在するのか？
4. 理論上、すべての解決策を見出すことは可能だろうか？
5. 実際に解の完全なリストを計算することは可能だろうか？

これらの伝統的な問題はしばしば何世紀にもわたって未解決のまま放置され、数学者たちはそれらを単なるパズルとして扱うのではなく、徐々にその奥深さを理解するようになった（場合によっては）。

父親の年齢を数字ABで表すと、息子の年齢BAの逆数になります。また、父親の年齢は息子の年齢の2倍より1小さいです。彼らは何歳でしょうか？これらの条件から、10 A + B = 2(10 B + A ) – 1、つまり19 B – 8 A = 1という方程式が得られます。このような線形方程式の一般的な解法は上に示されていますが、単純に調べるとA = 7、B = 3となり、AB = 73歳、BA = 37歳となります。AとBが0から9までの整数である場合、これが唯一の解であることは容易に示せます。

娯楽数学における多くの有名なパズルは、砲弾問題、アルキメデスの牛問題、猿とココナッツ問題など、ディオファントス方程式につながる。

1637年、ピエール・ド・フェルマーは『算術』の余白にこう書き記した。「立方を2つの立方体に分割することは不可能であり、4乗を2つの4乗に分割することも不可能であり、一般に、2乗より大きい任意のべき乗を2つの同じべき乗に分割することも不可能である。」より現代的な言葉で言えば、「方程式a ⁿ + b ⁿ = c ⁿは、2より大きい任意のnに対して解を持たない。」これに続いて彼はこう書いた。「私はこの命題の実に素晴らしい証明を発見したが、この余白は狭すぎて書ききれない。」しかし、このような証明は数世紀にわたって数学者たちを悩ませ、そのため彼のこの記述はフェルマーの最終定理として有名になった。それが証明されたのは1995年、イギリスの数学者アンドリュー・ワイルズによってであった。

1657年、フェルマーはディオファントス方程式61 x ² + 1 = y ²を解こうと試みた（この方程式は1000年以上前にブラフマグプタによって解かれていた）。この方程式は最終的に18世紀初頭にオイラーによって解かれ、彼は他にも多くのディオファントス方程式を解いた。正の整数におけるこの方程式の最小解はx = 226153980、y = 1766319049である（チャクラヴァラ法を参照）。

1900年、ダフィット・ヒルベルトは、すべてのディオファントス方程式の解の存在可能性を、彼の基本問題の10番目として提案した。1970年、ユーリ・マティヤセヴィチは、ジュリア・ロビンソン、マーティン・デイヴィス、ヒラリー・パトナムの研究に基づいて、すべてのディオファントス方程式を解くための一般的なアルゴリズムは存在しないことを証明し、この問題を否定的に解決した。

ディオファントス幾何学は、代数幾何学の手法を応用したもので、幾何学的な意味も持つ方程式を扱います。ディオファントス幾何学の中心となる概念は、有理点、すなわち多項式方程式または多項式方程式系の解であり、これは、代数的に閉じていない体Kにおけるベクトルです。

ディオファントス方程式を解く、あるいは解が存在しないことを証明する最も古い一般的な方法は、ピエール・ド・フェルマーによって導入された無限降下法である。もう一つの一般的な方法は、すべての素数を法とするモジュラー演算を用いて解を求めるハッセの原理である。多くの改良が加えられたにもかかわらず、これらの方法ではほとんどのディオファントス方程式を解くことはできない。

ディオファントス方程式を解くことの難しさは、 1900年にダフィット・ヒルベルトによって提起されたヒルベルトの第10問題によってよく示されています。この問題は、整数係数を持つ与えられた多項式ディオファントス方程式が整数解を持つかどうかを判定するアルゴリズムを見つけることでした。マティヤセビッチの定理は、そのようなアルゴリズムは存在しないことを示唆しています。

20世紀には、代数幾何学を用いる新しいアプローチが深く研究されてきた。実際、ディオファントス方程式は超曲面の方程式と見なすことができ、その方程式の解は、超曲面上の整数座標を持つ点である。

このアプローチは最終的に、 1637年頃に証明なしで述べられていたフェルマーの最終定理の、1994年のアンドリュー・ワイルズによる証明へとつながった。これは、ディオファントス方程式を解くことの難しさを示すもう一つの例である。

無限ディオファントス方程式の例は次のとおりです。 $${\displaystyle n=a^{2}+2b^{2}+3c^{2}+4d^{2}+5e^{2}+\cdots ,}$$ これは「与えられた整数n を、平方数＋平方数の 2 倍＋平方数の 3 倍…の和として表す方法はいくつあるか？」と表現できます。各nについてこれを行う方法の数は整数列を形成します。無限ディオファントス方程式は、シータ関数と無限次元格子に関連しています。この方程式は、任意の正のnに対して常に解を持ちます。^{[ 9 ]}これを以下と比較してください。 $${\displaystyle n=a^{2}+4b^{2}+9c^{2}+16d^{2}+25e^{2}+\cdots ,}$$これは必ずしも正のn に対して解を持つとは限りません。