- 数学A｜整数の性質「ユークリッドの互除法と最大公約数」の基本例題解説ページです。
- 目次をクリックすると各セクションへ移動します。
問題｜ユークリッドの互除法と最大公約数
整数の性質 29\(231\) と \(176\) の最大公約数をユークリッドの互除法で求める方法は？
高校数学A｜整数の性質
解法のPoint
ユークリッドの互除法と最大公約数
Point：ユークリッドの互除法と最大公約数
\(2\) つの自然数 \(a~,~b\) について、\(a\) を \(b\) で割った余りを \(r\) とすると、
\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい
① \(a\) を \(b\) で割った余り \(r\) を求める。
② \(b\) と \(r\) について、\(b\) を \(r\) で割った余り \(r^{\prime}\) を求める。
③ これを余りが \(0\) になるまでくり返して、最大公約数を求める。
■ ユークリッドの互除法
\(2\) つの自然数 \(a~,~b\) について、\(a\) を \(b\) で割った余りを \(r\) とすると、
\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい
ユークリッドの互除法を用いた最大公約数の求め方は、
① \(a\) を \(b\) で割った余り \(r\) を求める。
② \(b\) と \(r\) について、\(b\) を \(r\) で割った余り \(r^{\prime}\) を求める。
③ これを余りが \(0\) になるまでくり返して、最大公約数を求める。
©︎ 2026 教科書より詳しい高校数学 yorikuwa.com
詳しい解説｜ユークリッドの互除法と最大公約数
整数の性質 29\(231\) と \(176\) の最大公約数をユークリッドの互除法で求める方法は？
高校数学A｜整数の性質
\(231\) を \(176\) で割ると、
\(\begin{array}{rr}1~\\176~)~\overline{231~}\\\underline{176~}\\55~\end{array}\)
\(231=176 \cdot 1+55\)
よって、\(231\) と \(176\) の最大公約数は \(176\) と \(55\) の最大公約数に等しい
次に、\(176\) を \(55\) で割ると、
\(\begin{array}{rr}3~\\55~)~\overline{176~}\\\underline{165~}\\11~\end{array}\)
\(176=55 \cdot 3+11\)
よって、\(176\) と \(55\) の最大公約数は \(55\) と \(11\) の最大公約数に等しい
さらに、\(55\) を \(11\) で割ると、
\(\begin{array}{rr}5~\\11~)~\overline{55~}\\\underline{55~}\\0~\end{array}\)
余りが \(0\) となるので最大公約数は \(11\)
したがって、\(231\) と \(176\) の最大公約数は \(11\) となる
