Diophantine Equations

古代ギリシャの数学者Diophantus（ディオファントス）の墓には彼の生涯を語る文章が書かれていて，それをもとに没年齢を求める一次方程式の応用問題が有名ですが，これはその一次方程式のことではありません．

Diophantine Equations（ディオファントス方程式）は，係数が整数で$ax+by=c$や$x^2+y^2=z^2$などの形をしたindeterminate equation（不定方程式＝解が無数に存在する方程式）の総称で，他にもいくつかのパターンがあります．この中のひとつ，2012年からの日本の高等学校「数学A」に登場した「整数の性質」（2022年度から廃止）で学んだ$ax+by=c$の形の不定方程式は，cがaとbの最大公約数またはその倍数のときに整数解(x, y)が存在し，Bézout's identity（ベズーの等式）と呼ばれています．

簡単な例として，

$2x+3y=1$　…①

の整数解を求めてみましょう．まず簡単な数を代入してみて解を一組見つけます．例えば，

$2･(-1)+3･1=1$　…②

なので$(x,y)=(-1,1)$が一組の解になります．①から②を引くと

$2･(x+1)+3･(y-1)=0$

となり，移項すると

$2･(x+1)=-3･(y-1)$

になります．ここで2と3は互いに素（公約数が1だけ）だから，$x+1$は3の倍数でないといけないので$x+1=3k$（kは整数）と表すことができ，同様に$y-1=-2k$と表せます．よって，①のすべての整数解の組は

$(x,y)=(3k-1,-2k+1)$（kは整数）

と表せます．

もし最初に見つけた解が$(2,-1)$なら，同様にして

$(x,y)=(3k+2,-2k-1)$（kは整数）

となりますが，kの値が一つずれているだけで同じ解集合を表しています．これはグラフでいうと，直線$2x+3y=1$上の，lattice point（格子点＝座標が整数になる点）を表しています．

ところが，

$73x+67y=1$　…③

のような大きい数になると，一組の解が簡単に見つかりません．そんな時はEuclidean Algorithm（ユークリッドの互除法）を使います．

$73=67\cdot 1+6$　より　$6=73-67\cdot 1$

$67=6\cdot 11+1$　より　$1=67-6\cdot 11$

右下の式に右上の式を代入すると，

$1=67-(73-67\cdot 1)\cdot 11=73\cdot (-11)+67\cdot 12$　…④

だから$(x,y)=(-11,12)$が一組の解になります．③から④をひくと

$73(x+11)+67(y-12)=0$

となり，移項すると

$73･(x+11)=-67･(y-12)$

になります．ここで73と67は互いに素だから，$x+11$は67の倍数でないといけないので$x+11=67k$（kは整数）と表すことができ，同様に$y-12=-73k$と表せます．よって，③のすべての整数解の組は

$(x,y)=(67k-11,-73k+12)$（kは整数）

と表せます．

因みに，碑文の問題はDiophantus's riddle（謎）とかDiophantus puzzle（パズル）とか呼ばれていて，一次方程式の応用問題としても有名ですが，Nintendo DSというゲームの"Professor Layton and Pandora's Box（レイトン教授と悪魔の箱）"の第142問目にも登場します．

【Diophantine Equations 問題】
(1) Two farmers agree that pigs are worth 300 dollars and that goats are worth 210 dollars. When one farmer owes the other money, he pays the debt in pigs or goats, with "change" received in the form of goats or pigs as necessary. (For example, a 390 dollar debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way?
(A) 5  (B) 10  (C) 30  (D) 90  (E)  210

(2) Jack and Jill visit the cake shop every day, and Jack always buys jam doughnuts, and Jill chocolate éclairs. The jam doughnuts cost 0.95 each and the chocolate éclairs cost 0.97. At the end of the  week the non-itemised bill from the cake shop is 42.38. How much must each pay?
（解答はこちら）

[Reference]
Diophantus's Riddle
http://mathworld.wolfram.com/DiophantussRiddle.html
Diophantine equation
https://en.wikipedia.org/wiki/Diophantine_equation
Diophantine equation
http://artofproblemsolving.com/wiki/index.php?title=Diophantine_equation
Number Theory Using Modular Arithmetic to Solve Indeterminate Equations
https://trans4mind.com/personal_development/mathematics/numberTheory/indeterminateEquationsCongruences.htm