本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
最大公約数と除算の余りの関係
整数$a,q$と自然数$b$に対して，
\gcd(a,b) &= \gcd(a-qb,b)\label{主題1}
\end{align}
が成り立つ。特に，$a$の$b$による除算の余りを$r$とすると，
\gcd(a,b) &= \gcd(b,r)\label{主題2}
\end{align}
が成り立つ。
ユークリッドの互除法に利用される重要な定理です。
証明
$\gcd(a,b)=d_{1}$，$\gcd(a-qb,b)=d_{2}$とおいて，$d_{1}=d_{2}$を導きます。ただし，単純に$d_{1}=d_{2}$を導くのではなく，$d_{1},d_{2}$が公約数のうち最大の整数であることを利用して，$d_{1}\leq d_{2}$かつ$d_{2}\leq d_{1}$を導きます。まず，最大公約数の定義より，
a &= a_{1}d_{1},\quad b=b_{1}d_{1},\quad a-qb=a_{2}d_{2},\quad b=b_{2}d_{2}
\end{align}
を満たす自然数$a_{1},b_{1},a_{2},b_{2}$が存在します。いま，$b$が二通りの表され方をしていることに注目すると，$a-qb$の$b$に二通りの$b$を代入することで，$d_{1}\leq d_{2}$と$d_{2}\leq d_{1}$に相当する二つの条件式が得られそうです。まず，$a-qb$の形のまま$b=b_{1}d_{1}$を代入してみましょう。
a-qb &= a_{1}d_{1}-qb_{1}d_{1} = (a_{1}-qb_{1})d_{1}
\end{align}
したがって，$d_{1}$は$a-qb$の約数となります。$d_{2}$は$a-qb$と$b$の最大公約数であることから，$d_{1}$は$d_{2}$以下であることが分かります。すなわち，$d_{1}\leq d_{2}$が得られました。
$a-qb$に関する最大公約数の情報は使ってしまいましたので，$a$に関する最大公約数の情報を活用したいです。現状，$a=a_{1}d_{1}$も使ってしまいましたので，$a-qb=a_{2}d_{2}$を変形した$a=qb+a_{2}d_{2}$に対して$b=b_{2}d_{2}$を代入してみましょう。
a &= qb_{2}d_{2}+a_{2}d_{2} = (a_{2}-qb_{2})d_{2}
\end{align}
したがって，$d_{2}$は$a$の約数となります。$d_{1}$は$a$と$b$の最大公約数であることから，$d_{2}$は$d_{1}$以下となります。すなわち，$d_{2}\leq d_{1}$が得られました。以上より，$d_{1}\leq d_{2}$かつ$d_{2}\leq d_{1}$が示されましたので，$d_{1}=d_{2}$，すなわち式$(\ref{主題1})$が得られます。
特に，$a$の$b$による割り算の余りを$r$とおくと，$a-qb\geq 0$を満たす最大の$q$を$\hat{q}$に対して$r=a-\hat{q}b$となります。この$\hat{q}$に対しても$d_{1}=d_{2}$が成り立ちますので，式$(\ref{主題2})$が得られます。
参考文献
本稿の執筆にあたり参考にした文献は，以下でリストアップしております。
コメント