初等整数論/整除性
倍数・約数

定義
倍数・約数

q {\displaystyle q} が存在するとき、これを、「a は b の倍数」、「b は a の約数」、「a は b で割り切れる」という。記号で、 b | a {\displaystyle b\,|\,a} 。
倍数・約数

証明 b | a 0 , a 1 , a 2 , ⋯ , a n {\displaystyle b\,|\,a_{0},a_{1},a_{2},\cdots ,a_{n}} より、 b q 0 = a 0 , b q 1 = a 1 , ⋯ {\displaystyle bq_{0}=a_{0},bq_{1}=a_{1},\cdots } とおく。すると、
倍数・約数

a 0 x + a 1 x + a 2 x + ⋯ + a n x = b q 0 x + b q 1 x + b q 2 x + ⋯ + b q n x = b x ( q 0 + q 1 + q 2 + ⋯ + q n ) {\displaystyle {\begin{aligned}a_{0}x+a_{1}x+a_{2}x+\cdots +a_{n}x&=bq_{0}x+bq_{1}x+bq_{2}x+\cdots +bq_{n}x\\&=bx(q_{0}+q_{1}+q_{2}+\cdots +q_{n})\end{aligned}}}
倍数・約数

より、b の倍数であることから、 b | a 0 x + a 1 x + a 2 x + ⋯ + a n x . {\displaystyle b\,|\,a_{0}x+a_{1}x+a_{2}x+\cdots +a_{n}x.}
除法の原理

これも整数論の根幹の部分を成す基本的かつ大事な定理である。
除法の原理

定理 1.2 (除法の原理)
除法の原理

証明 まずは存在することを証明する。そのために、まずは自然数についてを証明し、それを利用して負の数と 0 の場合を証明すれば整数全てを網羅できる。
除法の原理

a {\displaystyle a} についての数学的帰納法で証明する。
除法の原理

(i) a = 1 {\displaystyle a=1} のとき
除法の原理

b = 1 {\displaystyle b=1} ならば、 a = b 1 + 0 {\displaystyle a=b1+0} とすることで定理の主張を満たす。 b > 1 {\displaystyle b>1} ならば、 a = b 0 + 1 {\displaystyle a=b0+1} とすることで定理の主張を満たす。
除法の原理

(ii) a = n {\displaystyle a=n} のとき成り立つと仮定する
除法の原理

すなわち、 n = b q + r ( 0 ≦ r < b ) {\displaystyle n=bq+r(0\leqq r<b)} なる q , r {\displaystyle q,r} が存在する。
除法の原理

0 ≦ r < b − 1 {\displaystyle 0\leqq r<b-1} ならば、 n + 1 = b q + ( r + 1 ) ( 0 ≦ r < b ) {\displaystyle n+1=bq+(r+1)\ \ \ \ \ (0\leqq r<b)} より n+1 でも正しい。 r = b − 1 {\displaystyle r=b-1} ならば、 n + 1 = b q + r + 1 = b ( q + 1 ) + 0 {\displaystyle {\begin{aligned}n+1&=bq+r+1&=b(q+1)+0\end{aligned}}} となって、結局 n+1 の場合も正しい。
除法の原理

(i) (ii) によって数学的帰納法から、自然数について成り立つことが分かった。
除法の原理

次に、負数の場合である。
除法の原理

a < 0 ⇒ − a > 0 {\displaystyle a<0\Rightarrow -a>0} であるので、先ほど証明したことから − a = b q + r ( 0 ≦ r < b ) ⋯ ( 1 ) {\displaystyle -a=bq+r\ \ \ \ \ (0\leqq r<b)\cdots (1)} なる q , r {\displaystyle q,r} が存在する。
除法の原理

( 1 ) ⟺ a = b ( − q ) + ( − r ) ( − b < − r ≦ 0 ) ⟺ a = b ( − q ) − b + ( − r + b ) ( 0 < − r + b ≦ b ) {\displaystyle {\begin{aligned}(1)&\iff a=b(-q)+(-r)\ \ \ \ \ (-b<-r\leqq 0)\\&\iff a=b(-q)-b+(-r+b)\ \ \ \ \ (0<-r+b\leqq b)\end{aligned}}}
除法の原理

よって、 0 < − r + b < b {\displaystyle 0<-r+b<b} ならば定理は正しい。そうではなく、 − r + b = b {\displaystyle -r+b=b} のときも、 − r + b = b ⟺ r = 0 {\displaystyle -r+b=b\iff r=0} であることから定理の主張を満たす。
除法の原理

最後に 0 の場合であるが、これは自明。
除法の原理

以上より全ての整数において除法の原理を満たす q, r が存在することが証明された。
除法の原理

次に、その唯一性を証明する。仮にとある整数 a , b > 0 {\displaystyle a,b>0} でこれが成り立たず、
除法の原理

