不定方程式\(ax＋by＝1\)を満たす整数解の組\((x, y)\) の求め方

これを解くには,　ユークリッドの互除法を使った方法と,　合同式を用いた方法により解くことができます。どちらが自分にとってわかりやすいか,　\(76x+59y=1\)・・・①を例に考えていきます。

ユークリッドの互除法を用いた解き方

まず,　76を59で割り,　商と余りを出します。

\(76=59×1+17\)・・・②

同様に59を17で割っていき,　余りが1になるまで計算していきます。

\(59=17×3+8・・・③\)

\(17=8×2+1・・・④\)

②,　③,　④をあまり\(=\)の式に変形すると, 　

\(\color{blue}{76}-\color{red}{59}×1=\color{magenta}{17}\)・・・⑤

\(\color{red}{59}-\color{magenta}{17}×3=\color{yellowgreen}{8}\)・・・⑥

\(\color{magenta}{17}-\color{yellowgreen}{8}×2=1\)・・・⑦

⑦式は,　\(17x+8y=1\)を満たす整数の組の1つは,　\((x, 　y)=(1,　-2)\)であることを示しています。

私たちのゴールは\(76×〇+59×△=1\)となる〇や△を見つけることです。

そこで, 不要な17や8を⑥,　⑤式を利用して①式の形にします。

⑦式に⑥式を代入すると,

\( \color{magenta}{17} -( \color{red}{59} - \color{magenta}{17} ×3)×2=1\)

\( \color{magenta}{17} ,　 \color{red}{59} \)を残すように変形すると,

\( \color{magenta}{17} - \color{red}{59} ×2+ \color{magenta}{17} ×3×2=1\)

\( \color{magenta}{17} ×7- \color{red}{59} ×2=1\)・・・⑧

今度は不要な\( \color{magenta}{17} \)を消去するために,　⑤を代入すると,

\(( \color{blue}{76} - \color{red}{59} ×1)×7- \color{red}{59} ×2=1\)

\( \color{blue}{76} ×7-59×7- \color{red}{59} ×2=1\)

\( \color{blue}{76} ×7- \color{red}{59} ×9=1\)

よって,　\((x, y)=(7, -9)\)が①を満たす整数解の1つです。

\begin{cases}76x+59y=1・・・①\\76×7+59×(-9)=1・・・⑨\end{cases}

①\(-\)⑨より,

\(76(x-7)=-59(y+9)\)・・・⑩

76と59は互いに素であるので,　\(x-7\)は59の倍数である。

\(x-7=59k (k\)は整数）とおけます。これを⑩に代入すると

\(76×59k=-59(y+9)\) よって,　\(y+9=-76k\)

\(y=-76k-9\)

これより,　\((x, y)=(59k+7, -76k-9) (k\)は整数）

合同式を用いた解き方

76と59の小さい方である,　59を法として考えます。すると,　①は,　\(76x≡1\)(mod 59)・・・⑪

76=59×1+17であるから,　\(76≡17\)(mod 59)　すなわち,　\(17x≡1\)(mod 59)・・・⑫

次に17に数字を掛けて,　59を超えるようにしていきます。3だと届かないので,　⑫の両辺を4倍すると,

\(68x≡4\)　すなわち,　\(9x≡4\)(mod 59)・・・⑬

⑫\(-\)⑬より,　\(8x≡-3\)(mod 59)・・・⑭

⑬\(-\)⑭より,　\(x≡7\)(mod 59)・・・⑮

よって,　\(x=59k+7(k\)は整数)

\(76x+59y=1\)・・・① の\(x\)に7を代入すると,

\(59y=1-76×7=-531,　y=-9\)

これより,　\(76×7＋59×(-9)=1\)・・・⑯

①に\(x=59k+7\)を代入すると,　\(76(59k+7)+59y=1\)

\(76×7+59(76k+y)=1\) ・・・⑰

⑯\(-\)⑰より,　\(76k+y=-9\)

よって,　\(x=59k+7,　y=-76k-9(k\)は整数)

いかがでしたでしょうか。ここはなかなかわかりづらいところだと思います。気になる箇所がある場合は質問していただければと思います！