自然数：まとめと挑戦課題

要約

この課は、自然数を扱う単元を締めくくる。集合の言語とペアノの公理から二項定理に至る演繹の鎖を再構成し、各環でどの原理が使われ、どの結果が得られるかを示す。また、達成したことをコースの計画のなかに位置づけ、自然数どうしの減法と除法の限界がなぜ、数の集合を扱う次の単元へ導くのかを説明する。最後に、各課の問題より難しく、いくつもの課の道具を組み合わせることを求める十の挑戦課題を置く。

学習目標

単元の結果の論理的な順序を再構成し、それぞれが依拠する原理を特定する。
帰納法、整列性、余りのある割り算、素因数分解の一意性、合同式がどのように関係しているかを説明する。
自然数どうしの減法と除法の限界から出発して、数の集合を拡張する必要性を正当化する。
帰納法、整除性、位取り記数法、数え上げを組み合わせる問題を解く。

単元で達成したこと

この単元は、少数の原理から自然数の算術を導き、その性質のどれも自明なものとして認めないことを目指した。この目的は、それぞれその場所で明示した少数の留保のもとで果たされた。その留保とは、ほかのすべてを書き表す言語である素朴集合論と量化子の否定の規則、デデキントの再帰定理が保証し、集合論に属するという理由で認めた、再帰によって定義される関数の存在、数え上げの土台である、有限集合の要素の個数の一意性とその部分集合の有限性、有限個の積の因数を並べ替えることを許す一般化された交換法則、そして、この単元が例題と問題で先取りし、次の単元が構成する整数・有理数・実数の初等的な規則である。これらの留保のもとで、たどってきた道筋は四つの区間からなる一本の演繹の鎖として読むことができる。

基礎：集合、公理、演算、順序

集合、関係、写像の課は、単元を書き表す言語を定め、集合論から認めるわずかなことを明示したうえで、同値関係と分割が一つの考えの二つの面であることを証明した。すなわち、同値関係の同値類は分割をなし、どの分割もただ一つの同値関係から生じる。この結果は、余りによる整数の分類と合同式に再び現れ、次の単元はこれを用いて整数と有理数を対の同値類として構成する。ペアノの公理の課では、自然数を $1$ 、後者をとる演算、五つの公理によって定義した。第二から第四の公理は列が止まらず自分自身に戻らないことを保証し、第五の公理である数学的帰納法の原理は、 $1$ から出発して到達できる自然数のほかに自然数がないことを保証する。基本的な演算と順序の課は、再帰定理を用いて、後者の上に再帰的定義のはしごを組み立てた。そこでは各演算が一つ前の演算によって定義される：

n + S(m) = S(n + m), \qquad n \cdot S(m) = n \cdot m + n, \qquad b^{S(n)} = b^n \cdot b

これらの定義から、帰納法によって交換法則、結合法則、分配法則、簡約法則を導き、加法から順序を、三分律、推移律、単調性とともに得た。減法と除法は逆演算として定義したが、それはある場合に限られる。 $a - b$ が存在するのは $b < a$ のときであり、 $\frac{a}{b}$ が存在するのは $b$ が $a$ を割り切るときである。

証明の原理

総和・数列・帰納法の課は、証明の手立てを広げた。通常の帰納法が累積帰納法と整列原理を導くこと、そして、 $1$ と異なる自然数はどれもある数の後者であるという補題と順序の性質を用いれば、逆に整列性が帰納法を導くことを証明した。こうして、どの証明も自分にとって最も自然な原理を用いることができる。また、和に再帰的な定義と計算を可能にする性質を与え、望遠鏡和によって、公式は確かめるだけでなく導くこともできることを示した。整列原理は、その後のほとんどすべての存在証明の道具となった。集合の最小の要素を選び、最小反例によって推論することを可能にするからである。

整除の算術

整列性を用いて、整除の課は、どの整数も自然数で割ると、ただ一つの商とただ一つの余りをもつことを証明した。この定理に、以下の四つの結果が依存しており、それぞれが前の結果に支えられている：

