ユークリッドの互除法で【最大公約数】を求めよう

\begin{align*}
& a>b\ である\ 2\ つの正の整数\ a,\ b\ について,\\
& \colorbox{mistyrose}{$a$}\ を\ \colorbox{bisque}{$b$}\ で割った商を\ \colorbox{palegreen}{$q$},\ 余りを\ \colorbox{violet}{$r$}\ とすると,\\
& \qquad\Longrightarrow\fcolorbox{red}{white}{$\colorbox{mistyrose}{$a$}=\colorbox{bisque}{$b$}\times\colorbox{palegreen}{$q$}+\colorbox{violet}{$r$}$}\ と表せる。\\
& \scriptsize\color{red}余り\ r\ は割った数\ b\ より小さいから\ 0 \leqq r < b\ が成り立つ。
\\\\
\\
& 例えば,\\
& \colorbox{mistyrose}{$17$}\ を\ \colorbox{bisque}{$3$}\ で割った商が\ \colorbox{palegreen}{$5$},\ 余りが\ \colorbox{violet}{$2$}\ だから,\\
& \qquad\Longrightarrow\fcolorbox{red}{white}{$\colorbox{mistyrose}{$17$}=\colorbox{bisque}{$3$}\times\colorbox{palegreen}{$5$}+\colorbox{violet}{$2$}$}\ と表せる。\\
& \scriptsize\color{red}余り\ 2\ は割った数\ 3\ より小さいから\ 0 \leqq r < 3\ が成り立っている。\\
\\
\\
& \colorbox{mistyrose}{$23$}\ を\ \colorbox{bisque}{$5$}\ で割った商が\ \colorbox{palegreen}{$4$},\ 余りが\ \colorbox{violet}{$3$}\ だから,\\
& \qquad\Longrightarrow\fcolorbox{red}{white}{$\colorbox{mistyrose}{$23$}=\colorbox{bisque}{$5$}\times\colorbox{palegreen}{$4$}+\colorbox{violet}{$3$}$}\ と表せる。\\
& \scriptsize\color{red}余り\ 3\ は割った数\ 5\ より小さいから\ 0 \leqq r < 5\ が成り立っている。\\
\end{align*}

\begin{align*}
& \colorbox{bisque}{$n$}\ が\ \colorbox{palegreen}{$a$}\ の約数\\
& \scriptsize\color{red}\Rightarrow\ a\ は\ n\ で割り切れる！このとき商が\ a',\ 余り\ 0\ とすれば\\
& \scriptsize\color{red}\Rightarrow\ a=n \times a' + 0\\
& \Longleftrightarrow\ \colorbox{palegreen}{$a$} = \colorbox{bisque}{$n$}\cdot\colorbox{mistyrose}{$a'$}\ となる\ \colorbox{mistyrose}{$a'$}\ が存在する。\\
\\
\\
& 例えば,\\
& \colorbox{bisque}{$4$}\ は\ \colorbox{palegreen}{$12$}\ の約数だから\\
& \scriptsize\color{red}\Rightarrow\ 12\ は\ 4\ で割り切れる！このとき商が\ 3,\ 余り\ 0\ だから\\
& \scriptsize\color{red}\Rightarrow\ 12=4 \times 3 + 0\\
& \qquad\colorbox{palegreen}{$12$} = \colorbox{bisque}{$4$} \cdot \colorbox{mistyrose}{$3$}\ と表せる。\\
\\
& \colorbox{bisque}{$3$}\ は\ \colorbox{palegreen}{$27$}\ の約数だから\\
& \scriptsize\color{red}\Rightarrow\ 27\ は\ 3\ で割り切れる！このとき商が\ 9,\ 余り\ 0\ だから\\
& \scriptsize\color{red}\Rightarrow\ 27=3 \times 9 + 0\\
& \qquad\colorbox{palegreen}{$27$} = \colorbox{bisque}{$3$} \cdot \colorbox{mistyrose}{$9$}\ と表せる。\\
\\

