数学。ユークリッドの互除法についての問題です。 ユークリッドの互除法の原理に、 <r＝0のとき、aと

数学。ユークリッドの互除法についての問題です。

ユークリッドの互除法の原理に、
<r＝0のとき、aとｂの最大公約数はｂである>
とあるので、r＝0となるように式を変えていけばいいというところまでなんとなく分かりました。

ただ、この上の二行が何をしているのかよく分かりません。
今まで位置で覚えて解いてきましたが、
理屈を理解して解けるようになりたいです。

< r≠0のとき、aとｂの最大公約数とｂとrの最大公約数は等しい>という原理を使っているの
かな…とは思いましたが、よく分かりませんでした。教えてください。

No.2 ベストアンサー 回答者： ji6 回答日時： 2017/12/24 10:34

< r≠0のとき、936と273の最大公約数と273と117の最大公約数は等しい>

936と273の最大公約数をGとします。( m,n,k,p は整数 ※互いに素の話は省略)

936と273もGの倍数です。
936と273をそれぞれ何倍かしても、やはりGの倍数です。

Gの倍数同士の差(これが 117 になります)は、やはりGの倍数です。

936=Gm ,273=Gn
→ 936-273×3=G(m-3n) また 936-273×3=117…①
→ 117＝G(m-3n)
→ よって、このGは 273と117の最大公約数として求めることができる。

ノートでは、①のところを 936=273×3+117 とまとめてあるようですね。

この回答へのお礼

なるほど。
疑問に思っていたところが解消されました。ありがとうございました。

お礼日時：2017/12/24 15:51

No.1 回答者： syotao 回答日時： 2017/12/24 10:20

そうです。

< r≠0のとき、aとｂの最大公約数とｂとrの最大公約数は等しい>
という原理を使っているのです。
つまり、1行目から936と273の最大公約数＝273と117の最大公約数です。
そして、2行目から273と117の最大公約数＝117と39の最大公約数です。
この2式から、936と273の最大公約数＝117と39の最大公約数が出てきます。
そして、3行目から117と39の最大公約数＝39だから
936と273の最大公約数＝39となります。

この回答へのお礼

丁寧にありがとうございました。よく分かりました。

お礼日時：2017/12/24 15:52