定義
整数
a
,
b
{\displaystyle a,b}
a
=
b
q
{\displaystyle a=bq}
q
{\displaystyle q}
倍数 」、「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
|
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}
証明
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 (除法の原理 )
任意の整数
a
,
b
>
0
{\displaystyle a,b>0}
a
=
b
q
+
r
(
0
≦
r
<
b
)
{\displaystyle a=bq+r\ \ \ \ \ (0\leqq r<b)}
q
,
r
{\displaystyle q,r}
証明
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
+
1
<
b
)
{\displaystyle n+1=bq+(r+1)\ \ \ \ \ (0\leqq r+1<b)}
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}}}
(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) は仮定に矛盾。したがって、唯一性が証明された。以上により除法の原理が証明された。
定義
先ほどの定理をそのまま用いると、q を 「a を b で割った商 」、r を 「a を b で割った余り 」という。またこれを、「b を法 とした a の最小正剰余 」ともいう。 例
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}
がある。
定義
2つ以上の数 a, b, ... について、a の約数であり、かつ b の約数であり、かつ、... という数を「a, b, ... の公約数 」という。自然数の公約数のうち最大のものを「最大公約数 」という。「g.c.d, gcd」などとも書かれ、gcd(a, b, ...)、または単に (a, b, ...) という記号で表す。
2つ以上の数 a, b, ... について、a の倍数であり、かつ b の倍数であり、かつ、... という数を「a, b, ... の公倍数」という。自然数の公約数のうち最小のものを「最小公倍数 」という。「l.c.m, lcm, LCM」などとも書かれ、lcm[a, b, ...] という記号で表す。
特に、gcd(a, b) = 1 のとき、「a, b は互いに素 である」、という。さらにここでは、3つ以上の数 a, b, c, ... については、gcd(a, b, c, ...) = 1 を「広義の互いに素」あるいは単に「互いに素」、3つ以上の数のうち任意の異なる2数をとっても互いに素であるとき、「狭義の互いに素」「対ごとに互いに素」「どの2つも互いに素」という。対ごとに互いに素な数の組は互いに素である。このような区別は一般的ではなく曖昧な部分もあるがここではこのように約束する。 例
84, 32 の最大公約数は 4, 記号で
gcd
(
84
,
32
)
=
4.
{\displaystyle \gcd(84,32)=4.}
(
84
,
32
)
=
4.
{\displaystyle (84,32)=4.}
(
189
,
42
)
=
21.
{\displaystyle (189,42)=21.}
(
230
,
132
,
91
)
=
23.
{\displaystyle (230,132,91)=23.}
12 と 20 の最小公倍数は 60, 記号で
lcm
[
12
,
20
]
=
60.
{\displaystyle {\textrm {lcm}}[12,20]=60.}
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
)
=
2
,
(
10
,
15
)
=
5
,
(
6
,
15
)
=
3
{\displaystyle (6,10)=2,(10,15)=5,(6,15)=3}
次に述べるものは直観的に考えて合っているもので、証明なしに受け入れられるものである。それを反省する意味でもここに証明を載せる。
2つ以上の数の公倍数は最小公倍数の倍数である。 証明
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つ以上の数の公約数は最大公約数の約数である。 証明
さて、ここで最大公約数を 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
.
{\displaystyle l\geqq m.}
l
=
m
{\displaystyle l=m}
任意の自然数 a, b について、
gcd
(
a
,
b
)
=
g
,
lcm
[
a
,
b
]
=
l
{\displaystyle \gcd(a,b)=g,{\textrm {lcm}}[a,b]=l}
a
b
=
g
l
{\displaystyle ab=gl}
証明
l
=
a
′
b
=
a
b
′
{\displaystyle l=a'b=ab'}
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 }
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)}
g
=
d
.
{\displaystyle g=d.}
a
b
=
g
l
.
{\displaystyle ab=gl.}
gcd
(
a
,
b
)
=
1
{\displaystyle \gcd(a,b)=1}
a
|
b
c
⟺
a
|
c
{\displaystyle a\,|\,bc\iff a\,|\,c}
証明
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}
b
/
l
{\displaystyle b/l}
a
b
|
b
c
⟺
a
|
c
.
{\displaystyle ab\,|\,bc\iff a\,|\,c.}
a
|
b
c
⟺
a
gcd
(
a
,
b
)
|
c
{\displaystyle a\,|\,bc\iff {\frac {a}{\gcd(a,b)}}\,|\,c}
証明
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}
a
|
b
c
⟺
a
′
|
b
′
c
⟺
a
′
|
c
.
{\displaystyle a\,|\,bc\iff a'\,|\,b'c\iff a'\,|\,c.}
![{\displaystyle {\textrm {lcm}}[12,20]=60.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0735a19c839af6192133e18e9842a530a7ee9955)
![{\displaystyle {\textrm {lcm}}[9,21,15]=315.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41e0aca7c87fb7fb5c77f4400e5709b2da011346)
![{\displaystyle \gcd(a,b)=g,{\textrm {lcm}}[a,b]=l}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15688dc8e91bba8db102be2106402e1adb4125dd)
