ユークリッド互除法のやり方!最大公約数を求める手順をイチから解説!




高校数学Aで学習する整数の性質の単元から

「ユークリッドの互除法のやり方」

についてイチから解説していきます。

 

この記事を通して、互除法のやり方をマスターして、

スラスラと最大公約数が求めれるようになりましょう!

ユークリッドの互除法とは

自然数 \(a, \ b\) について、\(a\) を \(b\) で割ったときの余りを \(r\) とすると、

\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しい。

という性質があります。

これを利用して、最大公約数を求める方法のことをユークリッドの互除法、または互除法といいます。

 

例えば、629と259の最大公約数を求める場合。

>最大公約数、最小公倍数の求め方と性質をイチから解説!

ここで学習した通り、素因数分解を利用して考えることもできるのですが、

629,259ともに素因数分解をするのが難しいですよね(^^;)

割れる数を探すのに一苦労です…

 

そんなときに役に立つのが互除法を使ったやり方になります。

次の章で、互除法のやり方について確認していきましょう。

ユークリッドの互除法のやり方

【問題】

629,259の最大公約数を求めよ。

まず、\(629 \div 259\) を計算しましょう。

すると、「629と259の最大公約数」と「259と111の最大公約数」が等しいことが分かります。

 

次に、\(259 \div 111\) を計算しましょう。

すると、「259と111の最大公約数」と「111と37の最大公約数」が等しいことが分かります。

 

さらに繰り返し計算していきます。\(111 \div 37\) を計算しましょう。

すると、余りが0になりました。

このように余りが0になるまで割り算を続けていきます。

余りが0になった(割り切れた)ことから、111と37の最大公約数は37であることが分かります。

 

つまり、このように629と259の最大公約数も37になるってことが分かりました。

答え

$$37$$

 

大きい数どうしの最大公約数は見つけにくいものですが、

これを小さな数に変換していくことによって、最大公約数を見つけやすくしてるんですね!

 

互除法の筆算のやり方

こちらの章では、互除法の筆算のやり方について紹介しておきます。

さっきと同じ問題を、今度は筆算を用いたやり方で求めてみましょう。

【問題】

629,259の最大公約数を求めよ。

 

まずは、\(629\div 259\) を筆算で計算します。

次に、余りを割る数の左に持ってきて、\(259\div 111\) を計算します。

これを繰り返し、余りが0になるまで計算します。

余りが0になったとき、一番左にある数(割る数)が最大公約数となります。

 

以上が筆算を使ったやり方です。

結局やっている計算は同じことなのですが、

割り算をするときに暗算が難しく、筆算を利用する必要があるのであれば、

今回紹介したように、筆算を並べていくやり方でやっていくと式を書き並べる手間が省けて、ちょっとだけ時短になりますね。

互除法の練習!

【問題】

次の2つの整数の最大公約数を,互除法を用いて求めよ。

(1)323,884

(2)304,1463

(3)943,1058

解答・解説はこちら

答え

(1)\(17\)

(2)\(19\)

(3)\(23\)

(1)

$$\begin{eqnarray}884&=&323\cdot 2+238\\[5pt]323&=&238\cdot 1+85\\[5pt]238&=&85\cdot 2+68\\[5pt]85&=&68\cdot 1+17\\[5pt]68&=&17\cdot 4+0 \end{eqnarray}$$

(2)

$$\begin{eqnarray}1463&=&304\cdot 4+247\\[5pt]304&=&247\cdot 1+57\\[5pt]247&=&57\cdot 4+19\\[5pt]57&=&19\cdot 3+0\end{eqnarray}$$

(3)

$$\begin{eqnarray}1058&=&943\cdot 1+115\\[5pt]943&=&115\cdot 8+23\\[5pt]115&=&23\cdot 5+0\end{eqnarray}$$

 

まとめ!

これでユークリッドの互除法のやり方はバッチリかな??

次に学習する「一次不定方式」の内容で、

互除法が、すっごく役に立つことになります。

なので、今のうちにしっかりと使えるように練習しておきましょう!

 

 

【中3受験生へ】この力を身につけたら本番で60点は楽勝にとれる!


頑張っているのに思うように成績が上がらず、
「このままだと本番で数学60点が厳しいかも…」
と不安に感じているあなた。

もしかして、
このような問題に直面していませんか?
  • 模試になると点がガクッと落ちる
  • 復習のやり方が分からない
  • 勉強してもすぐに忘れる
  • 凡ミスが直らない
  • 家だと集中して勉強できない
  • 問題集を買っても、1人で解けなくて途中でやめてしまう
  • 友人が点を伸ばしていて焦る
  • 頑張りたいから何をすればいいか教えて欲しい

僕が2年前に指導させてもらった中3のAくん
彼がまさにこのような状態でした。
 
すごく勉強したのに試験の結果が36点…
 
「どうすればいいか分からない…」
「点を上げれる自信がない…」
 
自信をなくし落ち込んでいましたが、
ある勉強方法を取り入れたことによって
Aくんは大変身!
 
なんと、たった2ヶ月で
36点 ⇒ 72点
なんと、驚きの36点UPを達成!

 
何をやっても点が伸びなかったAくん
彼を大変身させた「ある勉強方法」とは、
たったの5分で取り組める簡単なものです。
 
この勉強法を活用した人は、

 

43点 ⇒ 69点



67点 ⇒ 94点



人生初の100点!



 
このように次々と良い結果を報告してくれています^^
 
Aくんを大変身させた「ある勉強法」を
あなたにも活用してもらい
今すぐにでも結果を出して欲しいです。
 
そこで!
ある勉強法が正しく身につくように、
3つのワークを用意しました。
 
こちらのメルマガ講座の中で、
順にお渡ししていくので1つずつ取り組み、
やればやっただけ点が伸びていく感覚を掴んでくださいね!
 
もちろんメルマガ講座の登録は無料!
いますぐワークを受け取っておきましょう('◇')ゞ

     
 




コメントを残す

メールアドレスが公開されることはありません。