可除性
可除性は、整数を構造をもつ体系へと変換するという点において、数論の実質的な出発点である。すなわち、数を単なる「量」としてではなく、互いに適合するか否かという観点から捉えるようになる。単一の構造である a\mid b を用いることで、簡約や因数分解の判定基準から、ユークリッドのアルゴリズムのような手続きの中核に至るまでを表現できる。これにより、大きな数に対しても最大公約数を短時間で計算することが可能となる。さらに、可除性は、応用数学や計算機科学において繰り返し現れる概念の技術的基盤でもある。すなわち、合同、剰余算術、検証、符号化、そして（後に扱う）暗号理論である。可除性を習得することは、本質的には、整数に潜む不可視のパターンを見抜き、それらを常に機能する手続きへと変換する方法を学ぶことに他ならない。
学習目標
本資料を修了した時点で、学生は以下の事項ができるようになる。
- 理解する：整数間における可除性の関係。
- 理解する：可除性の定義およびその性質。
- 展開する：可除性に関連する結果や定理の数学的証明。
可除性の定義
「a が b を割り切る」という非形式的な考え方は、それを整数間の関係として表現することで厳密なものとなる。整数 a が整数 b を割り切るとは、b が a の正確な倍数として書ける場合をいう。この定義は本資料全体の基礎であり、「正確に当てはまる」といった表現を、検証可能な基準へと変換する。
定義. a,b\in\mathbb{Z} を a\neq 0 とする。a が b を割り切るとは、かつそのときに限り、ある整数 k\in\mathbb{Z} が存在して b=ka と書けることである。このとき a\mid b と書く。そうでない場合には a\nmid b と書く。
a\mid b := (\exists k \in \mathbb{Z})(b = ka )
この定義において、数 k は可除性に対応する商（または因子）と呼ばれる。例えば、6\mid 42 と主張することは、42=6k を満たす k\in\mathbb{Z} が存在することを意味する。この場合、k=7 を取ればよい。
重要な注意点
- 条件 a\neq 0 は本質的である。というのも、もし a=0 を許そうとすると、可除性の条件は b=0\cdot k を満たす k\in\mathbb{Z} の存在を要求することになる。しかし 0\cdot k=0 はすべての k に対して成り立つため、唯一の可能性は b=0 である。この場合、関係によって「定まる」 k は存在せず、任意の k\in\mathbb{Z} が 0=0\cdot k を満たしてしまう。別の言い方をすれば、非形式的な表現 k=b/a は k=0/0 となり、これは定義されていない。このような退化（商の概念が意味を失う状況）を避けるために、a\neq 0 が要求される。この理由により、関係 0\mid b は有効とはみなされない。
- 一方で、a\mid 0 は a\neq 0 を満たすすべての a\in\mathbb{Z} に対して真である。というのも、k=0 を取れば 0=a\cdot 0 が成り立つからである。
この定義から、今後繰り返し用いる同値性が導かれる。すなわち、a\mid b であるということは、b が a の整数倍全体からなる集合に属することと同値であり、これは b\in a\mathbb{Z} と書ける。ここで a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\} である。この書き方は、可除性が単なる「技巧」ではなく、\mathbb{Z} の中に現れる高度に構造化された部分集合を記述する方法であることを強調している。
可除性の基本的性質
- 反射性: a\mid a.
証明:\begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; }\mathbb{Z}\text{ における乗法の単位元}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; 存在導入 (1)}\\ (3) &\vdash a \mid a &\text{; 可除性の定義 (2)} \\ &\blacksquare & \end{array}
- 推移性: a\mid b かつ b\mid c ならば、a\mid c.
証明:
\begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; 可除性の定義，仮定}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; 可除性の定義，仮定}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; }\exists\text{-圧縮(1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; (3)より}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; (4)より}\\ &\text{量化子内での代数的操作}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; (5)より}\\ &\text{乗法に関する }\mathbb{Z}\text{ の閉性}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; 可除性の定義 (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; }\wedge\text{-除去(7)}\\ &\blacksquare& \end{array}
- 加法および減法との両立性: a\mid b かつ a\mid c ならば、a\mid (b+c) および a\mid (b-c).
証明:\begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; 可除性の定義，仮定}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; 可除性の定義，仮定}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; }\exists\text{-圧縮(1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; (3)より}\\ &\text{量化子内での代数的操作}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; (4)より}\\ &\text{加法に関する }\mathbb{Z}\text{ の閉性}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; 可除性の定義 (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; }\wedge\text{-除去(6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; (3)より}\\ &\text{量化子内での代数的操作}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; (8)より}\\ &\text{減法に関する }\mathbb{Z}\text{ の閉性}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; 可除性の定義 (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; }\wedge\text{-除去(10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{; 結論における }\wedge\text{-導入(7,11) }\\ &\blacksquare& \end{array}
- 積との両立性: a\mid b ならば、すべての c\in\mathbb{Z} に対して a\mid (bc) が成り立つ。
証明:\begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; 可除性の定義，仮定}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; (1)より，}\forall\text{-導入 (}c\text{ 任意)}\\ &\text{存在量化子内での }\mathbb{Z}\text{ の代数的操作}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; (2)より，閉性: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; 可除性の定義 (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; 推論規則(4)}\\ &\blacksquare& \end{array}
定理: 除数の上界
b\neq 0 かつ a\mid b であるならば、|a|\le |b| が成り立つ。
証明:
\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; 仮定} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; 可除性の定義，仮定} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; 絶対値の性質，(2)より} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; (1),(3)より} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; (4)より，}k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; (5)より} \\ &\blacksquare& \end{array}
演習問題
- b=0 の場合、定理「除数の上界」が必ずしも成り立たないことを示せ。
- 集合 A と、その上の関係 \rho を考える。要素 x,y\in A が \rho によって関係付けられているとき、x\rho y と書く。関係 \rho が A 上の半順序であるとは、次を満たすことをいう。
a)(\forall x\in A) (x\rho x),
b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z).可除性の関係が、整数全体の集合上で半順序関係であることを証明せよ。
- a\mid b_1, a\mid b_2, \cdots, a\mid b_n であるならば、任意の集合 \{x_i\}_{i=1}^n \subset \mathbb{Z} に対して a\mid \sum_{i=1}^n b_i x_i が成り立つことを帰納法により証明せよ。さらに、a\mid b_i が i\in \{1,2,3,\cdots, n\} に対して成り立ち、かつ c がそれらの b_i の線形結合として表されるとき、a\mid c が成り立つことを示せ。
- a\neq 0 のとき、集合 \{x\;:\; d\mid a\} が有限集合であることを示せ。
- 固定した n\in\mathbb{Z}^+ に対し，
S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}
とおく。次を証明せよ。
- d\in S \leftrightarrow n/d\in S
- 集合 S の要素を昇順に並べて 1=d_1 \lt d_2 \lt \cdots \lt d_t =n とするとき、対応する要素 n\mid d_i（i \in \{1,2,\cdots, t\}）は降順に並ぶことを示せ。
- a,b\in\mathbb{Z}^+ かつ ab=c とする。このとき \min\{a,b\}\le \sqrt{c} が成り立つことを証明せよ。
- 整数 n が 2\mid n を満たすとき偶数といい、2\nmid n を満たすとき奇数という。次について証明せよ。
- 二つの偶数の和および差は偶数である。
- 二つの奇数の和および差は偶数である。
- 一つの偶数と一つの奇数の和および差は奇数である。
- n が \pm 1 とは異なる奇数であるとき、n は連続する二つの偶数を同時に割り切ることができないことを証明せよ。
- a,b,n\in\mathbb{Z} で |a-b|\lt |n| を満たすとする。このとき n は a も b も割り切ることができないことを証明せよ。
- a\in\mathbb{Z} とする。次を証明せよ。
- (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
- (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
- a,b,c\in\mathbb{Z} で c\neq 0 とする。ac\mid bc ならば a\mid b が成り立つことを示せ。