\end{align*}

\begin{align*}
& \colorbox{mistyrose}{$a$} = \colorbox{bisque}{$m$} \times \colorbox{palegreen}{$n$}\ と表せたら\\
& \scriptsize\color{red}\quad\ a\ は\ m\ で割り切れるから\ a = m \times n + 0\\
& \qquad \colorbox{bisque}{$m$}\ は\ \colorbox{mistyrose}{$a$}\ の約数\\
& \scriptsize\color{red}\quad\ a\ は\ n\ で割り切れるから\ a = n \times m + 0\\
& \qquad \colorbox{palegreen}{$n$}\ は\ \colorbox{mistyrose}{$a$}\ の約数\\
\\
\\
& 例えば,\\
& \colorbox{mistyrose}{$18$} = \colorbox{bisque}{$3$} \times \colorbox{palegreen}{$6$}\ と表せるから\\
& \qquad \colorbox{bisque}{$3$}\ は\ \colorbox{mistyrose}{$18$}\ の約数\\
& \qquad \colorbox{palegreen}{$6$}\ は\ \colorbox{mistyrose}{$18$}\ の約数\\
\\
& \colorbox{mistyrose}{$14$} = \colorbox{bisque}{$1$} \times \colorbox{palegreen}{$14$}\ と表せるから\\
& \qquad \colorbox{bisque}{$1$}\ は\ \colorbox{mistyrose}{$1$}\ の約数\\
& \qquad \colorbox{palegreen}{$14$}\ は\ \colorbox{mistyrose}{$14$}\ の約数\\

\end{align*}

