ロシア人のマチアセビッチにより，すべてのディオファントス方程式（不定方程式）の解の存否を判定するアルゴリズムが存在しないことが証明されています．一般に３変数以上のディオファントス方程式を解く有力な方法はまったく見つかっておらず，たとえば，ｘ^3 ＋ｙ^3 ＋ｚ^3 −３＝０が（１，１，１），（４，４，−５）とその並び換え以外の整数解をもつかどうかすらわかっていません．

　この証明にはフィボナッチ数の整除性のアイディアを拡張したものが使われているそうです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】マチアセビッチの補題

　マチアセビッチの補題とは「Ｆmが（Ｆn）^2の倍数であること」＝「ｍがｎＦnの倍数であること」が同値であるというものです．

　Ｆm＝０　　（ｍｏｄ　Ｆn）であればｍ＝ｋｎはわかっていますから，

Ｆkn＝０　　（ｍｏｄ　Ｆn^2）

かどうかを調べてみます．

Ｆn≠０　　（ｍｏｄ　Ｆn^2）

　Ｆn+1＝Ｆn-1　　（ｍｏｄ　Ｆn）より

　　Ｆ2n＝ＦnＦn+1＋Ｆn-1Ｆn＝２ＦnＦn+1　　（ｍｏｄ　Ｆn^2）

　　Ｆ2n+1＝Ｆn+1^2＋Ｆn^2＝２Ｆn+1^2　　（ｍｏｄ　Ｆn^2）

　　Ｆ3n＝Ｆ2nＦn+1＋Ｆ2n-1Ｆn＝３Ｆn+1^2Ｆn　　（ｍｏｄ　Ｆn^2）

　　Ｆ3n+1＝Ｆ2n+1Ｆn+1＋Ｆ2nＦn＝Ｆn+1^3　　（ｍｏｄ　Ｆn^2）

　一般に，

　　Ｆkn＝ｋＦnＦn+1^k-1，Ｆkn+1＝Ｆn+1^k　　（ｍｏｄ　Ｆn^2）

ここで，Ｆn+1とＦnは互いに素であるから，

　　「Ｆkn＝０　　（ｍｏｄ　Ｆn^2）」＝「ｋＦn＝０　　（ｍｏｄ　Ｆn^2）」＝「ｋ＝０　　（ｍｏｄ　Ｆn^2）」

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【補】１９７１年，旧ソ連のマチアセビッチは，素数全体をあるひとつのディオファントス方程式の解として表すことにも成功しています．すなわち，すべての素数をつくる式を生み出したことになるのですが，その式は３７次で２４個の変数をもつ多項式と２１次で２１個の変数をもつ多項式でした．これらの多項式は負の値もとり，また，素数は多項式の値として繰り返し出現します．

　すべての素数をもれなくつくり，しかも素数以外はつくらない公式は知られていません．素数を完全に定義する式が存在することは証明されていませんし，存在しないともわかっていません．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