Question

さ

ユークリッドの互除法でなぜ必ず互いに素で無ければならないのですか？

Answer 1

ジャスタウェイ

別にこのような問題は互いに素にならなくてもいいんです。
例えばma・x+mb・y=c(a,b,mは整数。a,bは互いに素)とします。
ma・x+mb・y=c
=m(a・x+b・y)=c
この問題は整数解を求める問題なので、x,yには整数が入ります。
従って、aは整数なので、a・x+b・yも整数となります。
mもa・x+b・yも整数なのでcも整数となります。また、cはmの倍数ということにもなります。
よって両辺mで割ってあげると、
a・x+b・y=d(d=c/m,dは整数)
となります。
この類の問題は、最終的には互いに素となるのでユークリッドの互除法が使えるようになります！
ちょっと難しいですね😅

ジャスタウェイ

9行目
❌従って、aは･･･
⭕️従って、a,bは･･･
誤字ってすみませんm(*_ _)m

ジャスタウェイ

ちなみに、上の方が言っている通り、ユークリッドの互除法とは最大公約数を求めるというものであり、使う時は互いに素であるという決まりはありません。たまたまこのような問題は左辺の係数が互いに素になるので(左辺)=1をユークリッドの互除法で作ることができます。(左辺)=1、(右辺)=1で(左辺)=(右辺)となり、特殊解を見つけることができます！

Answer 2

NN

何と何が互いに素である必要があるのでしょうか......?

さ

例えば4x+7y＝1などの方程式の整数解を求める場合です。

NN

4と7が
ということですね
ax+by=1について
a,bの最大公約数をgとすると
a=gk、b=gmである整数k,mが存在することになります
gkx+gmy=1
g(kx+my)=1
により、kx+myは整数なのでg=1でなければ等式が成立しなくなります。

さ

ありがとうございます。
その場合、ユークリッドの互除法が絡んでくる問題は全て互いに素でなければならないという認識でいいでしょうか。

NN

そこがわかりません
この整数の方程式は互いに素でなければ成立しません

ユークリッドの余除法はそもそも最大公約数を求める方法です。ここにつながりは無いです。