絵で見る最大公約数(ユークリッドの互除法)

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

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.1】
正方形$\mathrm{S}$は$b=26$の長さを敷き詰められるので,「長方形の短い方の辺$b=26$で作られた正方形」も敷き詰めることができなくてはなりません.

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

ユークリッドの互除法
Step.1:正方形$\mathrm{S}$が敷き詰められる$26\times 26$の正方形を除く.
もとの長方形が正方形$\mathrm{S}$で敷き詰められるためには,オレンジの長方形も正方形$\mathrm{S}$で敷き詰められる必要があります.したがって,
「もとの長方形を敷き詰める最大の正方形$\mathrm{S}$」は「オレンジの長方形を敷き詰める最大の正方形」である
ことがわかります.


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

Step.2:正方形$\mathrm{S}$が敷き詰められる$6\times 6$の正方形を除く.


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

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

ユークリッドの互除法
Step.3:正方形$\mathrm{S}$は$2\times 2$であることがわかった.正方形$\mathrm{S}$の辺の長さ$s=2$が$a=58$, $b=26$の最大公約数となる.


背景(式との対応)

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

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


上で解説したように,同じことの繰り返しなので【Step.1】についてだけ解説します.
大きい方の整数$a$を$b$で割ったときの「商を$\color{red}{q}$」「余りを$\color{blue}{r}$」とすると
\begin{align}
a=b\color{red}{q}+\color{blue}{r}\quad (0 \leq \color{blue}{r} < b )
\end{align}と書くことができます.このとき,

  • 商$\color{red}{q}$:取り除いた正方形の数
  • 余り$\color{blue}{r}$:残った長方形(オレンジ)の短い方の辺の長さ

となります.上の例では
\begin{align}
58=26\times \color{red}{2}+\color{blue}{6} \quad (0 \leq \color{red}{2} < \color{blue}{6} )
\end{align}というわけです:

ユークリッドの互除法
Step.1:正方形$\mathrm{S}$が敷き詰められる$26\times 26$の正方形を除く.


【おまけ(図の作り方)】
今回は(見た目を考えて)「最初に2個・次に4個・最後に3個の正方形」を作るように逆算しました.つまり,$a,b$を辺の長さとするとき
\begin{align}
a=&\underline{b}\times \color{red}{2} + c \\
&b=c\times \color{blue}{4}+c/\color{green}{3}
\end{align}において,$c=6$とすると$(a,b)=(58,26)$.