場合分けによる証明を可能にする、余りによる整数の分類と、倍数判定法。後者は、 $d$ の倍数だけ異なる二つの数が、 $d$ で割ったときに同じ余りを残すという事実に帰着する。
素数の課では、整列性と余りのある割り算によって証明したユークリッドの補題と、それに基づく算術の基本定理。すなわち、 $1$ より大きいどの自然数も、ただ一通りに素数の積になる。一意性から、約数の個数、平方数の特徴づけ、割り切れない根の無理性を導いた。
最大公約数の課では、余りのある割り算を尽きるまで繰り返すユークリッドの互除法、そこから導かれるベズーの等式、一次不定方程式の完全な解法。
合同式の課では、それまでのすべてを計算に変えたこと。 $n$ を法とする合同は、加法と乗法と両立する同値関係であり、その同値類が $\mathbb{Z}_n$ をなす。ベズーの等式は、どの余りが可逆か、一次合同式がいつ解をもつかを決め、中国剰余定理を与える。そしてユークリッドの補題は、逆元とあわせてフェルマーの小定理を与える。

書き表すことと数え上げ

位取り記数法の課は、余りのある割り算を何度も用いて、どの自然数もどの底でもただ一通りに書けることを証明し、それによって、どの底においても計算の手順と倍数判定法を正当化した。組合せ論と二項定理の課は出発点に戻った。数えることこそ、自然数が生まれた演算だからである。全単射による要素の個数の定義から証明した和の法則と積の法則（後者は前者から帰納法で証明した）は、二項係数、パスカルの法則、二項定理へと導いた。二項定理の証明は、帰納法、総和記号、数え上げを一つにまとめる。

次の図は、四つの区間を一本の鎖にまとめたものである。列の各節点は定義か定理で、論理的な順序で番号が付き、その証明が用いる前の環と弧で結ばれている。そのまわりに浮かぶのが支え、すなわち鎖が何度も立ち返る原理と道具であり、それぞれは、よりかかる環と実線で、確立される環と点線で結ばれる。ただし、証明なしに認めるものは輪として描かれる。支えを押すと、それを使うすべての環が強調され、各環はそれが証明される課へのリンクになっている。

鎖の支え

A数学的帰納法の原理. ある性質が $1$ について成り立ち、任意の自然数 $k$ について成り立つと仮定するとその後者 $S(k)$ についても成り立つならば、その性質はすべての自然数について成り立つ。確立される環: 2. ペアノの公理.
B再帰定理. $1$ における値と、 $S(n)$ における値を与える規則（ $n$ における値から求めるもの）を定めると、それらを満たす自然数上の関数がただ一つ存在する。加法、乗法、累乗、総和、階乗はこのようにして定義される。存在は認め、一意性は帰納法で証明する。この単元では証明なしに認める。
C累積帰納法. ある性質が $1$ について成り立つこと、そして $1$ から $n$ までのすべての自然数について成り立つと仮定すると $n + 1$ についても成り立つことを証明すれば十分である。確立される環: 9. 累積帰納法.
D整列性. 自然数からなる空でない集合はどれも最小の要素をもち、これによって最小反例による推論が可能になる。確立される環: 10. 整列原理.
E余りのある割り算. 任意の整数 $a$ と任意の自然数 $b$ に対して、ただ一つの商 $q$ とただ一つの余り $r$ が存在して、 $a = bq + r$ かつ $0 \leq r < b$ となる。確立される環: 12. 余りのある割り算.
F一次結合. 整数 $d$ が整数 $a$ と $b$ を割り切るならば、それは $ax + by$ を割り切る。ただし $x$ と $y$ は任意の整数である。特に、それらの和と差を割り切る。確立される環: 11. 整除の性質.
G先取りした数. 整数・有理数・実数の計算と順序の初等的な規則（符号、簡約、分数、根）は、この単元では証明なしに先取りして用いる。それらの構成は次の単元の内容である。この単元では証明なしに認める。
H要素の個数. $\{1, \ldots, n\}$ との間に全単射が存在する集合は $n$ 個の要素をもつ。この数がただ一つであること、有限集合の部分集合が有限であることは認める。この単元では証明なしに認める。

