ユークリッド（Euclid）の互除法（その2）
今回は、ユークリッドの互除法を使って、最大公約数との間で成立する関係式を求めます。
ユークリッドの互除法とは整数\(n,m\)に対し最大公約数を \( (n,m)\)と表すと \[(n,m)=(n-m,m)\] が成り立つことでした。
今回は\(n,m\)と最大公約数\( (n,m)\)との間で成り立つ関係式について解説します。
2.ユークリッドの互除法（その2）
2.1 最大公約数との関係式
具体的な数字を使って説明してみます。21と15の最大公約数が3であることをユークリッドの互除法で求めてみましょう。 \( (21,15)=(21-15,15)=(15,6)=(15-2\cdot6,6)=(6,3)=3 \)
です。上の式では3は、\(3=15-2\cdot6\)から計算されています。そして、6は\(6=21-15\)ですのでこれを代入すると\(3=15-2(21-15)=-2\cdot21+3\cdot15\) つまり、 \[ -2\cdot21+3\cdot15=3 \] と分かります。つまり、もとの数の一次式で最大公約数は表すことができます。
以上を一般化すると次が成立していることが分かります。
(ユークリッドの互除法ー最大公約数との関係式ー）
\(n,m\)を整数とするとき、整数\(a,b\)が存在して \[ an+bm=(n,m) \] とできる。
証明は省略しますが、上の例で21と15の場合と全く同様にできます。
2.2 最大公約数との関係式の逆
最大公約数との関係式は、一種の逆が成り立ちます。最大公約数の定義より、\(n\)は\( (n,m)\)の倍数であり、同様に\(m\) も\( (n,m)\)の倍数です。すると、\( an+bm \)は、\( (n,m)\)の倍数となります。
\(n,m\)を整数とする。このとき、整数\(a,b\)に対し、\( an+bm \)は\( (n,m)\)の倍数である。
これは、特に\(n\)と\(m\)が互いに素の場合に頻出です。\(n,m,a,b\)を\(an+bm=1\)が成り立つ整数とします。このとき、上の性質により、\(an+bm=1\)が\( (n,m)\)の倍数となり、\( (n,m)=1\)となります。これにより、次が成立します。 \[an+bm=1 \Longrightarrow nとmは互いに素 \] このとき、式が対称的であることを考えると、\(n\)と\(m\)ばかりでなく、\(n\)と\(b\)も、\(a\)と\(b\)も、\(a\)と\(m\)も全て互いに素であることが分かります。
\[ \begin{align} an+bm=1 & \Longrightarrow nとmは互いに素 \\ an+bm=1 &\Longrightarrow nとbは互いに素 \\ an+bm=1 &\Longrightarrow aとbは互いに素 \\ an+bm=1 & \Longrightarrow aとmは互いに素 \end{align} \]
2.3 最大公約数との関係式の応用
最大公約数の関係式は、応用範囲は広いです。
すでに、何度か出てきていますが、\(m\)を2以上の自然数とするときの、\(\mathbb{Z}/m\mathbb{Z}\)の既約剰余類について考えてみましょう。\(\mathbb{Z}/m\mathbb{Z}\)の既約剰余類とは、\(\bmod{m}\)において乗法に関し逆元をもつ剰余類のことです。つまり、\(n\)が\(\bmod{m}\)において既約剰余類とは、整数\(a\)が存在して\(an=1 \pmod{m}\)が成立する場合です。
上の関係式を使い、\(n\in\mathbb{Z}/m\mathbb{Z}\)の既約剰余類であることと、\(n\)と\(m\)が互いに素であることが同値であることを示してみましょう。
\[ \begin{align} nが\bmod{m}で既約 & \Longleftrightarrow an=1 \pmod{m} なる整数aが存在する\\ &\Longleftrightarrow an-1=bm なる整数a,bが存在する \\ &\Longleftrightarrow an-bm=1 なる整数a,bが存在する \\ &\Longleftrightarrow n,mは互いに素 \end{align} \]