\begin{align*}
& \colorbox{mistyrose}{$a$}\ を\ \colorbox{bisque}{$b$}\ で割った商を\ q\ ,\ 余りを\ \colorbox{palegreen}{$r$}\ とすると\\
& \qquad\colorbox{mistyrose}{$a$} = \colorbox{bisque}{$b$} \times q + \colorbox{palegreen}{$r$}
（0 \leqq r < b）\cdots①\\
& と表すことができる。\scriptsize\color{blue}・・・・・・・・・・・・・【確認①】\\
\\
& さらに①を変形して\\
& \qquad \colorbox{palegreen}{$r$} = \colorbox{bisque}{$b$} \times q - \colorbox{mistyrose}{$a$}\cdots②\\
\\
&\colorbox{violet}{$m$}\ を\ \colorbox{mistyrose}{$a$}\ と\ \colorbox{bisque}{$b$}\ の最大公約数,\\
&\colorbox{lightcyan}{$n$}\ を\ \colorbox{bisque}{$b$}\ と\ \colorbox{palegreen}{$r$}\ の最大公約数とする。\\
& \qquad\qquad\qquad\qquad\qquad\qquad\scriptsize\color{red}\Rightarrow m=n\ を示したい！\\
\\
& \fcolorbox{red}{white}{$r \neq 0$\ のとき}\\
& \quad\begin{align*}
(i)\quad & \colorbox{violet}{$m$}\ は\ \colorbox{mistyrose}{$a$}\ と\ \colorbox{bisque}{$b$}\ の最大公約数だから,\\
& \qquad a = m \cdot a',\ b = m \cdot b'\\
& となる自然数\ a',\ b'\ が存在する。\scriptsize\color{blue}・・【確認②】\\
& これらを②に代入して\\
& \qquad \colorbox{palegreen}{$r$} = m \cdot b' \times q - m \cdot a' = \colorbox{violet}{$m$}(b'q-a')\\
& よって,\\
& \qquad\colorbox{violet}{$m$}\ は\ \colorbox{palegreen}{$r$}\ の約数である。\\
& したがって,\scriptsize\color{red}\ m\ は\ b\ の約数でもあるから\\
& \qquad \colorbox{violet}{$m$}\ は\ \colorbox{bisque}{$b$},\ \colorbox{palegreen}{$r$}\ の公約数である。\\
& ここで,\ \colorbox{lightcyan}{$n$}\ は\ \colorbox{bisque}{$b$}\ と\ \colorbox{palegreen}{$r$}\ の\fcolorbox{red}{white}{\bf 最大}公約数だから\\
& \qquad \colorbox{violet}{$m$} \leqq \colorbox{lightcyan}{$n$} \qquad\cdots ③\\
\\
(ii)\quad & \colorbox{lightcyan}{$n$}\ は\ \colorbox{bisque}{$b$}\ と\ \colorbox{palegreen}{$r$}\ の最大公約数だから,\\
& \qquad b = n \cdot b'',\ r = n \cdot r''\\
& となる自然数\ b'',\ r''\ が存在する。\scriptsize\color{blue}・・【確認②】\\
& これらを①に代入して\\
& \qquad \colorbox{mistyrose}{$a$} = n \cdot b'' \times q + n \cdot r'' = \colorbox{lightcyan}{$n$}(b''q+r'')\\
& よって,\\
& \qquad\colorbox{lightcyan}{$n$}\ は\ \colorbox{mistyrose}{$a$}\ の約数である。\\
& したがって,\scriptsize\color{red}\ n\ は\ b\ の約数でもあるから\\
& \qquad \colorbox{lightcyan}{$n$}\ は\ \colorbox{mistyrose}{$a$},\ \colorbox{bisque}{$b$}\ の公約数である。\\
& ここで,\ \colorbox{violet}{$m$}\ は\ \colorbox{mistyrose}{$a$}\ と\ \colorbox{bisque}{$b$}\ の\fcolorbox{red}{white}{\bf 最大}公約数だから\\
& \qquad \colorbox{violet}{$m$} \geqq \colorbox{lightcyan}{$n$} \qquad\cdots ④
\end{align*}\\
& ③,\ ④\ より,\\
& \qquad \colorbox{violet}{$m$} = \colorbox{lightcyan}{$n$}\quad\scriptsize\color{red}\cdots{\bf 目的達成！}\\
\\
\\
& \scriptsize\color{red}ちなみに\\
& \fcolorbox{red}{white}{$r = 0$\ のとき},\ \scriptsize\color{red}余りが\ 0\ =\ 割り切れる！\\
& \qquad\colorbox{mistyrose}{$a$} = \colorbox{bisque}{$b$} \times q\\
& となるから, \colorbox{mistyrose}{$a$}\ と\ \colorbox{bisque}{$b$}\ の\fcolorbox{red}{white}{\bf 最大}公約数は\\
& \qquad\colorbox{bisque}{$b$}\\
& である。\\
& \qquad
& 

\end{align*}

