不定方定式（ディオファントス方程式）－合同式の応用－

不定方程式について

古代ギリシャの数学者ディオファントスについては、以前書いておきました。ディオファントスは「数論（アリトメティカ)13巻」に数についての知見を書き記しました。ディオファントスは、不定方程式と言われる1次式や2次式の整数解をどう解くかを詳しく研究しています。その研究は、フェルマーにつがれ、さらにはガウスによって整数論として体系化してゆきます。さらに素数論としてリーマンなどの研究につながってゆきます。ディオファントス－数論のはじまり－

合同式による整数方程式の解法

合同式は、整数の余りの計算法としてガウスによって考えられました。合同式を使うことによって、割合簡単に整数解を求めることができます。使いこなせるようにしておいて損はないと思います。

合同式の定義・性質

１）合同式の定義

\(a,b\)を正の整数とし、正の整数\(c\)で割ったときの余りが等しいとき、\(a\)と\(b\)は\(c\)を法として合同といい、
\(a≡b　(mod　c)\)
と書きます。これは、\(a－b\)が\(c\)で割り切れるときと同値です。

２）合同式の基本公式

\(a≡b　(mod　m)，c≡d（mod　m)\)ならば、
a)　\(a+ｃ≡b+d、a－c≡b－d　(mod　m)\)
ｂ）\(ac≡bd（mod　m)\)
c)　\(a^n≡b^n　(mod　m)\)　\(n\)は自然数

不定方程式の合同式による解法

不定方程式（整数方程式）は、通常は、特殊解を１つ求め、未知数が整数であることを利用して解くのが普通の方法です。特殊解を求めるとき、ユークリッドの互除法を使うのが、受験数学の方法です。数Ⅰの整数の問題として、よく出題されています。（センター試験など）これを合同式を使う方法をとれば、簡単に求めることができます。整数の問題は、合同式を使いこなせるようにすべきだと思います。

【例題1】

\(13x+17y＝193･･････････①\)の整数解を求めてください。

【解答1】

①の不定方程式は、\(17y≡193　(mod　13)\)　と同値です。[\(13x≡193　(mod　17)\)でも同等です。]
これは、\(4y≡11≡24　(mod　13)\)です。
\(４\)と\(13\)は互いに素ですから、\(y≡6　(mod13)\)となります。
よって、\(y=6+13ｋ　(ｋ＝0,±1，±2，････････）\)
①から、\(x=7－17ｋ\)　従って
\((x,y)＝(7－17ｋ,6+13ｋ)\)となります。\(（k=0,±1，±2，･･････････）\)

（注）合同式で割り算をするときは、同値性に十分注意してください。

【別解1】関連する整数解の問題がこのリンクにあります。整数解の問題－整数方程式の解き方－

①を普通の方法で解くと次のようになります。

①の特殊解を１つ求めます。直感で、\((x,y)＝(4,－3)\)が求まれば、これで、一般解はすぐに求まります。
特殊解が求まらないときは、ユークリッドの互助法で求めます。

\(17=13ｘ1＋4,　13＝4ｘ3＋1\)　この2式から、\(13＝(17－13ｘ1)ｘ3+1\)
よって、\(13ｘ4－3ｘ17＝1\)この両辺に193を掛けると、
\(772ｘ13－579ｘ17＝193\)･･･････②
①－②から、\(13(ｘ－772)＝17(ｙ+579)\)･････････③
これから、\(13と17\)は互いに素ですから、\((x,y)＝(772+17t,－579+13t)、tは整数\)です。

③をよく考えると、\(13,17\)は互いに素ですから、\(x≡772≡7　(mod17)\)です。
よって、\(x=7+17t\)となり、\(y=6－13t\)です。ここで\(t＝-k\)とおきかえれば、【解答1】と
同じになります。