ユークリッドの互除法

質問

二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。
そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。
しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。
これまでの書き込みを見ても理解ができませんでした。
どなたか分かりやすくお教えください。

回答No.4

noname#101087 · ベストアンサー

# です。
(互除法は伝家の宝刀、じゃなくて錆だらけ。
うっかり抜けないのです。とは言え、かなり気ままに勘定してます....)

>4*4+1=17の両辺に（-3)を掛けるのは、4x-3=17yの式に、-3が出てくるからですか?

Certainly !

>>4x≡3 (mod17) の(一般?)解は、x=-12+17*m　: m = 整数。ふつうは 0≦x < 17 をとり、4*(5)-3=17*(1) とするようですが。
>で、4x-3=17yが、x=-12+17*mとなぜ変形できるのですか？
>また、4に5を掛けるのはなぜですか？直感ですか?

4x-3=17y の解の一つが x=-12, y=-3 だとわかり、その x に 0(mod 17) = 17*m を加えたものも解のはずだとみてます。
5 というのは、-12+17*m のうち 0≦x < 17 になるものです。

お礼

ありがとうございました、やっと分かりました。
d=ax+by（dはa,bの最大公約数）としたとき、x,yはユークリッドの互除法で求められる、と説明があったのですが、何を何で割り、どの余りで商を割ればいいのか、さっぱり分かりませんでした。
与えられた整数a,bの最大公約数は互除法で求められるのは知っていましたが、d=ax+byのような式の特殊解（特殊解がわかれば一般解も分かる）が、どうして互除法で分かるのだろう、って謎でした。
このサイトをみても、互除法でどうぞ、くらいの説明しかなく、実際の計算はどうするのか分からなくて困りました。分かっている人にとってはバカバカしいのでしょうが、頭の良い人は、頭の悪い者の分からないことが分からないようで（笑）

回答No.3

koko_u_

こうやって質問が途中で変わるのは好きくないけど。

>4x≡3（mod17）の特殊解を求める際、4x-3=17yと置け、
合同式の意味が理解できないということですか？

4x≡3（mod17）とは　4x - 3 が 17 で割り切れるということです。
すなわち、ある整数 y をもって 17y = 4x - 3 ということ。

回答No.2

noname#101087

>4x≡3（mod17）の特殊解を求める際、4x-3=17yと置け、それがユークリッドの互除法を使うとなぜ特殊解が分かるのか...

17を4で割ると、4あまり1。つまり、4*4+1=17 。
これを (-3) 倍して、4*(-12)-3=17*(-3) 。
これは、4x-3=17y にて x=-12, y=-3 としたものですね。特殊解というのはこれでしょうか ?

4x≡3 (mod17) の(一般?)解は、x=-12+17*m　: m = 整数。
ふつうは 0≦x < 17 をとり、4*(5)-3=17*(1) とするようですが。

補足

相当頭が悪くて、迷惑をおかけします。申し訳ありません。

4*4+1=17の両辺に（-3)を掛けるのは、4x-3=17yの式に、-3が出てくるからですか?

それと
4x≡3 (mod17) の(一般?)解は、x=-12+17*m　: m = 整数。
ふつうは 0≦x < 17 をとり、4*(5)-3=17*(1) とするようですが。

で、4x-3=17yが、x=-12+17*mとなぜ変形できるのですか？
また、4に5を掛けるのはなぜですか？直感ですか?

回答No.1

koko_u_

ユークリッドの互除法の計算を逆まわしするだけ。

例)
a = 27 b = 69

69 = 27×2 + 15 … (1)
27 = 15×1 + 12 … (2)
15 = 12×1 + 3 … (3)
12 = 3×4

よって d = 3 ← (3) の余り
(3) を逆にして
3 = 15 + 12×(-1) … (3)'

15 と 12 の線形和を得た。

(2) より 12 = 27 + 15×(-1) だから、これを (3)' に代入する
3 = 15 + {27 + 15×(-1)}×(-1)
= 27×(-1) + 15×{1 + (-1)×(-1)} … (2)'

27 と 15 の線形和を得た。

(1) より 15 = 69 + 27×(-2) だから、これを (2)' に代入する
3 = 27×(-1) + {69 + 27×(-2)}×{1 + (-1)×(-1)}
= 69×{1 + (-1)×(-1)} + 27×{(-1) + (-2)×(-1)×(-1)} … (1)'

69 と 27 の線形和を得た。

という感じ。ユークリッドの互除法の証明も、結局上の例を文字 q_i や r_i に置き換えているだけのはず。

(教訓)
自分で幾つか計算すればすぐわかる。

お礼

補足でお尋ねします。
最初に整数が与えられていれば、逆回しも理解できます。
でも具体的には、4x≡3（mod17）の特殊解を求める際、4x-3=17yと置け、それがユークリッドの互除法を使うとなぜ特殊解が分かるのか、関連が理解できないのです。