\begin{align*}
& \underline{288\ と\ 126\ の最大公約数\ \colorbox{violet}{$m$}\ を求めよう！}\\
\\
& \scriptsize\color{red}大きい数を小さい数で割る\\
& ①\ \colorbox{mistyrose}{$288$} \div \colorbox{bisque}{$126$}\ を計算すると,\\
& \qquad 商が\ 2\ ,\ 余りが\ \colorbox{palegreen}{$36$}\ になります。\\
& \qquad \Rightarrow{\bf 互除法の原理}により\\
& \qquad\qquad \colorbox{violet}{$m$}\ は,\ \colorbox{bisque}{126}\ と\ \colorbox{palegreen}{$36$}\ の最大公約数！\\
\\
& \scriptsize\color{red}126\ と\ 36\ の最大公約数\ m\ を求めよう\\
& ②\ \colorbox{mistyrose}{$126$} \div \colorbox{bisque}{$36$}\ を計算すると,\\
& \qquad 商が\ 3\ ,\ 余りが\ \colorbox{palegreen}{$18$}\ になります。\\
& \qquad \Rightarrow{\bf 互除法の原理}により\\
& \qquad\qquad \colorbox{violet}{$m$}\ は,\ \colorbox{bisque}{36}\ と\ \colorbox{palegreen}{$18$}\ の最大公約数！\\
\\
& \scriptsize\color{red}36\ と\ 18\ の最大公約数\ m\ を求めよう\\
& ③\ \colorbox{mistyrose}{$36$} \div \colorbox{bisque}{$18$}\ を計算すると,\\
& \qquad 商が\ 2\ ,\ \fcolorbox{red}{white}{\bf 余りが０}\ になりました！\\
& \qquad\qquad\qquad\scriptsize\begin{array}{c}\\
\colorbox{violet}{$18$}）& 36 && 18\\\hline
& 2 && 1\\
\\
\end{array}\\
& \qquadよって,\\
& \qquad\qquad\colorbox{mistyrose}{$36$}\ と\ \colorbox{bisque}{$18$}\ の最大公約数は\ \colorbox{violet}{$18$}\\
\\
& したがって,\\
& \qquad\colorbox{violet}{$m = 18$}
\\

\end{align*}

\begin{align*}
& 筆算でも可能ですが・・・\\
& \qquad\begin{array}{c}\\
2 & ） & 288 && 126\\\hline
3 & ） & 144 && 63\\\hline
3 & ） & 48 && 21\\\hline
& & 16 && 7
\end{array}\\
& よって,\ 最大公約数は\\
& \qquad 2 \times 3 \times 3 = \colorbox{violet}{$18$}\\
\\
& 大きい数になると難しくなります。\\
& そんなときこそ\\
& \bf\color{red}\Rightarrow\ ユークリッドの互除法をどうぞ。
\end{align*}

\begin{align*}
& \scriptsize\color{red}\fbox{\bf 解説なし}\\
& \begin{align*}
288 &=& 126 & \times 2 & + 36\\
126 &=& 36 & \times 3 & + 18\\
36 &=& \colorbox{violet}{$18$} & \times 2 & \color{lightgray}+ 0\\
\end{align*}\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$18$}\ である。\\
\\
\\
& \scriptsize\color{red}\fbox{\bf 解説付き}\\
& \scriptsize\color{red}[1]\ \colorbox{mistyrose}{大きい数}を\colorbox{bisque}{小さい数}で割ると\\
& \scriptsize\color{red}\Rightarrow 288 \div 126\ は,\ 商が\ 2,\quad 余り\ 36\ であるから\\
& \colorbox{mistyrose}{$288$} = \colorbox{bisque}{$126$} \times 2 + \colorbox{palegreen}{$36$}\\
\\
& \scriptsize\color{red}[2]\ \colorbox{bisque}{小さい数}を\colorbox{palegreen}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 126 \div 36\ は,\ 商が\ 3,\quad 余り\ 18\ であるから\\
& \colorbox{bisque}{$126$} = \colorbox{palegreen}{$36$} \times 3 + \colorbox{violet}{$18$}\\
\\
& \scriptsize\color{red}[3]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 36 \div 18\ は,\ 商が\ 2,\quad 余り\ 0\ になった！\\
& \colorbox{palegreen}{$36$} = \colorbox{violet}{$18$} \times 2 \color{lightgray}+ 0\\
\\
& \scriptsize\color{red}\bf 最後に\colorbox{violet}{\color{white}割った数}が答えだから\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$18$}\ である。\end{align*}