第 1 区間基礎：集合、公理、演算、順序
- 集合、関係、写像の言語を定め、同値関係と分割が互いに対応することを証明する。
- 自然数を、 $1$ と後者から出発して、ペアノの五つの公理によって定義する。
- 後者の上に再帰的定義のはしごを組み立てる。加法、乗法、累乗である。
- 交換法則、結合法則、分配法則、簡約法則を帰納法で導く。
- 加法から順序を、三分律、推移律、単調性とともに得て、差と商がいつ存在するかを明らかにする。
1. 同値関係と分割. 集合上の同値関係の同値類はその集合の分割をなし、どの分割もただ一つの同値関係の同値類全体の集合である。
  証明される授業: 集合・関係・関数.
2. ペアノの公理. 自然数は $1$ から後者によって生成される。 $1$ はどの数の後者でもなく、異なる自然数は異なる後者をもち、 $1$ と自分の各要素の後者を含む集合はどれも、すべての自然数を含む。
  証明される授業: 自然数とペアノの公理.
3. 再帰的な加法. $n + 1 = S(n)$ と $n + S(m) = S(n + m)$ によって定義される加法は、可換で結合的であり、簡約法則を満たす。
  使う結果: 2. ペアノの公理. 支え: A (数学的帰納法の原理), B (再帰定理). 証明される授業: 自然数の基本演算と順序関係.
4. 乗法と累乗. $n \cdot 1 = n$ と $n \cdot S(m) = n \cdot m + n$ によって定義される乗法は、可換、結合的、分配的で、簡約法則を満たし、累乗は $b^n b^m = b^{n + m}$ 、 $(b^n)^m = b^{nm}$ 、 $(ab)^n = a^n b^n$ を満たす。
  使う結果: 3. 再帰的な加法. 支え: A (数学的帰納法の原理), B (再帰定理). 証明される授業: 自然数の基本演算と順序関係.
5. 順序、減法、除法. $a < b$ が $a + k = b$ を意味するとき（ $k$ はある自然数）、二つの自然数の間には $a < b$ 、 $a = b$ 、 $b < a$ の関係のうちちょうど一つが成り立ち、順序は推移的で、加法と乗法によって保たれる。差 $a - b$ が存在するのは $b < a$ のときに限り、商 $\frac{a}{b}$ が存在するのは $b$ が $a$ を割り切るときに限る。どちらも簡約法則によってただ一つである。
  使う結果: 2. ペアノの公理, 3. 再帰的な加法, 4. 乗法と累乗. 支え: A (数学的帰納法の原理). 証明される授業: 自然数の基本演算と順序関係.
第 2 区間証明の原理
- 通常の帰納法、累積帰納法、整列原理が同値であることを証明する。
- 総和を再帰的に定義し、その性質を導く。
- 公式を、確かめるだけでなく、望遠鏡和によって導く。
- 等差数列と等比数列の和を求める。
1. ある自然数からの帰納法. $n_0$ について成り立ち、各自然数 $k \geq n_0$ から $k + 1$ へ受け継がれる性質は、すべての自然数 $n \geq n_0$ について成り立つ。
  使う結果: 5. 順序、減法、除法. 支え: A (数学的帰納法の原理). 証明される授業: 総和・数列・帰納法.
2. 総和と望遠鏡和. 再帰的に定義された総和は線形であり、連続する和に分けることができ、添字のずらしと順序の反転が許される。連続する値の差の和は、最後の値から最初の値を引いたものに等しい： $\sum_{k=1}^{n} (b_{k + 1} - b_k) = b_{n + 1} - b_1$ 。
  使う結果: 4. 乗法と累乗, 6. ある自然数からの帰納法. 支え: A (数学的帰納法の原理), B (再帰定理). 証明される授業: 総和・数列・帰納法.
