スポンサーリンク

ユークリッドの互除法の問題の解法

ホームページのリニューアルに伴い一部のページは新しいサイトにリダイレクトされます。

 

ユークリッドの互除法を使って最大公約数を求める問題です。
ユークリッドの互除法に関する知識はユークリッドの互除法と一次不定方程式をご参照ください。

基本問題

1428と7038の最大公約数を求めなさい。

解き方

最大公約数の問題は、大体以下の3つを使いますね。

  1. 素因数分解
  2. ユークリッドの互除法
  3. 最小公倍数

最小公倍数は2数a,bの最大公約数をg、最小公倍数をlとしたときab=lgという性質がありますが、これを使った問題を意図しています。

解説

1428と7038の最大公約数を求めなさい。
今回はユークリッドの互除法の解説になります。

7038を1428で割った商と余りを求めます。
7038=1428\times 4+1326
1つスライドし、1428を1326で割った商と余りを求めます。
1428=1326\times 1+102
1つスライドし、1326を102で割った商と余りを求めます。
1326=102\times 13
割り切れたので、最大公約数は102です。

ちなみに、逆にたどっていってみましょう。
1326=102\times 13
1428=1326\times 1+102=102\times 13+102=102\times 14
7038=1428\times 4+1326=102\times 14 \times 4+102\times 13 =102\times (14\times 4+13)=102 \times 69

終わりに

これだけだと少し退屈かもしれません。
ユークリッドの互除法はユークリッドの互除法の問題の解法でまた必要になります。
あわせてご確認ください。

にほんブログ村 地域生活(街) 東北ブログへ にほんブログ村 地域生活(街) 東北ブログ 米沢情報へ にほんブログ村 教育ブログへ にほんブログ村 教育ブログ 塾教育へ
スポンサーリンク