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

合同式を使えば、簡単に解ける！

ところが、合同式を使えば、簡単に解けてしまいます。

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

[1] 以下、$\rm mod~23$ とする。
[2] $56x-23y\equiv1$
[3] $56x\equiv1$
[4] $(46+10)x\equiv1$$
[5] $10x\equiv1\equiv24\equiv47\equiv70$
[6] $10x \equiv 70$で、$10$と$23$は互いに素であるから、
[7] $x \equiv 7$
[8] よって、$k$ を整数として、$x=23k+7$
[9] 与式に代入して、$y=56k+17~~$

答　$x=23k+7,~$$y=56k+17~~$($k$ は整数)

何をやっているか分からない人が多いと思うので、詳しく解説します。

不定整数方程式を解く手順

[1] $x,~y$ の係数のうち、小さい方の$\rm mod$をとる。この場合は、$\pmod{23}$とする。
[2] $56x-23y=1$であるから、$56x-23y\equiv1$が成り立つ。
[3] $23\equiv0\pmod{23}$であるから、$56x\equiv1$となる。
[4] この$x$の係数をどんどんと小さくして、最終的に$1$にすることを目指す。とりあえず、大雑把に小さくする。この場合は、$10x\equiv1$
[5] 右辺に法の$23$をどんどんと足して行って、$x$の係数の$10$で割り切れる数を見つける。$23\equiv0$であるから、右辺に$23$をどんどん足しても、合同である。
[6] この場合は、$10x\equiv70$。
[7] 両辺を$10$で割って、$x\equiv7\pmod{23}$を導く。その際、「$10$と$23$は互いに素であるから」と断る（理由は後ほど説明）
[8] よって、$x=23k+7~~$($k$は整数) と $x$ が求まる。
[9] 与式に代入して、$y$を求める。

従来から合同式を使って不定整数方程式を解く方法は、紹介されていましたが、Tommy先生が、誰でも解ける工夫をしました。それが、[5]です。