続いて Week 7 は Number theory: 数論（または整数論とも）についてです。いよいよ数学という数学っぽくなってきました。
講義自体は、YouTube で公開されてます。リンクがこちらにあるので、興味がある人はぜひ。
https://www.youtube.com/watch?v=LN7cCW1rSsI
※ あくまで素人が趣味で防備のノートとしてまとめているだけなので、解釈違い、数学的な厳密さの欠如についてはご容赦ください。
Lecture 9A – Number Theory 1
If you restrict arithmetic to the integers division actually relates to two numbers, a quotient and a remainder.
割り算を分数ではなく、わざわざ「商と余り」で表現していたのは、整数のみに閉じた状態で割り算を表現していたということ。
Division Theorem: Let \( a, b \) integers, \( b \gt 0 \). Then there are unique integers \( q, r \) such that \( a = q \cdot b + r \) and \( 0 \le r \lt b \).
Proof: We prove existence first, then uniqueness.
Existence: Look at all non-negative integers of the form \( a-kb \), where \(k \) is an integer, and show that one of them is less then \( b \).
Such integers do exist. Take \( k = -|a| \). Then, since \( b \ge 1\), ( \( b \gt 0 \ \)より )
\[ a-kb = a + |a| b \ge a + |a| \ge 0 \]
Let \( r \) be the smallest such integer. Let \( q \) be the value of \( k \) for which it occurs, i.e., \( r = a – qb \).
To complete the proof, we show that \( r \lt b \). Suppose, on the contrary, that \( r \ge b \). (proof by contradiction)
Then: \( a – (q + 1) b = a – qb – b = r – b \ge 0 \).
Thus \( a – (q+1)b \) is a non-negative integer of the form \( a – kb \). But \( r \) is the smallest such, and yet \( a – (q+1)b \lt a – qb = r \). Contradition. Hence \( r \lt b \).
That proves existence.
Uniqueness: We show that if there are two representations of \( a\),
\( a = qb + r = q’b + r’ \), where \( 0 \le r, r’ \lt b \),
then \( r = r’ \) and \( q = q’ \).
Rearranging the above equation.
(1) \( r’ – r = b(q – 1′) \)
Taking absolute values in (1):
(2) \( |r’ – r| = b|q – q’| \)
But \( -b \lt -r \le 0 \) and \( 0 \le r’ \lt b \), so \( -b \lt r’ – r \lt b\)
i.e., \( |r’ – r| \lt b \).
So by (2), \( b|q – q’| \lt b \).
Hence, \( |q – q’| \lt 1\). Hence \( q = q’ \). ( \( q, q’ \) は共に整数なので )
Then by (1), \( r = r’ \). That proves uniqueness.
David Hilbert (1862-1943) の Hilbert’s Hotel の話が出てきます。解析学を理解するための重要なキーワード、”infinity” に対する洞察を得るための思考実験です。Hilbert’s paradox of the Grand Hotel
Theorem (General Division Theorem): Let \( a, b\) be integers, \( b \ne 0\). Then there are unique integers \( q, r \) such that \( a = q \cdot b + r \) and \( 0 \le r \lt |b| \).
Proof: We have proved the result in the case \( b \gt 0 \), so assume \( b \lt 0 \).
Then, since \( |b| \gt 0 \), the previous theorem tells us there are unique integers \( q’, r’ \) such that \( a = q’ \cdot |b| + r’ \) and \( 0 \le r’ \lt |b| \).
Let \( q = -q’ \), \( r = r’ \). Then, since \( |b| = -b \), we get
\( \qquad a = q \cdot b + r \), \( 0 \le r \lt |b| \).
The number \( q \) is called the quotient of \( a \) by \( b \), and \( r \) is called the reminders.
Lecture 9B – Number Theory 2
DIVISIBILITY
If division of \( a \) by \( b \) produces a remainder \( r = 0 \), we say \( a \) is divisible by \( b \). Hence, \( a \) is divisible by \( b \) iff there is an integer \( q \) such that \( a = b \cdot q \).
For example, 45 is divisible by 9, but 44 is not divisible by 9.
NOTATION: \( b|a \) denotes \( a \) is divisible by \( b \).
ここで重要なことは、\( b|a \) iff \( \exists q [a = bq] \). であるということ、つまり、\( 9 | 0 \) は、true たりうる。 \( 0 = 0 \cdot b \)であるため。
そして、素数は以下の通りとなる。
A prime number is an integer \( p \gt 1 \) that is divisible only by 1 and \( p \).
また、\( (\forall n \in \mathbb{N}) [n|0] \) は、true となるが、\( (\forall n \in \mathbb{Z}) [n|0] \) は、false であることに注意が必要。\( \mathbb{Z} \) は、整数であり0を含むため。(つまり、0を除く整数、とすれば true でOK)
BASIC PROPERTIES OF DIVISIBILITY
Theorem: let \( a, b, c, d \) be integers, \( a \neq 0 \). Then:
- \( a|0, a|a \)
- \( a|1 \) iff \( a = \pm 1\)
- If \( a|b \) and \( c|d \), then \( ac | bd \) (for \( c \neq 0 \))
- If \( a|b \) and \( b|c \), then \( a|c \) (for \( b\ \neq 0 \))
- [\( a|b \) and \( b|a\) ] iff \( a = \pm b \)
- If \( a|b \) and \( b \neq 0 \), then \( |a| \le |b| \)
- If \( a|b \) and \( a|c \), then \( \ a| (bx + cy) \) for any integers \( x, y \)
FUNDAMENTAL THEOREM OF ARITHMETIC
Theorem: Every natural number greater than 1 is either prime or can be expressed as a product of primes in a way that is unique except for the order in which they are written.
「全ての1より大きい自然数は、素数であるか、または、その順序を問わない素数の積である。」といったような意味合い。
For example: \( 4 = 2 \times 2 = 2^{\ 2} \), \( 6 = 2 \times 3 \), \( 10 = 2 \times 5 \) and so on and so on.
The expression of a number as a product of primes is called its prime decomposition.
The uniqueness proof will require “Euclid’s lemma”: If a prime \( p \) divides a product \( ab \), then \( p \) divides at least one of \( a, b \).
上記のような自然数が「存在し」かつ「一意である」ことをそれぞれ証明する必要がある。
EXISTENCE PROOF (NEW PROOF)
Proof: Existence. Prove it by contradiction. Suppose there were a composite number (i.e., non prime) that could not be written as a product of primes. Then there must be a smallest such number. Call it \( n \). Since \( n \) is not prime, there are numbers \( a, b \) with \( 1 \lt a, b \lt n \) such that \( n = ab \).
If \( a, b \) are primes, then \( n = ab \) is a prime decomposition of \( n \) and we have a contradiction.
このケースでは、そもそも \( n \) を、「素数ではない数の積で表される自然数のうち最小のもの」としているため、「\( a, b \) が共に素数であることは」前提からして矛盾する。
If either of \( a, b \) is composite, then because it is less than \( n \), it must be a product of primes, so by replacing one or both of \( a, b \) by its prime decomposition in \( n = ab \), we get a prime decomposition of \( n \), and again we have a contradiction.
反対にこちらのケースは、「\( a, b \) のうち、少なくとも一方が素数の積である」場合に、\( n \) 自体も素数の積となり、「素数ではない数の積で表される自然数」という前提に矛盾してしまう。
That proves existence.
UNIQUENESS
To prove: The prime decomposition of any natural number \( n \gt 1 \) is unique up to the ordering of the primes.
Proof by contradiction. Assume there is a number \( n \gt 1 \) that has two (or more) different prime decompositions. Let \( n \) be the smallest such number.
Let
(*) \( n = p_1 p_2 … p_r = q_1 q_2 … q_s \)
be two different prime decompositions of \( n \).
Since \( p_1 \) divides \( (q_1)(q_2 … q_s) \), by Euclid’s lemma, either \( p_1 | q_1 \) or \( p_1 | (q_2 … q_s) \).
\( p_1 \) は \( n \) の約数だから、\( n \) と等しい \(q_1 q_2 … q_s \) の約数でもある。
Hence, either \( p_1 = q_1\) or else \( p_1 = q_i \) for some \( i \) between 2 and \( s \).
But then we can delete \( p_1 \) and \( q_i \) from the two decompositions in (*), which gives us a number smaller than \( n \) that has two different prime decompositions, contrary to the choice of \( n \) as the smallest such.
存在に関する証明の際と同様に、「\( n \)は2つ以上の異なる素因数分解の方法をもつ自然数のうち最も小さいもの」であるため、約分してしまうとそれより小さい自然数となってしまう。（＝矛盾する）
And that proves uniqueness.
その他いろいろ
数学的帰納法それ「自体」の証明があり、ちょっと解釈に手間取ったので、その辺りのメモ書き。
Proof: We have to prove that if:
\(\hspace{5mm} A(1) \)
\(\hspace{5mm} (\forall n)[A(n) \Rightarrow A(n+1)] \)
Then \( (\forall n) A(n) \).
We argue by contradiction.
背理法による証明。
Suppose the conclusion is false. Then there will be a natural number \( n \) such that \( \lnot A(n) \).
つまり、\( (\forall n) A(n) \) の否定をとり、\( (\exists n)[\lnot A(n)] \) の仮定について検討するということ。
Let \( m \) be the least such number.
\( m \) を \( \lnot A(n) \) が成り立つ場合の最小の自然数とおく。
By the first condition, \( m \gt 1 \), so \( m = n + 1 \) for some \( n \).
最初の条件である、\( A(1) \) より、 \( m \gt 1 \) となる。
Since \( n \lt m \), \( A(n) \).
\( m \)は、「\( (\exists n)[\lnot A(n)] \) が成り立つ場合の最小の自然数」であったため、それ以下の\( n \)においては、 \( \lnot A(n) \) とはならないということ。 <- ここが重要
つまり、\( A(n) \) が成り立つ。
Then by the second condition, \( A(n+1) \), i.e., \( A(m) \).
そして、\( A(n) \Rightarrow A(n+1) = A(m) \) なので、2つ目の条件である \( (\forall n)[A(n) \Rightarrow A(n+1)] \) とは矛盾してしまう。 なぜなら、\( m \) はそもそも、\( \lnot A(n) \) が成り立つ最小の自然数であると仮定した論理なので。
This is a contradiction, and that proves the result.
The prime decomposition of any natural number \( n \gt 1 \) is unique up to the ordering of the primes.
ここで、”up to” という表現が使われていますが、本来は「〜まで（〜を含んで）」の意味で使われます。ただし、数学の文脈では「〜を除く」という意味で使われるとかなんとか、Wikipedia に載ってるあたり、割とよく使われる用法みたいです。
up to
up to – Cambridge Dictionary
used to say that something is less than or equal to but not more than a stated value, number, or level:
\( b|a \) iff \( a/b \) is an integer. となるが、ここで \( b|a \) は、\( a \) と \( b \) との関係性であり、 \( a/b \) ある数字（有理数）または演算であることに注意。
整数の集合に対する演算には、「加算、減算、乗算」が存在するのみで、「除算」は存在しない。
英語だと、\( b|a \) は、”\( a \) is divisible by \( a \)” または、”\( b \) divides \( a \)” となり、
\( a/b\) は、”\( a \) devided by \( b \)” となって紛らわしい。
まとめ
整数論 と銘打ってはありますが、そこまで極端に難しい内容は扱われていないです。
普段、仕事やら日常生活やらで何気なく行っている四則演算も、改めて見てみると面白い性質があるものです。
「なぜそうなるのか？」を考えるきっかけになる良い Module だったかなと思います。
さて、次の Module は Real Analysis: 実解析、です。どんどん専門的な内容になっていきます。
それでは！ この辺で。
コメント