2.1.1 最大公約数

素因数分解の一意性が成立するメカニズムの1つにユークリッドの互除法があります。2つの自然数の最大公約数を、ユークリッドの互除法という方法で求めることからはじめましょう。最大公約数は素因数分解を用いて共通因子を見つけることにより求めることが多いですが、なぜ整数は素因数分解できるのでしょうか。「整数は必ず素因数分解できる」これはユークリッドの互除法に由来しています。

$n$と$m$の最大公約数を、$\gcd(n,m)$または$\gcd$を省略して$(n,m)$と記載します。たとえば、$(14,12)=2$です。$14$と$12$の最大公約数は、$14$を素因数分解 $14=2\times 7$し、また、$12$も素因数分解 $12=2^2\times 3$することにより、最大公約数は2と分かります。このように、最大公約数を求めるのには、素因数分解を行って、そのうち重なっているものを取り出すことで求められます。しかし、この方法では、 $(1200,1201)$のように、大きな数の場合困ってしまいます。1200と1201の素因数分解はすぐにはできませんね。でも、ユークリッドの互除法を用いれば、 $(1200,1201)=1$だとすぐに分かります。このように、ユークリッドの互除法とは、素因数分解をせずに、最大公約数を求める方法です。

さて、$n,m$が自然数（1以上の整数)のみならず整数（負の整数を含む）にまで最大公約数の定義を拡大します。その前に「割り切れる」とはどういうことなのか、厳密に定義しておきます。

定義 2.1.1
$n$と$m$が整数（したがって、負の整数も含みます。）のとき、 整数$d$が存在し$n=dm$となるとき、$m$は$n$を割り切る又は$n$は$m$で割り切れる（divisible）といい、 ${\bf m\mid n}$と記載します。 また、$m$が$n$を割り切らないとき、$m\nmid n$と記載します。

わざわざ、当然のことを定義したのは、今後、拡張した整数の体系において「割り切れる」を定義するためです。

例 2.1.2
$3\mid 15$ , $（-3）\mid 15$ , $3\vert(-15)$ , $(-3)\mid(-15)$
$4\nmid 15$ , $5　\nmid 12$ , $-3\nmid 16$ , $32\nmid 23$

定義 2.1.3
$n$が整数のとき$n$を割り切る数を約数（divisor）という。 $n,m$が整数のとき、$n,m$の公約数（common divisor）とは$n,m$の共通の約数のことをいい、最大公約数（greatest common divisor）とは公約数のうち最大のもの（したがって、必ず正）を指します。

3つ以上の整数 $n,m,l,\cdots$に対しても公約数、最大公約数が同様に定義されます。

上記のとおり、$n,m$の最大公約数のことを、$\gcd(n,m)$または$(n,m)$と表します。当然、 $(n,m)=(m,n)$です。また、$(n,0)=n$です（0は全ての整数を約数として持つことに注意しましょう。）。
$d=(n,m)$とすると。$d$は、$n,m$の約数ですので、 $n=dn_1,m=dm_1$とおけます。ここで、$d$が最大公約数ですので、 $(n_1,m_1)=1$です。なぜなら、仮に $(n_1.m_1)=d_1$とおくと、$d_1$は$n_1,m_1$を割り切りますので、$dd_1$は、 $n=dn_1,m=dm_1$を割り切ります。つまり、$n,m$の公約数です。しかし、dが最大公約数ですので、$d_1=1$です。以上より、以下の命題が成り立ちます。

命題 2.1.4
$n,m$を整数、 $d=\gcd(n,m)=(n,m)$とするとき、 $n_1=n/d,m_1=m/d$は整数となり、 $(n_1,m_1)=1$となる。

定義 2.1.5
整数$n,m$の最大公約数が$1$のとき、つまり、$(n,m)=1$のとき、$n$と$m$は 互いに素（coprime）であるといいます。

ここで、$n,m$の公約数を$d$とおくと、 $n=dn_1,m=dm_1$となる整数$n_1,m_1$が存在します。このとき、 $m-n=d(m_1-n_1)$ですので、$d$は$n,m-n$の公約数でもあります。逆に、$n,m-n$の公約数を$d'$とおくと $n=d'n_{1}',m-n=d'm'_1$と表せます。すると、 $m=d'(n'_1+m'_1)$ですので、$d'$は、$m$の約数、つまり、$d'$は、$n,m$の公約数にもなります。つまり、$n,m-n$の公約数は$n,m$の公約数となります。 以上より、$n,m$の公約数と$n,m-n$の公約数は一致することが分かりました。最大公約数は、公約数のうち最大のものですので、最大公約数も一致することがわかります。つまり、 $(n,m)=(n,m-n)$です。

同様な方法で、 $(n,m)=(n,m+n)$もわかります。

これを何回か繰替えすと $(n,m)=(n,m+n)=(n,m+2n)=(n,m+3n)=\cdots$です。また、 $(n,m)=(n,m-m)=(n,m-2n)=(m,m-3m)=\cdots$です。つまり、任意の整数$k$に対し、 $(n,m)=(n,m+kn)$がいえます。

これまでお話してきた、最大公約数の性質$(n,m)$をまとめておきましょう。これを使うと、簡単に最大公約数が求められます。

命題 2.1.6
$n,m$を整数とすると
（1） $(n,m)=(m,n)$
（2） $(n,m)=(-n,m)=(n,-m)=(-n.-m)$
（3） $(n,0)=n$
（4） 整数$k$に対して、 $(n,m)=(n,m-kn)$

この命題のうち、特に重要なものは（4）です。（4）を使うことにより、$(n,m)$の2つの数字を次々と小さくすることができます。例えば$(45,50)$を求めてみましょう。命題より $(45,50)=(45,5)=(5,45)=(5,45-5\cdot 9)=(5,0)=5$と求めることができます。

例 2.1.7
（1） $(32,15)=(15,2)=(2,1)=1$
（2） $(521,519)=(519,2)=(2,1)=1$
（3） $(48,32)=(32,16)=16$

例 2.1.8
$n$を整数とすると、 $(n,n+1)=(n,1)=n$です。つまり、隣り合う整数は、互いに素なことが分かります。

例 2.1.9
2離れた整数同士の最大公約数を求めていましょう。 $n$を整数とすると、 $(n,n+2)=(n,2)$となります。ここで、$n$が偶数であるとき、$(n,2)=2$、$n$が奇数のとき$(n,2)=1$ですので、$(n,n+2)$は、$n$が偶数のとき2、奇数のとき1(つまり、互いに素)と分かります。。

このように、 $(n,m)=(n,m-kn)$を何度か使い最大公約数を求める方法を、ユークリッドの互除法といいます。ユークリッドの互除法を使えば必ず最大公約数を求めることができるます。この点は次講2.1.2で確認しましょう。