1.2 Notation and Well-Ordered Property
Let’s write \(\mathbb {N} = \{ 0, 1, 2,\ldots \} \) for the set of natural numbers and \(\mathbb {P} = \{ 1,2,3,\ldots \} \) for the set of positive natural numbers. Write \(\mathbb {Z}\) for the set of all integers.
If \(a\) and \(b\) are integers, we write \(a|b\) and say that \(a\) divides \(b\) if there exists an integer \(c\) such that \(b = ac\). If \(a | b\), then \(a\) is called a divisor of \(b\), and \(b\) is called a multiple of \(a\).
Suppose \(a\), \(b\), \(c\), \(x\) and \(y\) are all integers.
If \(a | b\) and \(b | c\), then \(a | c\).
If \(a | b\) and \(a | c\), then \(a | (xa + yb)\).
Exercise.
Any nonempty subset \(S\) of \(\mathbb {P}\) has a smallest element.
As Gallian points out in his text, Axiom 1.3 is pretty much equivalent to the principle of mathematical induction.
A prime number is a positive integer \(p\), which has exactly two positive divisors. An integer \(n {\gt} 1\), which is not prime is said to be composite.
Suppose \(n\in \mathbb {P}\).
\(n\) is prime if and only if it has exactly two positive divisors. Moreover, when \(n\) is prime, the two positive divisors are exactly \(1\) and \(n\) itself.
\(n\) is composite if and only there exist positive integers \(a\) and \(b\), both less than \(n\), such that \(n = ab\).
Exercise.
Let’s say that a prime factorization of an integer \(n\in \mathbb {P}\) is a list \([p_1,p_2,\ldots , p_r]\) of prime numbers such that
\(p_1\le p_2 \le \cdots \le p_r\), and
\(n = p_1\ldots p_r\).
We allow the empty list \([]\) of prime numbers with the convention that the product of the empty list is \(1\). Under this convention, \(1\) has a prime factorization (it’s just empty).
We say that a positive integer \(n\) has a unique prime factorization if any two prime factorizations of \(n\) are equal. Explicitly, this means that, if \([p_1,\ldots , p_r]\) and \([q_1,\ldots , q_s]\) are both prime factorizations of \(n\), then \(r = s\) and \(p_i = q_i\) for all \(i = 1,\ldots , r\).
Finally, note that if \([p_1,\ldots , p_r]\) is any list of primes satisfying 2 above, we can sort it to get a list of primes satisfying 1 as well. We’ll do that below (possibly sometimes without even mentioning it).