「不定方程式 ax + by = 1の整数解x,yを求めよ」
こういった問題を求めるためには、ユークリッドの互除法を使います。
具体的な解法は、こちらの記事で解説しています。→【Python】不定方程式の整数解を求める方法を世界一わかりやすく解説！
それはそうと、こういった問題では、aとbは互いに素であるはずです。互いに素でなければ、問題として成立しません。
今回の記事では、「なぜaとbが互いに素である必要があるのか？」について解説していきます。
「互いに素」とは？
そもそも、「互いに素」というのは、共通の約数（公約数）が１しかないということです。
例えば、15と27は、どちらも3で割り切れます。もちろん整数なので１でも割り切れます。つまり、互いに素ではありません。
例えば、15と26は、１以外には共通で割り切れる数字がありません。なので、互いに素であるということになります。
ax + by = 1では、aとbが互いに素である理由とは？
ここでは、逆に互いに素ではなかった場合にどうなるかを考えてみます。
例えば、aもbも2で割り切れるとしましょう。
そして、式を変形をしていくと、次のようになります。
ax + by = 1
2a’x + 2b’ y= 1
2(a’x + b’y) = 1
a’x + b’y = 1/2…①
この時、a’, b’, x, yは整数なので、a’x + b’yも整数になります。
そうなると、①の式が成りたちません。
２以外の場合は、2をcなどの文字に置き換えてみれば、同様に証明することができます。
コメント