『ユークリッドの互除法』の電卓

この電卓は3万3984回使われています
の最大公約数

スポンサーリンク

このページを友達に教える

電卓の使い方

ユークリッドの互除法で求めたい最大公約数の数値を電卓に入力し「計算」ボタンを押してください。

3つ以上の数の最大公約数を求めたい場合は「入力追加」ボタンを押すと電卓の入力欄が追加されます。

計算をやり直す場合は「クリア」ボタンを押すと入力された数値が削除されます。

目次

スポンサーリンク

ユークリッドの互除法の解説

2つの数の最大公約数を求める場合、「2で割れる?」「3で割れる?」という具合に小さな数で割っていって両方が同じ数で割れる最大の数を探していくと思います。

しかし、この方法は最大公約数を求める2つの数が小さいときにはすぐに求めることができますが、3桁を超えるような大きな数字になってくると最大公約数を求めるのに時間がかかりやすい、さらに間違ってしまう可能性も高くなります。

そこで、このページでは大きな数同士でも簡単に最大公約数を求めることができる「ユークリッドの互除法(ごじょほう)」という手法を解説していきます。

名前からして難しいようなイメージを持つかもしれませんが、計算自体は小学生でもできる計算です。覚えておくとなにかと便利なので是非覚えておきましょう。

ユークリッドの互除法で最大公約数を求める

ユークリッドの互除法で最大公約数を求める手順としては、まず2つの数のうち、大きい数を小さい数で割って余りを求めます。

845と299の最大公約数は?

845 ÷ 299 = 2 ... 247

次に割ったほうの数を余りの数で割ってまた余りを求めます。

845と299の最大公約数は?

845 ÷ 299 = 2 ... 247

299 ÷ 247 = 1 ... 52

上記の計算を余りが0になるまで繰り返します。余りが0になった時に最後に割った数が最大公約数になります。

845と299の最大公約数は?

845 ÷ 299 = 2 ... 247

299 ÷ 247 = 1 ... 52

247 ÷ 52 = 4 ... 39

52 ÷ 39 = 1 ... 13

39 ÷ 13 = 3 ... 0

845と299の最大公約数は13

これがユークリッドの互除法で最大公約数を求める手順になります。手順は非常にシンプルですね。この手法であれば大きな数の最大公約数でも簡単に求めることができます。

3つ以上の数の最大公約数を求める

前章で2つの数の最大公約数をユークリッドの互除法で求める方法を解説しましたが、3つ以上の数の最大公約数を求めたい場合にはどうしたらいいのでしょうか?

3つの数の最大公約数を求める場合には、まず2つの数の最大公約数を求めて、その最大公約数と残りの数との最大公約数を求めれば3つの数の最大公約数を求めることができます。

例えば、A・B・Cの最大公約数を求める場合、まずAとBの最大公約数を求めて(仮にDとします)、DとCの最大公約数を求めればA・B・Cの最大公約数が求められます。

1820と1080と570の最大公約数は?

▼1820と1080の最大公約数
1820 ÷ 1080 = 1 ... 740
1080 ÷ 740 = 1 ... 340
740 ÷ 340 = 2 ... 60
340 ÷ 60 = 5 ... 40
60 ÷ 40 = 1 ... 20
40 ÷ 20 = 2 ... 0

▼570と20の最大公約数
570 ÷ 20 = 28 ... 10
20 ÷ 10 = 2 ... 0

1820と1080と570の最大公約数は10

スポンサーリンク

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

ユークリッドの互除法を用いて1288と736の最大公約数を求めなさい。
1288 ÷ 736 = 1 ... 552
736 ÷ 552 = 1 ... 184
552 ÷ 184 = 3 ... 0
ユークリッドの互除法を用いて3825と2790の最大公約数を求めなさい。
3825 ÷ 2790 = 1 ... 1035
2790 ÷ 1035 = 2 ... 720
1035 ÷ 720 = 1 ... 315
720 ÷ 315 = 2 ... 90
315 ÷ 90 = 3 ... 45
90 ÷ 45 = 2 ... 0
ユークリッドの互除法を用いて1140と810と735の最大公約数を求めなさい。

▼1140と810の最大公約数
1140 ÷ 810 = 1 ... 330
810 ÷ 330 = 2 ... 150
330 ÷ 150 = 2 ... 30
150 ÷ 30 = 5 ... 0

▼735と30の最大公約数
735 ÷ 30 = 24 ... 15
30 ÷ 15 = 2 ... 0

関連ページ

よく見られているページ