初等整数論
初等整数論
自然数や整数の基本的な性質とその原理を整理してみよう．簡単な割り算計算の果たしている役割が非常に大きいことに気が付くであろう．
目次
- 割り算原理
- 最大公約数，最少公倍数
- 素数
整数 a,bについて，ある整数 c が存在して， a = bc と表されるとき，a は b の 倍数である，a は b で 割り切れる，あるいは b は a の 約数（または因数）であるなどといい，b | a という記号で表す．整数 a ≠ 0 が与えられたとき，±1, ±a は a の約数である．これらを a の自明な約数という．
自然数のもっとも重要な性質は次の 割り算原理である．
定理 1 a, b を整数とし，b > 0 を仮定すれば，a = bq + r, (0 ≦ r < b) を満たす自然数 q, r が一意的に存在する．このとき，q を 商，r を 余りという．
整数 a1,...,ar が与えられたとき，すべての ai の共通の倍数になる 0 でない整数 を a1, ... ,ar の 公倍数といい， 最小公倍数は公倍数の中で最小の自然数として定義され，LCM(a1, ..., ar) という記号で表される．ただし，ai の中に 0 がある場合には，LCM(a1, ..., ar) = 0 と定めておく．
また，すべての ai の共通の約数になる整数を a1, ..., ar の 公約数という． 最大公約数は公約数の中で最大の自然数として定義され，GCD(a1, ..., ar) という記号で表される．特別に，GCD(0, ..., 0) = 0 としておく．
2 つの整数 a, b について，GCD(a,b) = 1 のとき，a と b は 互いに素であるという．これは，a, b の公約数が ±1 しかないことを意味する．
補題 2 a1, ..., ar を 0 でない整数とする．
- l = LCM(a1, ..., ar) のとき，a1, ..., ar の任意の公倍数は l の倍数である．
- d = GCD(a1, ..., ar) のとき，a1, ..., ar の任意の公約数は d の約数である．
補題 3 整数 a, b (bneq 0) に対して，a = bq + r と表されたとする．このとき，GCD(a,b) = GCD(b,r) が成立する．
このことを利用して，自然数 a, b の 最大公約数 GCD(a,b) を求めることができる．次のようにすればよい．まず，q1 = q, r1 = r とおき，順に，
| a | = q1b + r1 |
| b | = q2r1 + r2 |
| r1 | = q3r2 + r3 |
| ... |
| ri-1 | = qi + 1ri + ri+1 |
| ... |
のように割り算をすると，b > r1 > r2 > ... だから，この操作は有限回で終了して，
rn-1 = qn+1rn
となる n が存在する．このとき，補題3により，
GCD(a,b) = GCD(b,r1) = GCD(r1,r2) = ... = GCD(rn,0) = rn
が成立するので，rn が求める最大公約数である．この方法を ユークリッドの互除法という．
定理 4
整数 a,b に対して，d = GCD(a,b) とすると，sa + tb = d を満たす整数 s, t が存在する．
自明な約数しかもたない 2 以上の自然数を 素数という．小さい方から並べると，素数は 2,3,5,7,11,13,17,23,29, のように続く．素数以外の自然数（≧ 2）は 合成数とよばれる．
素数の求め方については エラトステネスのふるいが有名である．たとえば，100 以下の素数を求めるときには，まず，2 以外の 2 の倍数を消す．このとき，残っている 2 より大きい数の中で最も小さい数は 3 になるので，3 以外の 3 の倍数を消す．以下同様に，残っている数の中で最も小さい数は素数であるので，その素数を残して，その他の倍数をすべて消すという操作を続ける．この操作で最後まで残った数が素数である．
補題 5 素数は無限に存在する．
補題 6 素数 p について，p|ab であれば，p|a あるいは p|b が成立する．
問題 1 素数 p について，p|a1 ... ar であれば，ある ai が存在して，p|ai であることを示せ．
定理 7（算術の基本定理） 任意の自然数 n （≧ 2）は素数の積に分解され，その分解は素数の順序を除いて一意的である．この分解を素因数分解とよぶ．
証明 存在については、素因数分解の存在を参照されたい。ここでは素因数分解の一意性を証明する．２通りの素因数分解が得られたと仮定する．
n = p1 ... pr = q1 ... qs
ただし，pi, qj はすべて素数とする．このとき，r = s であり，番号をつけ直すことにより，p1 = q1, ..., pr = qr となることを r に関する帰納法で証明する．
まず，r = 1 のときには，n は素数だから，n = q1 ... qs が可能なのは s = 1 の場合のみである．次に，r = k のときに順序を除く一意性が成立することを仮定する．等式 n = p1 ... pk+1 = q1... qs があれば，pk+1|n だから，ある qj があって，pk+1|qj となる（補題6）．双方が素数であるので，pk+1 = qj でなければならない．番号をつけ直して，pk+1 = qs として一般性を失わない．このとき，p1 ... pk = q1 ... qs-1 が成立する．帰納法の仮定により，s - 1 = k であり，番号をつけ直して，p1 = q1, ..., pk = qk とできる．したがって，pk+1 = qs と合わせて，r = k + 1 のときにも一意性が成立することが示されたことになる．
問題 3 自然数 n について，その m 乗根が有理数になる必要十分条件は n が自然数の m 乗であることである．このことを示せ．
トップへ酒井文雄記（2000年4月）