不定整数方程式を合同式を使って簡単に解く方法

ユークリッドの互除法はウザい！

不定整数方程式とは次のような問題です。

\(56x-23y=1\cdots\)① を満たす整数 \(x,~y\) の組を全て求めよ。

この\(x,~y\)を満たす整数を\(1\)組見つけることができたら、この方程式は解けます。しかし、この問題の場合は、それが簡単には求まりません。結論をいうと、整数解の組の一つは、\(x=7,~y=17\) です。こんな解を試行錯誤で求めることは不可能です。

そういう場合は、ユークリッドの互除法を使う方法が、教科書に載っています。きちんと読まなくていいです。ざっと眺めて下さい。

\(56\) と \(23\) に互除法を計算を行うと
\(56=23\cdot2+10\)
\(23=10\cdot2+3\)
\(10=3\cdot3+1\)
それぞれ移項すると
\(10=56-23\cdot2\)
\(3=23-10\cdot2\)
\(1=10-3\cdot3\)
よって、
\(1=10-3\cdot3\)
\(=10-(23-10\cdot2)\cdot3\)
\(=10\cdot7+23\cdot(-3)\)
\(=(56-23\cdot2)\cdot7+23\cdot(-3)\)
\(=56\cdot7+23\cdot(-17)\)
\(=56\cdot7-23\cdot17\cdots\)②
よって、\(x=7,~y=17\) は \(56x-23y=1\) の \(1\) つの解である。
①\(-\)②より、
\(56(x-7)-23(y-17)=0\)
\(56(x-7)=23(y-17)\cdots\)③
\(56\) と \(23\) は互いに素であるから、
\(x-7\) は \(23\) の倍数である。
よって、\(k\) を整数として、
\(x-7=23k\)
③より \(y-17=56k\)
よって、\(x=23k+7,~\)\(y=56k+17~~\)(\(k\) は整数)