【徹底解説】最大公約数と除算の余りの関係

本記事は数学の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため,多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

目次

最大公約数と除算の余りの関係

整数$a,q$と自然数$b$に対して,

\begin{align}
\gcd(a,b) &= \gcd(a-qb,b)\label{主題1}
\end{align}

が成り立つ。ただし,$\gcd$は最大公約数を表す。特に,$a$の$b$による除算の余りを$r$とすると,

\begin{align}
\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}$を導きます。まず,最大公約数の定義より,

\begin{align}
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}$を代入してみましょう。

\begin{align}
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}$を代入してみましょう。

\begin{align}
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})$が得られます。

参考文献

本稿の執筆にあたり参考にした文献は,以下でリストアップしております。

シェアはこちらからお願いします!

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.

目次