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

POINT

絵を書くことで，最大公約数の求め方（ユークリッドの互除法）を簡単に理解できます．

【メモ】

絵で見る最大公約数

2つの整数$a,b$の最大公約数とは「$a,b$を割り切る最大の整数」のことです．

「割り切る」という概念は，図形で考えると「敷き詰められる」と言い換えられます．例えば，$6\div 2=3$は「長さ6mの棒は，長さ2mの棒3つで敷き詰められる」と言えるわけです．

この考え方を使えば，最大公約数は次で言い換えられます：

最大公約数

【整数$a,b$の最大公約数】
＝【「2辺の長さが$a,b$である長方形」を敷き詰められる最大の正方形の辺の長さ】

上の性質を満たす正方形はどんな$a,b$に対しても存在します．なぜなら，辺の長さが1の正方形を使えば必ず長方形を敷き詰めることができるからです（つまり，どんな2つの整数も$1$を公約数にもつ）．

こうして「最大公約数」を絵で表すと，その求め方を簡単に理解できます．この方法は「ユークリッドの互除法」と呼ばれます．

以下では「2辺の長さが$a,b$である長方形」を敷き詰められる最大の正方形を$\mathrm{S}$，その辺の長さ（$=a,b$の最大公約数）を$s$と呼ぶことにしましょう．

それでは，具体的に$a=58$, $b=26$の場合を考えてみます．最大公約数$s=2$がどのように導かれるのか見てみましょう．

STEP

「長方形の短い方の辺」を一辺とする正方形を敷き詰める

正方形$\mathrm{S}$は$b=26$の長さを敷き詰められるので，「長方形の短い方の辺$b=26$で作られた正方形」も敷き詰めることができなくてはなりません．

この正方形を除いてできた長方形に着目しましょう（下図オレンジの部分）．

もとの長方形が正方形$\mathrm{S}$で敷き詰められるためには，オレンジの長方形も正方形$\mathrm{S}$で敷き詰められる必要があります．したがって，

「もとの長方形を敷き詰める最大の正方形$\mathrm{S}$」は「オレンジの長方形を敷き詰める最大の正方形」である

ことがわかります．

STEP

現れた長方形で同じことをする

というわけで，辺の長さが変わっただけで，また同じ問題になりました．
長方形の短い方の辺で作った正方形を取り除くと，同じ手順を繰り返すことができます．

STEP

正方形で敷き詰められるようになるまで繰り返す

これを何度か繰り返せば「考えている長方形」が「"長方形の短い方の辺"で作られた正方形」でピッタリ敷き詰められるようになります（上で触れたように，長さ1の正方形では必ず敷き詰められるので，絶対に敷き詰められるものが見つかります）．これが，求めたかった正方形$\mathrm{S}$です．

今回の例では3回目で$2\times 2$の正方形で敷き詰められることがわかります．この正方形の辺の長さ$s=2$が$a=58$, $b=26$の最大公約数です．

ユークリッドの互除法と今回の説明の対応について解説します．

ユークリッドの互除法については以下で簡単にまとめているので，説明は（いまのところ）省略します．

上で解説したように，同じことの繰り返しなので【Step.1】についてだけ解説します．
大きい方の整数$a$を$b$で割ったときの「商を$\textcolor{red}{q}$」「余りを$\textcolor{blue}{r}$」とすると

\begin{aligned}
a=b\textcolor{red}{q}+\textcolor{blue}{r}\quad (0 \leq \textcolor{blue}{r} < b )
\end{aligned}

と書けます．このとき，

となります．上の例では

\begin{aligned}
58=26\times \textcolor{red}{2}+\textcolor{blue}{6} \quad (0 \leq \textcolor{red}{2} < \textcolor{blue}{6} )
\end{aligned}

というわけです：

【おまけ（図の作り方）】
今回は（見た目を考えて）「最初に2個・次に4個・最後に3個の正方形」を作るように逆算しました．つまり，$a,b$を辺の長さとするとき

\begin{aligned}
a=&\underline{b}\times \textcolor{red}{2} + c \\
&b=c\times \textcolor{blue}{4}+c/\textcolor{green}{3}
\end{aligned}

において，$c=6$とすると$(a,b)=(58,26)$．