3. 等差数列と等比数列. 等差数列の $n$ 項の和は $\frac{n(a_1 + a_n)}{2}$ であり、初項 $a$ 、公比 $r \neq 1$ の等比数列の和は $a \cdot \frac{r^n - 1}{r - 1}$ である。
  使う結果: 7. 総和と望遠鏡和. 支え: A (数学的帰納法の原理), G (先取りした数). 証明される授業: 総和・数列・帰納法.
4. 累積帰納法. ある性質が $1$ について成り立ち、 $1$ から $n$ までのすべての自然数について成り立つと仮定すると $n + 1$ についても成り立つならば、その性質はすべての自然数について成り立つ。
  使う結果: 6. ある自然数からの帰納法. 支え: A (数学的帰納法の原理). 証明される授業: 総和・数列・帰納法.
5. 整列原理. 少なくとも一つの要素をもつ自然数の集合はどれも最小の要素をもつ。 $1$ と異なる自然数はどれもある数の後者であるという補題と順序の性質を用いると、逆に整列性が帰納法を導き、三つの原理は同値になる。
  使う結果: 5. 順序、減法、除法. 支え: C (累積帰納法). 証明される授業: 総和・数列・帰納法.
第 3 区間整除の算術
- 整列性によって商と余りの存在と一意性を証明する。
- 整数を余りによって分類し、それに基づいて倍数判定法を根拠づける。
- 素数が無限にあること、ユークリッドの補題、素因数分解の一意性を、それらの帰結とともに証明する。
- ユークリッドの互除法で最大公約数を計算し、そこからベズーの等式を導き、一次不定方程式を解く。
- 合同式で計算し、どの余りが可逆かを判定し、一次合同式と、互いに素な法をもつ連立合同式を解き、フェルマーの小定理を証明する。
1. 整除の性質. 整数の間の整除関係は反射的かつ推移的であり、整数 $a > 0$ の約数は $-a$ と $a$ の間にあり、 $d$ が $a$ と $b$ を割り切るならば、どの結合 $ax + by$ も割り切る。
  使う結果: 5. 順序、減法、除法. 支え: G (先取りした数). 証明される授業: 整除と余りのある割り算.
2. 余りのある割り算. 任意の整数 $a$ と任意の自然数 $b$ に対して、ただ一つの商 $q$ とただ一つの余り $r$ が存在して、 $a = bq + r$ かつ $0 \leq r < b$ となる。
  支え: D (整列性), G (先取りした数). 証明される授業: 整除と余りのある割り算.
3. 余りと判定法. 二つの整数が $d$ で割ったときに同じ余りを残すのは、その差が $d$ の倍数であるとき、かつそのときに限る。ここから和、積、累乗の余りが求まり、 $3$ 、 $9$ 、 $11$ の倍数判定法が得られる。
  支え: A (数学的帰納法の原理), E (余りのある割り算), F (一次結合). 証明される授業: 整除と余りのある割り算.
4. 素因数と無限性. どの自然数 $n > 1$ も素因数をもち、 $n$ が合成数ならば、その最小の素因数 $p$ は $p^2 \leq n$ を満たす。ここから、どの有限のリストもすべての素数を含みはしないことが従う。
  使う結果: 5. 順序、減法、除法, 11. 整除の性質. 支え: D (整列性), F (一次結合). 証明される授業: 素数と算術の基本定理.
5. ユークリッドの補題. 素数が積 $ab$ を割り切るならば、 $a$ を割り切るか $b$ を割り切る。また、いくつかの因数の積を割り切るならば、そのうちのどれかを割り切る。
  支え: A (数学的帰納法の原理), D (整列性), E (余りのある割り算), F (一次結合). 証明される授業: 素数と算術の基本定理.
