2-2-1 ユークリッドの互除法(要点)

ユークリッドの互除法

【ユークリッドの互除法】

自然数\(a\)を自然数\(b\)で割ったときの商を\(q\)、余りを\(r\)とする。
\(a=bq+r\)
このとき、
・\(a,b\)の最大公約数
・\(b,r\)の最大公約数
は一致する。

解法の手順は、
(1)\(a\)を\(b\)で割った余り\(r\)を求める。
(2)このときの割った数\(b\)を余り\(r\)で割る。
(3)これを繰り返して、割り切れるまで割る。
(4)割り切れたときの割った数が最大公約数になる。


【例題】次の最大公約数を求めなさい。

(1)\(260,117\)

(2)\(391,299\)

(3)\(1914,858\)

互除法の活用

【例題】次の等式を満たす整数\(x,y\)の組を\(1\)つ求めなさい。

(1)\(23x+17y=1\)

(2)\(51x+19y=3\)

メニュー
1章 場合の数と確率

1-1 場合の数

1-2 確率

2章 整数の性質

2-1 整数の性質

2-2 ユークリッド互除法

2-3 整数の性質の活用

3章 図形の性質

3-1 三角形の性質

3-2 円の性質

3-3 作図

3-4 空間図形

1章 場合の数と確率

1-1 場合の数

1-2 確率

2章 整数の性質

2-1 整数の性質

2-2 ユークリッド互除法

2-3 整数の性質の活用

3章 図形の性質

3-1 三角形の性質

3-2 円の性質

3-3 作図

3-4 空間図形

当サイトに一言
このサイトは個人で作成しており、閲覧者からのコメントを元にサイトの改善、精度を上げていきたいと考えています。
質問・問題のミス・改善要望、問い合わせがあればご連絡ください。

名前[必須]

メールアドレス[必須](メールアドレスが公開されることはありません。)

コメント