ニ☆ウ☆ト☆ラ☆ボ

タイトルテスト中

ユークリッドの互除法

\[ 8983 \quad \text{と} \quad 4043 \]

の最大公約数を求めてみます. \( a \) を \( b \) で割って, 商が \( q \), 余りが \( r \) ならば,

\[ a \div b = q \, \cdots \, r \]

と書きます.

\begin{align} 8983 \div 4043 &= 2 \, \cdots \, 897 \\[0.5em] 4043 \div 897 &= 4 \, \cdots \, 455 \\[0.5em] 897 \div 455 &= 1 \, \cdots \, 442 \\[0.5em] 455 \div 442 &= 1 \, \cdots \, 13 \\[0.5em] 442 \div 13 &= 34 \, \cdots \, 0 \end{align}

\( 0 \) になる前の余り \( 13 \) が最大公約数です. 「ユークリッドの互除法」と呼ばれており, どんな \( 2 \) つの数に対しても最大公約数が求まります.

広告を非表示にする