ユークリッドの互除法で、最大公約数はばっちり！
始めに
中学受験の塾だと、4年生から5年生の間に最大公約数の求め方を習いますね。
例えば24と36の最大公約数を出したいときは、逆割り算（すだれ算・連除法とも言われます）で最初2つの数を4で割り、商の6と9をさらに3で割って終わりになり、最大公約数は3x4=12と出せる、といった具合です。そして、公約数がすぐに見つからない場合は、2つの数の差に注目して見つけるんでしたね。
では、296と777の最大公約数はすぐに見つけられるでしょうか？
……むずくね？無理じゃね？と思ったそこの君に、今回は「ユークリッドの互除法」を教えます！
ユークリッドの互除法
ユークリッドの互除法とは、紀元前3世紀ごろの古代エジプトで活躍した数学者・ユークリッドが見つけた最大公約数の求め方です。
具体的なやり方は以下の通りです。
最大公約数を求めたい2つの整数をそれぞれa, b (a > b) とするとき、
- a ÷ bのあまりを出す（このあまりをr1とする）
- b ÷ r1のあまりを出す（このあまりをr2とする
- r1 ÷ r2のあまりを出す（このあまりをr3とする）この手順を、あまりが0になるまでくりかえす。
- あまりが0になったときの割る数（一番最後にでたあまり）が最大公約数
文字で説明されても難しいと思うので、296と777の最大公約数をこの方法で出してみます。
- 777 ÷ 296 = 2 あまり 185
- 296 ÷ 185 = 1 あまり 111
- 185 ÷ 111 = 1 あまり 74
- 111 ÷ 74 = 1 あまり 37
- 74 ÷ 37 = 2 あまり 0
よって、最大公約数は37と求められます。
実際に296 = 37 x 8, 777 = 37 x 21となり、確かに最大公約数は37だとわかりますね（ちなみに111 = 37 x 3 なので、3ケタのゾロ目の数は37の倍数になります）
練習問題
最後にいくつか練習問題を用意しておくので、ぜひやってみてください！
(1) 182と377の最大公約数
(2) 342と779の最大公約数
(3) 319と841の最大公約数
(4) 527と1116の最大公約数
(5) 738と1681の最大公約数
是非ユークリッドの互除法も使いこなしてみましょう。今回も読んでくれてありがとうございました！（答えは下にあります）
答え (1) 13 (2) 19 (3) 29 (4) 31 (5) 41