数学・算数検定

ユークリッドの互除法と使い方

ユークリッドの互除法

今回はユークリッドの互除法の使用方法を数検1級の試験で出題された問題を用いて実際に使用してみましょう。

ペンちゃん
ペンちゃん
ユークリッドの互除法の使い方についてお勉強しよう!

ユークリッドの互除法

まずはユークリッドの互除法を約分が可能かについて考えることで確認してみましょう。

$$\frac{a}{b}$$が約分可能か考えよう。

1.aをbで割り、余りをrとする。
もしr=0であれば約分可能である。

2.r > 0のとき、aにbの値を、bにrを入れて1を再度行う。

r=0になったとき、bの値が、元の数a,bの最大公約数になる。

これがユークリッドの互除法です。
もし最大公約数が1のとき、既約分数となるので、元の分数は約分できなかったということになります。

ユークリッドの互除法の使用例

$$\frac{1029}{1071}$$は約分可能か?

ユークリッドの互除法でa=1029,b=1071とする。
1071÷1029=1 余り 42
1029÷42=24 余り 21
42÷21=2 余り 0
なので最大公約数は21である。
よって$$\frac{1029}{1071}=\frac{21・49}{21・51}=\frac{49}{51}$$となる。

別解

ユークリッドの互除法を用いないで次のようにしても求められます。

$$\frac{a}{b}$$
が約分可能と
$$1-\frac{a}{b}$$
が約分可能は同値なので
$$1-\frac{1029}{1071}=\frac{42}{1071}$$
$$=\frac{2・21}{1071}=\frac{2・21}{21・51}=\frac{2}{51}$$
なので
$$\frac{1029}{1071}=1-\frac{2}{51}=\frac{49}{51}$$

数検1級の過去問を解いてみよう

問題

数検1級1次 第184回 問1

次の分数は約分できますか。できるならば、約分してもっとも簡単な分数で表し、できないならば「約分できない」と答えなさい
$$\frac{10033}{12877}$$

解答

ユークリッドの互除法でa=10033,b=12877する。
12877÷10033=1 余り 2844
10033÷2844=3 余り 1501
2844÷1501=1 余り 1343
1501÷1343=1 余り 158
1343÷158=8 余り 79
158÷79=2 余り 0
なので最大公約数は79である。
よって$$\frac{10033}{12877}=\frac{79・127}{79・163}=\frac{127}{163}$$となる。

答え $$\frac{127}{163}$$

解答2

ユークリッドの互除法を使用しない解答もみてみましょう。

$$1-\frac{10033}{12877}=\frac{2844}{12877}$$
$$=\frac{2^{2}・3^{2}・79}{12877}=\frac{2^{2}・3^{2}・79}{79・163}=\frac{36}{163}$$
なので
$$\frac{10033}{11877}=1-\frac{36}{163}=\frac{127}{163}$$

まとめ

ユークリッドの互除法で最大公約数や、約分可能かわかります。
ぜひ覚えておきましょう。

ユークリッドの互除法

$$\frac{a}{b}$$が約分可能か考えよう。

1.aをbで割り、余りをrとする。
もしr=0であれば約分可能である。

2.r > 0のとき、aにbの値を、bにrを入れて1を再度行う。

r=0になったとき、bの値が、元の数a,bの最大公約数になる。

ペンちゃん
ペンちゃん
ユークリッドの互除法を使って約分できるか知る方法についてお勉強したよ!

数検1級対策

数検1級の対策についてはこちらをご覧ください。

数検1級の勉強法
数検1級の試験範囲と勉強法今回は数検準1級の試験範囲と勉強法についてです。数検準1級の合格のためのおすすめ参考書6選もあげています。 数検について 数...

整数問題対策

また、整数問題の対策はこちらの記事をご覧ください。

整数問題攻略におすすめの参考書問題集
整数問題攻略におすすめの参考書・問題集6選整数問題とは、高校数学Aで扱われる分野である。整数自体は小学生でも知っているものであるが、この分野は難しい問題が出題されやすい。ここで点...