\begin{align*}
& \scriptsize\color{red}\fbox{\bf 解説なし}\\
& \begin{align*}
374 &=& 255 & \times 1 & + 119\\
255 &=& 119 & \times 2 & + 17\\
119 &=& \colorbox{violet}{$17$} & \times 7 & \color{lightgray}+ 0\\
\end{align*}\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$17$}\ である。\\
\\
\\
& \scriptsize\color{red}\fbox{\bf 解説付き}\\
& \scriptsize\color{red}[1]\ \colorbox{mistyrose}{大きい数}を\colorbox{bisque}{小さい数}で割ると\\
& \scriptsize\color{red}\Rightarrow 374 \div 255\ は,\ 商が\ 1,\quad 余り\ 119\ であるから\\
& \colorbox{mistyrose}{$374$} = \colorbox{bisque}{$255$} \times 1 + \colorbox{palegreen}{$119$}\\
\\
& \scriptsize\color{red}[2]\ \colorbox{bisque}{小さい数}を\colorbox{palegreen}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 255 \div 119\ は,\ 商が\ 2,\quad 余り\ 17\ であるから\\
& \colorbox{bisque}{$255$} = \colorbox{palegreen}{$119$} \times 2 + \colorbox{violet}{$17$}\\
\\
& \scriptsize\color{red}[3]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 119 \div 17\ は,\ 商が\ 7,\quad 余り\ 0\ になった！\\
& \colorbox{palegreen}{$119$} = \colorbox{violet}{$17$} \times 7 \color{lightgray}+ 0\\
\\
& \scriptsize\color{red}\bf 最後に\colorbox{violet}{\color{white}割った数}が答えだから\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$17$}\ である。\end{align*}

\begin{align*}
& \scriptsize\color{red}\fbox{\bf 解説なし}\\
& \begin{align*}
874 &=& 323 & \times 2 & + 228\\
323 &=& 228 & \times 1 & + 95\\
228 &=& 95 & \times 2 & + 38\\
95 &=& 38 & \times 2 & + 19\\
38 &=& \colorbox{violet}{$19$} & \times 2 & \color{lightgray}+ 0\\
\end{align*}\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$19$}\ である。\\
\\
\\
& \scriptsize\color{red}\fbox{\bf 解説付き}\\
& \scriptsize\color{red}[1]\ \colorbox{mistyrose}{大きい数}を\colorbox{bisque}{小さい数}で割ると\\
& \scriptsize\color{red}\Rightarrow 874 \div 323\ は,\ 商が\ 2,\quad 余り\ 228\ であるから\\
& \colorbox{mistyrose}{$874$} = \colorbox{bisque}{$323$} \times 2 + \colorbox{palegreen}{$228$}\\
\\
& \scriptsize\color{red}[2]\ \colorbox{bisque}{小さい数}を\colorbox{palegreen}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 323 \div 228\ は,\ 商が\ 1,\quad 余り\ 95\ であるから\\
& \colorbox{bisque}{$323$} = \colorbox{palegreen}{$228$} \times 1 + \colorbox{violet}{$95$}\\
\\
& \scriptsize\color{red}[3]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 228 \div 95\ は,\ 商が\ 2,\quad 余り\ 38\ であるから\\
& \colorbox{palegreen}{$228$} = \colorbox{violet}{$95$} \times 2 + 38\\
\\
& \scriptsize\color{red}[4]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 95 \div 38\ は,\ 商が\ 2,\quad 余り\ 19\ になった！\\
& 228 = 95 \times 2 + 38\\
\\
& \scriptsize\color{red}[5]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 38 \div 19\ は,\ 商が\ 2,\quad 余り\ 0\ になった！\\
& \colorbox{palegreen}{$38$} = \colorbox{violet}{$19$} \times 2 \color{lightgray}+ 0\\
\\
& \scriptsize\color{red}\bf 最後に\colorbox{violet}{\color{white}割った数}が答えだから\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$19$}\ である。\end{align*}