6. 算術の基本定理. どの自然数 $n > 1$ も素数の積であり、その分解は因数の順序を除いてただ一通りである。
  使う結果: 4. 乗法と累乗, 15. ユークリッドの補題. 支え: D (整列性). 証明される授業: 素数と算術の基本定理.
7. 約数と無理数の根. $n = p_1^{e_1} \cdots p_k^{e_k}$ ならば、その約数は数 $p_1^{f_1} \cdots p_k^{f_k}$ （ただし $0 \leq f_i \leq e_i$ ）であり、その個数は $(e_1 + 1) \cdots (e_k + 1)$ である。自然数 $n > 1$ が完全な $k$ 乗数であるのは、その分解のすべての指数が $k$ の倍数であるとき、かつそのときに限る。そうでなければ、自然数 $a$ と $b$ で $a^k = n b^k$ となるものは存在しない。すなわち、その $k$ 乗根は無理数である。
  使う結果: 15. ユークリッドの補題, 16. 算術の基本定理. 支え: A (数学的帰納法の原理), G (先取りした数). 証明される授業: 素数と算術の基本定理.
8. ユークリッドの互除法. $a = bq + r$ ならば、組 $a, b$ と組 $b, r$ は同じ公約数をもつ。したがって、 $\operatorname{gcd}(a, b)$ は、続けて行う割り算の最後の 0 でない余りである。
  支え: D (整列性), E (余りのある割り算), F (一次結合). 証明される授業: 最大公約数と最小公倍数.
9. ベズーの等式. 整数 $x$ と $y$ で $ax + by = \operatorname{gcd}(a, b)$ となるものが存在し、最大公約数は、この形に書ける最小の自然数である。
  使う結果: 18. ユークリッドの互除法. 支え: A (数学的帰納法の原理), F (一次結合), G (先取りした数). 証明される授業: 最大公約数と最小公倍数.
10. 最大公約数と最小公倍数の積. $\operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = ab$ が成り立ち、 $a$ と $b$ のどの公倍数も、それらの最小公倍数の倍数である。
  使う結果: 4. 乗法と累乗, 16. 算術の基本定理, 17. 約数と無理数の根. 支え: D (整列性), E (余りのある割り算), F (一次結合). 証明される授業: 最大公約数と最小公倍数.
11. 不定方程式. 方程式 $ax + by = c$ が整数解をもつのは、 $d = \operatorname{gcd}(a, b)$ が $c$ を割り切るとき、かつそのときに限り、そのときすべての解は $x = x_0 + \frac{b}{d} t$ と $y = y_0 - \frac{a}{d} t$ である。ただし $t$ は整数である。
  使う結果: 19. ベズーの等式, 20. 最大公約数と最小公倍数の積. 支え: F (一次結合), G (先取りした数). 証明される授業: 最大公約数と最小公倍数.
12. 合同と余り. 二つの整数が $n$ を法として合同であるのは、 $n$ で割ったときに同じ余りを残すとき、かつそのときに限る。合同は加法と乗法と両立する同値関係であり、その $n$ 個の同値類、すなわち余り $0, 1, \ldots, n - 1$ の類が $\mathbb{Z}_n$ をなす。
  使う結果: 1. 同値関係と分割, 13. 余りと判定法. 支え: E (余りのある割り算), F (一次結合). 証明される授業: 合同式とモジュラ算術.
13. 可逆な余り. 整数 $a$ が $n$ を法とする逆元をもつのは $\operatorname{gcd}(a, n) = 1$ のとき、かつそのときに限り、そのとき逆元は $n$ を法としてただ一つである。合同式 $ax \equiv b \pmod{n}$ が解をもつのは $d = \operatorname{gcd}(a, n)$ が $b$ を割り切るとき、かつそのときに限り、そのとき解は $d$ 個ある（ $n$ を法として）。
  使う結果: 22. 合同と余り, 19. ベズーの等式, 21. 不定方程式. 支え: F (一次結合). 証明される授業: 合同式とモジュラ算術.