a = b q + r ( 0 ≦ r < b ) a = b q ′ + r ′ ( 0 ≦ r ′ < b ) q ≠ q ′ ∨ r ≠ r ′ {\displaystyle {\begin{aligned}a&=bq+r\ \ \ \ \ (0\leqq r<b)\\a&=bq'+r'\ \ \ \ \ (0\leqq r'<b)\\q&\neq q'\vee r\neq r'\end{aligned}}}
除法の原理

だったとする。すると、
除法の原理

( b q + r ) − ( b q ′ + r ′ ) = a − a ⟺ b ( q − q ′ ) + ( r − r ′ ) = 0 ⟺ b ( q − q ′ ) = r ′ − r {\displaystyle {\begin{aligned}(bq+r)-(bq'+r')=a-a&\iff b(q-q')+(r-r')=0\\&\iff b(q-q')=r'-r\end{aligned}}}
除法の原理

∴ b | r ′ − r ⋯ ( 2 ) {\displaystyle \therefore b\,|\,r'-r\cdots (2)}
除法の原理

0 ≦ r ′ ∧ r < b ⇒ r < r ′ + b ⟺ r − r ′ < b ⟺ r ′ − r > − b ⋯ ( 3 ) {\displaystyle {\begin{aligned}0\leqq r'\wedge r<b&\Rightarrow r<r'+b\\&\iff r-r'<b\\&\iff r'-r>-b\cdots (3)\\\end{aligned}}}
除法の原理

0 ≦ r ∧ r ′ < b ⇒ r ′ < r + b ⟺ r ′ − r < b ⋯ ( 4 ) {\displaystyle {\begin{aligned}0\leqq r\wedge r'<b&\Rightarrow r'<r+b\\&\iff r'-r<b\cdots (4)\end{aligned}}}
除法の原理

(2), (3), (4) より r ′ − r = 0 ⟺ r = r ′ ⋯ ( 5 ) {\displaystyle r'-r=0\iff r=r'\cdots (5)}
除法の原理

したがって、再び ( b q + r ) − ( b q ′ + r ′ ) = a − a ⟺ b ( q − q ′ ) = 0 ⟺ b = 0 ∨ q − q ′ = 0 {\displaystyle (bq+r)-(bq'+r')=a-a\iff b(q-q')=0\iff b=0\vee q-q'=0}
除法の原理

ここで、 b > 0 {\displaystyle b>0} より、 q − q ′ = 0 ⟺ q = q ′ ⋯ ( 6 ) {\displaystyle q-q'=0\iff q=q'\cdots (6)}
除法の原理

(5), (6) は仮定に矛盾。したがって、唯一性が証明された。以上により除法の原理が証明された。
除法の原理

定義
除法の原理

例
除法の原理

19 = 7 ⋅ 2 + 5 {\displaystyle 19=7\cdot 2+5} 97 = 24 ⋅ 4 + 1 {\displaystyle 97=24\cdot 4+1} 186 = 38 ⋅ 4 + 32 {\displaystyle 186=38\cdot 4+32}
除法の原理

なお、余りの範囲を 0 ≦ r < b {\displaystyle 0\leqq r<b} とせず、 − b 2 ≦ r ≦ b 2 ( ⟺ r ≦ | b 2 | ) {\displaystyle -{\frac {b}{2}}\leqq r\leqq {\frac {b}{2}}(\iff r\leqq |{\frac {b}{2}}|)} とすることもできる。これを、絶対最小剰余という。例えば、
除法の原理

68 = 7 ⋅ 10 − 2 {\displaystyle 68=7\cdot 10-2}
除法の原理

がある。
公約数・公倍数

定義
公約数・公倍数

例 84, 32 の最大公約数は 4, 記号で gcd ( 84 , 32 ) = 4. {\displaystyle \gcd(84,32)=4.} または ( 84 , 32 ) = 4. {\displaystyle (84,32)=4.} 189, 42 の最大公約数は 21, 記号で ( 189 , 42 ) = 21. {\displaystyle (189,42)=21.} 230, 132, 91 の最大公約数は 23, 記号で ( 230 , 132 , 91 ) = 23. {\displaystyle (230,132,91)=23.}
公約数・公倍数

12 と 20 の最小公倍数は 60, 記号で lcm [ 12 , 20 ] = 60. {\displaystyle {\textrm {lcm}}[12,20]=60.} 9, 21, 15 の最小公倍数は 315, 記号で lcm [ 9 , 21 , 15 ] = 315. {\displaystyle {\textrm {lcm}}[9,21,15]=315.}
公約数・公倍数

6, 7 は互いに素。92, 15 は互いに素。3, 4, 5 は対ごとに互いに素である。4, 6, 7 は互いに素であるが、 ( 4 , 6 ) = 2 {\displaystyle (4,6)=2} なので対ごとに互いに素ではない。6, 10, 15 は互いに素であるが、 ( 6 , 10 ) = 2 , ( 10 , 15 ) = 5 , ( 6 , 15 ) = 3 {\displaystyle (6,10)=2,(10,15)=5,(6,15)=3} とどの2つをとっても互いに素ではない。
公約数・公倍数

次に述べるものは直観的に考えて合っているもので、証明なしに受け入れられるものである。それを反省する意味でもここに証明を載せる。
公約数・公倍数

証明 2つ以上の数を a, b, ..., k とおく。公倍数は必ず存在する。なぜなら、全てをかけあわせたもの、 a b ⋯ k {\displaystyle ab\cdots k} は定義より公倍数であるからである。これが負ならば正に直すことで自然数の公倍数がみつかる。そのうち最小のものは存在する。よって最小公倍数は必ず存在する。
公約数・公倍数

さて、ここで最小公倍数を l とおき、m は任意の公倍数とする。定理 1.2 に基づいて、
公約数・公倍数

m = l q + r , 0 ≦ r < l {\displaystyle m=lq+r,\ \ \ 0\leqq r<l}
公約数・公倍数

とおけば、 r = m − l q {\displaystyle r=m-lq}
公約数・公倍数

m も l も a, b, ... , k の倍数であるから、定理 1.1 によって r も a, b, ... , k の倍数、すなわち、公倍数である。ここで、l は正のもののうち最小のものだったから、 r = 0 {\displaystyle r=0} となるしかなく、よって定理の正しいことが証明される。
公約数・公倍数

証明 2つ以上の数を a, b, ..., k とおく。公約数は必ず存在する。なぜなら、1 は定義より公約数であるからである。また、それらの数のうち、最も大きい数を l とおくと、l + 1 以上の数は公約数ではない。よって公約数には最大のものは存在する。よって最小公倍数は必ず存在する。
公約数・公倍数

さて、ここで最大公約数を m とおき、d は任意の公約数とする。また、m, d の最小公倍数を l とおく。仮定によって、a は m の倍数であり、d の倍数である。したがって、定理 1.3 によって、a は l の倍数である。同様に、b, c, ... , k も l の倍数。したがって、l は a, b, c, ... , k の公約数。したがって m は「最大」なので l ≦ m . {\displaystyle l\leqq m.} また、l は m の倍数であるから、 l ≧ m . {\displaystyle l\geqq m.} 以上より、 l = m {\displaystyle l=m} となり、d は m の約数であると分かった。
公約数・公倍数

証明 仮定より、 l = a ′ b = a b ′ {\displaystyle l=a'b=ab'} とおける。ab は a, b の公倍数である。したがって定理 1.3 によって a b = d l ⋯ ( 1 ) {\displaystyle ab=dl\cdots (1)} とおける。 先ほどの式をこれに代入して、 a b = d a ′ b , a b = d a b ′ ⟺ a = d a ′ , b = d b ′ ⋯ {\displaystyle ab=da'b,ab=dab'\iff a=da',b=db'\cdots } つまり、d は a, b の公約数。定理 1.4 に基づいて、 g = d e ⋯ ( 2 ) {\displaystyle g=de\cdots (2)} とおく。仮定により、 g | a , b ⟺ d e | d a ′ , d b ′ ⟺ e | a ′ , b ′ . {\displaystyle g\,|\,a,b\iff de\,|\,da',db'\iff e\,|a',b'.} したがって、 a ′ = e a ′′ , b ′ = e b ′′ {\displaystyle a'=ea'',b'=eb''} とおけば、最初の式に代入して
公約数・公倍数

l = a b ′′ e = b a ′′ e {\displaystyle l=ab''e=ba''e} となるが、 e > 1 {\displaystyle e>1} であると、 l e ( < l ) {\displaystyle {\frac {l}{e}}(<l)} が a, b の公倍数となり、l の最小性に反するため、e = 1 となるしかなく、(2) より g = d . {\displaystyle g=d.} (1) より、 a b = g l . {\displaystyle ab=gl.}
公約数・公倍数

次の定理も、1.3, 1.4 とともに無条件で受け入れられている、非常に重要な定理である。
公約数・公倍数

証明 定理 1.5 より、a, b の最小公倍数は ab である。bc は a の倍数かつ b の倍数、したがって定理 1.3 によって a b | b c ⟺ a | c . {\displaystyle ab\,|\,bc\iff a\,|\,c.}
公約数・公倍数

定理 1.3 のみを使って証明することもできる。a, b の最小公倍数は当然 b の倍数であるから kb とかける。ab は明らかに a, b の公倍数であるから定理 1.3 より kb の倍数である。よって a は k の倍数である。そこで a = l k {\displaystyle a=lk} とおくと k b = a b / l {\displaystyle kb=ab/l} が a の倍数であるから b / l {\displaystyle b/l} は整数、つまり l は b の約数である。よって l は a, b の公約数でなければならないが仮定より l=1 つまり k=a でなければならない。したがって a, b の最小公倍数は ab である。bc は a の倍数かつ b の倍数、したがって定理 1.3 によって a b | b c ⟺ a | c . {\displaystyle ab\,|\,bc\iff a\,|\,c.}
公約数・公倍数

定理 1.6 は次のように一般化される。
公約数・公倍数

証明 a ′ = a / gcd ( a , b ) , b ′ = b / gcd ( a , b ) {\displaystyle a'=a/\gcd(a,b),b'=b/\gcd(a,b)} とおくと gcd ( a ′ , b ′ ) = 1 {\displaystyle \gcd(a',b')=1} なので定理 1.6 より a | b c ⟺ a ′ | b ′ c ⟺ a ′ | c . {\displaystyle a\,|\,bc\iff a'\,|\,b'c\iff a'\,|\,c.}