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

ユークリッドの互除法

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

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

目次

ユークリッドの互除法

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

STEP
aをbで割り、余りをrとする。

もしr=0であれば約分可能である。

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

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{1029}{1071}$$は約分可能か?

$$\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級の過去問を解いてみよう

問題

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

解答

ユークリッドの互除法で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{127}{163}$$

まとめ

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

STEP
aをbで割り、余りをrとする。

もしr=0であれば約分可能である。

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

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

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

数検1級対策

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

整数問題対策

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

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!
目次
閉じる