14. 中国剰余定理. 自然数 $m$ と $n$ が互いに素ならば、 $x \equiv a \pmod{m}$ と $x \equiv b \pmod{n}$ からなる連立合同式は解をもち、その解は $mn$ を法としてただ一つである。
  使う結果: 22. 合同と余り, 19. ベズーの等式, 20. 最大公約数と最小公倍数の積. 支え: G (先取りした数). 証明される授業: 合同式とモジュラ算術.
15. フェルマーの小定理. $p$ が素数で整数 $a$ を割り切らないならば、 $a^{p - 1} \equiv 1 \pmod{p}$ である。また、任意の整数 $a$ について $a^p \equiv a \pmod{p}$ である。
  使う結果: 22. 合同と余り, 15. ユークリッドの補題, 23. 可逆な余り. 証明される授業: 合同式とモジュラ算術.
第 4 区間書き表すことと数え上げ
- どの自然数もどの底でもただ一通りに書けることを証明する。
- どの底においても、筆算による足し算と倍数判定法を正当化する。
- 和の法則と積の法則で数え、それらから二項係数とパスカルの法則を得る。
- 帰納法、総和記号、数え上げを一つにまとめる二項定理を証明する。
1. 位取りによる表し方. どの底 $b \geq 2$ についても、どの自然数もただ一通りに $a_k b^k + \cdots + a_1 b + a_0$ の形に書ける。ただし数字は $0$ から $b - 1$ までで、 $a_k \neq 0$ である。
  支え: C (累積帰納法), D (整列性), E (余りのある割り算). 証明される授業: 位取り記数法.
2. どの底でも成り立つ計算と判定法. 筆算による足し算は和の表し方を与える。また、底 $b$ では、数は $b - 1$ で割ると各位の数の和と同じ余りを残し、 $b + 1$ で割ると交代和と同じ余りを残す。
  使う結果: 7. 総和と望遠鏡和, 13. 余りと判定法, 26. 位取りによる表し方. 支え: A (数学的帰納法の原理), E (余りのある割り算). 証明される授業: 位取り記数法.
3. 数え上げの原理. 共通の要素をもたない二つの集合で、要素がそれぞれ $m$ 個と $n$ 個のものの和集合は、 $m + n$ 個の要素をもつ。また、二段階の選択で、それぞれ $m$ 通りと $n$ 通りのものは、 $mn$ 通りで行える。
  使う結果: 3. 再帰的な加法, 4. 乗法と累乗, 5. 順序、減法、除法. 支え: A (数学的帰納法の原理), H (要素の個数). 証明される授業: 初等的な組合せ論と二項定理.
4. 二項係数とパスカルの法則. $n$ 個の要素からなる集合は $\binom{n}{k} = \frac{n!}{k!\,(n - k)!}$ 個の部分集合（要素 $k$ 個のもの）をもつ。 $\binom{n + 1}{k} = \binom{n}{k - 1} + \binom{n}{k}$ が成り立ち、ここから係数はパスカルの三角形をなし、第 $n$ 行の和は $2^n$ である。
  使う結果: 28. 数え上げの原理. 支え: B (再帰定理), H (要素の個数). 証明される授業: 初等的な組合せ論と二項定理.
5. 二項定理. すべての数 $x$ と $y$ （自然数、あるいは次の単元を先取りして実数）と、すべての自然数 $n$ について、 $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n - k} y^k$ が成り立つ。
  使う結果: 7. 総和と望遠鏡和, 29. 二項係数とパスカルの法則. 支え: A (数学的帰納法の原理), G (先取りした数). 証明される授業: 初等的な組合せ論と二項定理.

数の集合へ. 鎖は、自然数では足りなくなるところで止まる。減法と除法はある場合にしか存在せず、方程式 $x^2 = n$ は、 $n$ が平方数でないとき有理数の解をもたない。次の単元は、これを補うために自然数を拡張する。