整数の除法、割り切れる・約数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|\)がただひとつ存在する。

\[a = qb+r\]

このとき、\(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\)で、次の条件を満たすものを考えましょう。

  1. 共通の約数:\(d \mid a\)、\(d \mid b\)
  2. 共通の約数のうち最大である:任意の整数\(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)でした。ではでは。

 

 

Elementary Number Theory

Elementary Number Theory

posted with AmaQuick at 2021.02.02
Burton(著)
(2012T)
4.6outof5stars
¥5,437

 

こちらもおすすめ

倍数同士の和は同じ倍数となること、整数の合同modとは

偶数、奇数の見分け方(1の位)とその証明

偶数+奇数はいつでも奇数? 読み解き方、よくある間違いと証明

3の倍数の判定法・証明 各桁の和が3の倍数となるか?