初等整数論/整除性

出典: フリー教科書『ウィキブックス（Wikibooks）』

数論 > 初等整数論 > 整除性

ここでは数論の基本である整除性の概念について論じる。素数・約数などの初等整数論の基本疑念はここに属する。

目次 1 商と剰余 2 倍数と約数 3 公倍数と公約数 4 素数

[編集] 商と剰余

次の定理は整除性における基本的な定理である。

定理1. a, bを整数とする。このとき、a=bq+r, 0 ≤ r ≤ b-1を満たす整数q=q(a), r=r(a)がただ一つ存在する。a, bが非負ならばqも非負である。

証明. 一意性は0 ≤ r ≤ b-1より明らかである。存在性をaに関する数学的帰納法により証明する。

• a=0ならばq=r=0とおけばよい。
• aが正の場合0 ≤ r(a) ≤ q-2ならば、q(a+1)=q(a)かつr(a+1)=r(a)+1とおけばよい。r(a)=q-1ならば、q(a+1)=q(a)+1かつr(a+1)=0とおけばよい。

• aが負の場合1 ≤ r(a) ≤ q-1ならば、q(a-1)=q(a)かつr(a+1)=r(a)-1とおけばよい。r(a)=0ならば、q(a-1)=q(a)-1かつr(a+1)=q-1とおけばよい。

これによって、全ての整数aに対して定理が証明された。（証明終）

[編集] 倍数と約数

a, bが整数でb = naとなる整数nが存在するとき、bはaの倍数であるといい、aはbの約数または因数であるという。またaはbを割り切る、または整除するともいう。このときa|bとかく。

例. 全ての整数は1の倍数で、2, 4, 6, 8などは2の倍数である。6の正の約数は1, 2, 3, 6である。

命題1. a, b, cを整数とする。このとき次のことが成り立つ。

a) a|b, a|cならば、すべての整数x, yに対してa|(bx+cy)である（特にa|(b+c)であり、全ての整数xに対してa|bxである）。

b) a|bならば、ac|bcである。

c) a|b, b|cならば、a|cである。

d) a|bかつb|aならばa=bまたはa=-bである。

e) a|bならば|a|≦|b|である。よって与えられた整数の約数は有限個しか存在しない。

定理2. a, Nを正の自然数とする。このとき次のことが成り立つ。

a) aの倍数xで1 ≤ x ≤ Nを満たすものの個数は[N/a]である。

b) aの正の約数の個数は高々2√a である。

証明. a)は明らかなのでb)を証明する。b|aでb > √aならば、b=a/c（cは整数で、1≤ c<√aを満たす）と表せる。よってこのようなbの個数は高々√aしかない。このことからb)が従う。（証明終）

[編集] 公倍数と公約数

a, b, cを整数とする。cがaの倍数でなおかつbの倍数であるとき、cはa, bの公倍数であるという。cがaの約数でなおかつbの約数であるとき、cはa, bの公約数であるという。

abは常にa, bの公倍数であり、したがってa, bの正の公倍数の中で最小のものが存在する。これをa, bの最小公倍数であるといい、lcm(a, b)で示す。また1, -1は常にa, bの公約数であり、命題1, d)よりa, bの公約数は有限個しかないから、a, bの公約数の中で最大のものが存在する。これをa, bの最大公約数であるといい、gcd(a, b), pgcd(a, b)あるいは単に(a, b)で記す。

例1. lcm(2, 3)=6かつgcd(2, 3)=1である。一般にgcd(a, b)=1ならばlcm(a, b)=abとなることを後に示す。

例2.

とおくと、F_nはどの2つも互いに素である。というのは、n > mならば、

だから、a|gcd(F_m, F_n)ならば、a|2でなければならず、F_nは奇数なので結局gcd(F_m, F_n)=1だからである。

命題2. a, bを自然数とする。このとき次のことが成り立つ。

a) a, bの公倍数はlcm(a, b)の倍数である。

b) ab=lcm(a, b)gcd(a, b)が成り立つ。

c) a, bの公約数はgcd(a, b)の約数である。

d) cを自然数とする。gcd(a, b)=1で、なおかつa|bcならば、a|cである。

証明.

a) cをa, bの公倍数だが、n=lcm(a, b)の倍数ではない数とする。

定理1より、c=nq+rかつ0 ≤ r ≤ n-1となる自然数q, rが存在する。r=c-nq より定理1から、rもa, bの倍数となるが、r < nであるから、n=lcm(a, b)に矛盾する

b) bはgcd(a, b)の倍数なので b/gcd(a, b) は自然数である。よってab/gcd(a, b)はaの倍数。同様にしてこれはbの倍数でもあるから lcm(a, b)|ab/gcd(a, b) であるから、lcm(a, b)gcd(a, b)|abである。

また、lcm(a, b)/bは整数だから、 ab/lcm(a, b)はaの約数。同様にしてこれはbの約数でもあるから ab/lcm(a, b)|gcd(a, b) であるから、 ab|lcm(a, b)gcd(a, b)。

したがって、命題1, d)よりab=lcm(a, b)gcd(a, b)。

