1.4 余りとユークリッドの互除法
皆さんが小学校でどのように割り算を学んだかを私が知っているはずもありませんが、どんな教わり方をしていたとしても割り算という演算を式に直してしまえば必ず以下のようになります。ここでは整数$a$を$b$で割ってみることにします。
$$a=bq+r$$
$q$が$a$を$b$で割ったときの「商」：quotient、$r$が$a$を$b$で割ったときの「余り」：remainderです。このとき$a$を「割られる数」、$b$を「割る数」などと言いました。当然ですが、余り$r$が$b$より大きくなることはありません。もし$r>b$なら更に$b$で割れますからね。ここまでは何ということも無いと思います。
さて、皆さんは学校で「ユークリッドの互除法」（Euclidean algorithm）を学んだかと思いますが、これはある数とある数の最大公約数を求める方法でしたね。忘れちゃったという人や教わったけどイマイチ分からんという人はここで一度確認しておきましょう。
（例題）$2016$と$1572$の最大公約数を求めなさい。
〈互除法を利用した解き方〉
まず$2016$から$1572$を１回引いて$444$を得ます。
次に$1572$から$444$を３回引いて$240$を得ます。
同様に$444$から$240$を１回引いて$204$を得ます。
以下同様にして、$240$から$204$を１回引いて$36$、
$204$から$36$を５回引いて$24$、
$36$から$24$を１回引いて$12$を得ます。
今、$24$から$12$を２回引くと$0$になります。ここで引き算は終了です。
最後に求められた$12$という数字が実は$2016$と$1572$の最大公約数なのです。
ところで、解答の中でさっきから何度も「引き算」と言っていますが、これは「割り算」とやってることは同じです。つまり、
「ある整数から、それより小さいある整数を、負にならないように最大の回数だけ引く」
という操作は割り算の操作そのものなのです。このように割り算で最大公約数を求める方法を「ユークリッドの互除法」と言いました。もちろんユークリッドの互除法を使わず、素因数分解で解く方法もあります。
〈素因数分解を利用した解き方〉
２数を素因数分解すると、それぞれ$2016=2^5 \cdot 3^2 \cdot 7$、$1572=2^2 \cdot 3 \cdot 131$となるから、最大公約数は$12$と求められる。
一見すると素因数分解の方がラクに見えるかもしれませんが、これが例えば$1489201891$と$34997515657$だったらどうでしょう？
素因数分解すると$1489201891=1187 \cdot 1254593$、$34997515657=13 \cdot 89 \cdot 30248501$となるので最大公約数は１と分かりますが、このような大きな整数の素因数分解は容易ではありません。ユークリッドの互除法は大きな数同士の最大公約数を求めるための優れた方法なのです（実はユークリッドの互除法が最大公約数を求める最良のアルゴリズムであることが知られています）。
因みにユークリッド（Euclid）は紀元前３世紀ごろのギリシャで活躍した数学者で、日本ではエウクレイデスとも呼ばれています。2000年以上も前にこのようなアルゴリズムを考え出したユークリッドの天才ぶりは見事と言うほかありません。
さて、ユークリッドの互除法には余りの性質を利用したあるカラクリが使われています。ここにユークリッドの互除法の分かりにくさが潜んでいるとも言えます。
そのカラクリというのが、
「$a=bq+r$の式において$\text{GCD}(a,b)=\text{GCD}(b,r)$が成り立つ」
という事実です。（証明はこちらから）
これを応用して最大公約数を求めるのがユークリッドの互除法なのです。では具体的な数式で見ていきましょう。ゆっくりでいいので理解して整理しながら付いてきてください。
難しいと感じたら、以下の部分は読み飛ばしてもＯＫです。（でもいずれ戻ってきてくださいね？）
いま、２つの整数$N$と$M$の最大公約数$g$を求めることを考えます。ただし$N>M$とします。公約数の定義から、$N=kg$、$M=lg$となるような整数$k、l$が存在することが言えます。ただし$k、l$は互いに素です。また、当然$k、l$についても$k>l$という関係が成り立ちます。
先ほど割り算の原理を考えたときに、整数$a$を$b$で割ると
$$a=bq+r$$
となることを確認しました。
このことから、整数$N$を$M$で割ると
$$N=Mq_1+r_1$$
となるような２つの整数$ q_1$、$r_1$が存在するはずです。仮定より、$N=kg$、$M=lg$ですから、$M$を移項すると
$$N-Mq_1=r_1$$ $$\therefore (k-lq_1)g=r_1 \ $$
となります。この左辺は$g$の倍数ですから$r_1$も$g$の倍数でなければなりません。また、この式より$r_1$は$k-lq_1$の倍数であることも分かりますが、$k、l$は互いに素であるため$k-lq_1$は$N、M$に対しても互いに素です。したがって、$$\text{GCD}(N,M)= \text{GCD}(M,r_1)$$という関係式が成り立ちます。同様に$M$を$r_1$で割っていくと$\text{GCD}(M,r_1)= \text{GCD}(r_1,r_2)$という関係が得られ・・・というふうに次々に余りを求め、結局は$${r_1、r_2、\cdots、r_n}$$が$g$で割れるかどうかだけを見ていけばよいことになります。そして最終的には$$\begin{align} \text{GCD}(N,M) &= \text{GCD}(M,r_1) \\ &=\text{GCD}(r_1,r_2) \\ &= \cdots \\ &= \text{GCD}(r_n,0) =r_n \end{align}$$となるので$r_n$と$g$は一致することになります（仮定より$\text{GCD}(N,M)=g$と定義したので、上の式は$r_n=g$を意味します）。
※式の最後の$\text{GCD}(r_n,0)=r_n$が分かりにくいという人は次のように考えて下さい。
$a=bq+r$の式において$$\text{GCD}(a,b)=\text{GCD}(b,r)$$が成り立つことは確認しましたね。ここで、$0=r_n \cdot 0+0$より、余りが$0$になっていますから$0$は$r_n$の倍数である、つまり$0$は$r_n$で割り切れると考えることができます。例えば$r_n=1$のときは$0$と$1$の最大公約数を求めればよいですが、上記の通り$0$は$1$で割り切れるので求めるべき最大公約数は$1$です。これと同じく$r_n=2$のときでも$r_n=3$のときでもいつでも求めるべき最大公約数は$r_n$に一致します。従って$$\text{GCD}(r_n,0)=r_n$$が言えるワケです。
ユークリッドの互除法では上記の原理によって最大公約数を求めているのです。
説明を見てもよく分からないという人は実際に自分の手を動かして、適当な２整数の最大公約数をユークリッドの互除法で求めてみましょう。原理が何となく分かってくるはずです！
この操作・原理を土台にした入試問題も多く出題されているので、しっかりマスターしておきましょう。