\begin{align*}
& \scriptsize\color{red}\fbox{\bf 解説なし}\\
& \begin{align*}
3337 &=& 2627 & \times 1 & + 710\\
2627 &=& 710 & \times 3 & + 497\\
710 &=& 497 & \times 1 & + 213\\
497 &=& 213 & \times 2 & + 71\\
213 &=& \colorbox{violet}{$71$} & \times 3 & \color{lightgray}+ 0\\
\end{align*}\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$71$}\ である。\\
\\
\\
& \scriptsize\color{red}\fbox{\bf 解説付き}\\
& \scriptsize\color{red}[1]\ \colorbox{mistyrose}{大きい数}を\colorbox{bisque}{小さい数}で割ると\\
& \scriptsize\color{red}\Rightarrow 3337 \div 2627\ は,\ 商が\ 1,\quad 余り\ 710\ であるから\\
& \colorbox{mistyrose}{$3337$} = \colorbox{bisque}{$2627$} \times 1 + \colorbox{palegreen}{$710$}\\
\\
& \scriptsize\color{red}[2]\ \colorbox{bisque}{小さい数}を\colorbox{palegreen}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 2627 \div 710\ は,\ 商が\ 3,\quad 余り\ 497\ であるから\\
& \colorbox{bisque}{$2627$} = \colorbox{palegreen}{$710$} \times 3 + \colorbox{violet}{$497$}\\
\\
& \scriptsize\color{red}[3]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 710 \div 497\ は,\ 商が\ 1,\quad 余り\ 213\ であるから\\
& \colorbox{palegreen}{$710$} = \colorbox{violet}{$497$} \times 1 + 213\\
\\
& \scriptsize\color{red}[4]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 497 \div 213\ は,\ 商が\ 2,\quad 余り\ 71\ になった！\\
& 710 = 497 \times 1 + 213\\
\\
& \scriptsize\color{red}[5]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 213 \div 71\ は,\ 商が\ 3,\quad 余り\ 0\ になった！\\
& \colorbox{palegreen}{$213$} = \colorbox{violet}{$71$} \times 3 \color{lightgray}+ 0\\
\\
& \scriptsize\color{red}\bf 最後に\colorbox{violet}{\color{white}割った数}が答えだから\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$71$}\ である。\end{align*}

\begin{align*}
& \scriptsize\color{red}\fbox{\bf 解説なし}\\
& \begin{align*}
646 &=& 437 & \times 1 & + 209\\
437 &=& 209 & \times 2 & + 19\\
209 &=& \colorbox{violet}{$19$} & \times 11 & \color{lightgray}+ 0\\
\end{align*}\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$19$}\ である。\\
\\
\\
& \scriptsize\color{red}\fbox{\bf 解説付き}\\
& \scriptsize\color{red}[1]\ \colorbox{mistyrose}{大きい数}を\colorbox{bisque}{小さい数}で割ると\\
& \scriptsize\color{red}\Rightarrow 646 \div 437\ は,\ 商が\ 1,\quad 余り\ 209\ であるから\\
& \colorbox{mistyrose}{$646$} = \colorbox{bisque}{$437$} \times 1 + \colorbox{palegreen}{$209$}\\
\\
& \scriptsize\color{red}[2]\ \colorbox{bisque}{小さい数}を\colorbox{palegreen}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 437 \div 209\ は,\ 商が\ 2,\quad 余り\ 19\ であるから\\
& \colorbox{bisque}{$437$} = \colorbox{palegreen}{$209$} \times 2 + \colorbox{violet}{$19$}\\
\\
& \scriptsize\color{red}[3]\ 同じように\colorbox{palegreen}{割った数}を\colorbox{violet}{余り}で割ると\\
& \scriptsize\color{red}\Rightarrow 209 \div 19\ は,\ 商が\ 11,\quad 余り\ 0\ になった！\\
& \colorbox{palegreen}{$209$} = \colorbox{violet}{$19$} \times 11 \color{lightgray}+ 0\\
\\
& \scriptsize\color{red}\bf 最後に\colorbox{violet}{\color{white}割った数}が答えだから\\
& よって,\\
& \qquad 最大公約数は\ \colorbox{violet}{$19$}\ である。\end{align*}