c) cをa, bの公約数とし、n=gcd(a, b)とする。このとき、ab/n=lcm(a, b)であり、ab/cはa, bの公倍数だからa)よりab/cはab/nの倍数である。よって c|n である。

d) a|bcだからbcはa, bの公倍数、よってa)よりbcはlcm(a, b)の倍数である。gcd(a, b)=1なのだからb)よりlcm(a, b)=abである。したがってab|bc、よってa|cである。（証明終）

定理3. a, bを整数とする。このとき、an+bm=gcd(a, b)を満たす整数n, m)が存在する。

証明. bに関する帰納法で証明する。b=1のときは、n=1, m=a-1とおけばよい。

そこで、bに対して定理が成り立つことをbがより小さいときには常に定理が成り立つという仮定のもとで示す。定理1よりa-bs=r, 0 ≤ r ≤ b-1を満たす整数s, rが存在する。

r=0のときは、bはaの約数なので、a-b(s-1)=b=gcd(a, b)である。

r>0のときは、帰納法の過程より、b-rt=gcd(b, r)を満たす整数tが存在する。よって、-at+b(1+st) =b-rt=gcd(b, r)=gcd(b, a-bs)=gcd(a, b)となる。よって、n=-t, m=1+stとおけばよい。

これにより、定理が証明された。（証明終）

この証明で用いた方法で実際にgcd(a, b)を計算することができる（ユークリッドの互除法）。

[編集] 素数

整数pが素数であるとは、pが1でも-1でもなく、なおかつpの正の約数が1とpしか存在しないことをいう。整数aの素数の約数をaの素因数という。また、1でも-1でも素数でもない整数を合成数という。

素数に関する次の命題は基本的である。

命題3. a, bを整数とし、pを素数とする。このとき、次のことが成り立つ。

a) p|aまたはgcd(a, p)=1である。

b) p|abならばp|aまたはp|b。

証明.

a) gcd(a, p)はpの正の約数なので1かpである。gcd(a, p)=pならば、pはaの約数である。

b) p|abでありp|aでないなら、a)よりgcd(a, p)=1だから、命題2, d)よりp|bである。（証明終）

命題 3のb)は定理3を使って証明することもできる。

証明2. pがaを割り切らないなら命題3のa)より(a, p)=1だから、定理3よりan+pm=1となる整数m, nが存在する。 このとき、abn+pbm=bである。よって、p|abなら、左辺はpの倍数だからbもpの倍数でなければならない。（証明終）

命題4. 1より大きいすべての整数はいくつかの素数の積に表せる。

証明. 2の正の約数は1と2しかないから、それ自体が素数である。

nを整数とし、2≤ x≤ nとなる全ての整数xがいくつかの素数の積で表せるとする。このときn+1がいくつかの素数の積で表せることを示す。

n+1がそれ自体素数であれば、n+1は1つの素数の積で表せる。

n+1が素数でなければ、a|(n+1)かつ1 < a < n+1となる整数aが存在する。n+1=abとおくと、1 < a, b < n+1よりa, bはいくつかの素数の積で表せる。したがって、n+1=abもいくつかの素数の積で表せる。（証明終）

これらのことから、素数に関する最も基本的な、次の二つの定理を証明することができる。

定理4. 素数は無限に多く存在する。

証明1. 素数が有限個しか存在しないと仮定し、それを2, 3, 5, ..., pとする。ここで、 N=2 × 3 × 5 × ... × p + 1 とおく。このとき、命題4よりNはいくつかの素数の積で表される。よって、Nを割り切る素数 q が存在する。仮定よりqは2, 3, 5, ..., pのいずれかであるが、Nは2, 3, 5, ..., pのいずれでも割り切れない。これは矛盾である。（証明終）

証明2. 「公倍数と公約数」の例2で述べた数列F_nはどの二つも互いに素である。命題4よりF_nの素因数p_nが存在するが、これはどの二つも相異なる。よってp_nは無限個の素数の列をなしている。（証明終）

注釈. pを素数とし、N_p=2 × 3 × 5 × ... × p + 1とおいたとき、

• N₂=3,
• N₃=7,
• N₅=31,
• N₇=211,
• N₁₁=2311,

は素数である。このことや、上述した素数の無限性の証明から、N_pの形の数は全て素数なのではないかという考えが生じる。しかし

• N₁₃=30031=59*509

は素数ではない。

• N_pの形の素数は無限に多く存在するか？
• N_pの形の合成数は無限に多く存在するか？

といった問いは未だに解決されていない。

定理5. （初等整数論の基本定理）すべての自然数は（0個かも知れない）いくつかの素数の積に（順序を除いて）一意的に表せる。

証明. 存在性は命題4で示されているから、ここでは一意性のみを示す。

nを自然数とし、nが素数の積として

,

の二通りに表せたとする。ここで双方の表示に共通する素数があれば、その素数で双方の式の両辺を割ることにより、

かつq|mとなる自然数m、素数p_i、素数q（qはp_iのいずれとも異なる）を得る。しかし命題3, b)よりqはp_iのいずれかと等しくなければならない。これは矛盾である。（証明終）