整数の除法、割り切れる・約数b|a、最大公約数gcdとは？

どうも、木村（@kimu3_slime）です。

今回は、整数同士の除法、割り切れる・約数とは、最大公約数について紹介します。

整数同士が割り切れるとは
最大公約数とは
こちらもおすすめ

整数同士が割り切れるとは

「割り切れる」とはどういうことでしょうか？

有理数や実数の範囲で割り算を考えれば、\(7 \div 3 =\frac{7}{3}\)といったように、整数同士は常に割り切れます。

整数の理論では、そうではなく、\(7\div 3 =2 \)あまり\(1\)といったような整数の割り算（除法 division）を考えます。3で割ってあまり1という式は、\(7=3 \times 2 +1\)が成り立つことです。

整数同士の割り算は、除法の原理（と呼ばれる定理）によって定まっています。

除法の原理（division algorithm）

\(a,b\)を任意の整数で、\(b\neq 0\)とする。このとき、次の条件を満たす整数\(q,r\)、\(0\leq r < |b|\)がただひとつ存在する。

\[ \begin{aligned}a = qb+r\end{aligned} \]

このとき、\(b\)を割る数（divisor）、\(q\)を商（quotient）、\(r\)を余り、剰余（remainder）と呼ぶ。

これによって、負の整数の割り算も定義できています。\(-7 =2\cdot(-4)+1\)なので、\(-7\)を\(-4\)で割った商は\(2\)、余りは\(1\)です。

余りは常に正（非負）と約束していることに注意しましょう。\(-7 =1\cdot(-4)-3\)という式は正しいですが、だからといって\(-7\)を\(-4\)で割った商は\(1\)、余りは\(-3\)とは言いません（商、余りは\(a,b\)に対してただひとつ定まるものを考えたい）。

こうした割り算を考えた時、余りがない\(r=0\)ときを、割り切れると呼ぶわけです。

\(a\)が\(b\)で割り切れる（divisible）とは、\(a=kb\)となる整数\(k\)が存在することです。このとき、\(b\mid a\)と記号で表します（順序に注意）。割り切れないときは、\(b \nmid a\)と書きます。

\(b\mid a\)と書いてあったときに、どっちがどっちを割るのか紛らわしく思うかもしれません。これは英語式の語順で、\(b\) divides \(a\)（\(b\)が\(a\)を割り切る\(\mid\)）と読めば、混同することはないでしょう。

例えば\(6 \mid 18\)ですが、\(7 \nmid 18\)です。これは感覚的に「割り切れる」「割り切れない」と思うだけでなく、その理由が説明できるようにしましょう。\(18= 3\times 6\)なので、割り切れる。\(18=2\times 7 +4\)で余りが4なので、割り切れません（除法の原理より、割り切れることと余りが\(r=0\)であることは同値。割り切れないことと余りが\(r\neq 0\)であることは同値）。

\(a\)が\(b\)で割り切れるとは、\(a=kb\)となる整数\(k\)が存在すること、すなわち\(a\)が\(b\)の倍数（multiple）であることと同じです。\(b\)は\(a\)の約数（divisor）である、\(b\)は\(a\)の因数（factor）であるとも呼びます。

用語が多くて混乱するかもしれませんが、すべて同一の条件を指しています。その意味を具体例を通して理解すれば、相互に読み替えることはできるでしょう。

最大公約数とは

割り切れるとはどういうことかを定義したので、約数が定義されました。約数を考えるときは、正の約数を考えることが多いです。（単に約数と言うとき、正の約数であることを暗に意味することもある）

\(-6\)の正の約数をすべて求めてみましょう。\(1\mid -6, 2\mid -6, 3 \mid -6, 6 \mid -6\)なので、正の約数は\(1,2,3,6\)です。（すべての整数\(a\)に対して、\(1\)と\(a\)自身は常に\(a\)の約数になります。確かめてみてください）

このように、整数をひとつ決めれば、その正の約数のリストがひとつ決まります。整数が2つ\(a,b\)あれば、その正の約数のリストは2つ決まります。それらに共通する約数で、最大のものを、最大公約数と呼ぶわけです。

\(a,b\)を任意の整数とします。正の整数\(d\)で、次の条件を満たすものを考えましょう。

共通の約数：\(d \mid a\)、\(d \mid b\)
共通の約数のうち最大である：任意の整数\(c\)に対し、\(c\mid a\)、\(c \mid b\)ならば\( c \leq d\)

この\(d\)を\(a,b\)の最大公約数（greatest common divisor）と呼び、\(d=\mathrm{gcd}(a,b)\)と記号で表します。共通の約数は、公約数（common divisor）とも呼ばれます。

\(\mathrm {gcd}(10,24)\)を求めてみましょう。\(10\)の正の約数は\(1,2,5,10\)で、\(24\)の正の約数は\(1,2,3,4,6,8,12,24\)です。共通の約数は、\(1,2\)です。よってそのうちの最大のものなので、\(\mathrm {gcd}(10,24) =2\)であることがわかりました。

最大公約数は、必ず\(a,b\)の絶対値より小さくなります。最大公約数を間違って求めないためのチェック条件のひとつです。（\(a,b \neq 0\)ならば、\(1 \leq \mathrm{gcd}(a,b) \leq \min \{|a|,|b|\}\)です。確かめてみてください。）

\(\mathrm {gcd}(3,14)\)を求めてみましょう。\(3\)の正の約数は\(1,3\)で、\(14\)の正の約数は\(1,2,7,14\)です。したがって、\(\mathrm {gcd}(3,14)=1\)です。

一般に、\(\mathrm {gcd}(a,b)=1\)のとき、\(a,b\)は互いに素（relatively prime）と言います。\(3,14\)は互いに素です。素数（prime number）は、互いに素な整数たちの集まりと言えます。

今回は、整数の除法、割り切れること・約数\(b\mid a\)、最大公約数gcdについて紹介してきました。

この考えは、ユークリッドの互除法や、素数を考えるために基礎となっているものです。

具体的な数についてチェックしつつ、記号や一般論も扱えるようになってみてください。

木村すらいむ（@kimu3_slime）でした。ではでは。