美的数学のすすめ

初等整数論のうち、平方剰余の相互法則の意味を当面の目標としたいと思います。ゆくゆくは、ガウス和、円分体論まで到達したいです。

ユークリッド(Euclid)の互除法(その2)

 今回は、ユークリッドの互除法を使って、最大公約数との間で成立する関係式を求めます。

 ユークリッドの互除法とは整数\(n,m\)に対し最大公約数を \( (n,m)\)と表すと \[(n,m)=(n-m,m)\] が成り立つことでした。

ユークリッド(Euclid)の互除法 - 美的数学のすすめ

 今回は\(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} \]