Introduction#
Some sets, structures, and the well-ordering principle#
Some sets#
\( \begin{aligned} \mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \} && \text{the set of integers} \\ \mathbb{P} = \{ 1, 2, \dots \} && \text{the set of positive integers} \\ \mathbb{N} = \mathbb{P} \cup \{ 0 \} = \{ 0, 1, 2, \dots \} && \text{the set of natural numbers (nonnegative integers)} \\ \mathbb{Q} = \left\{ \frac{p}{q} \mid p, q \in \mathbb{Z}, q \ne 0 \right\} && \text{the set of rational numbers} \end{aligned} \)
\(\{ \mathbb{Z}, +, \cdot, \le \}\) The set of integers under the arithmetical operations of addition and multiplication, and the binary order relation less-than-or-equal-to \(\le\) on the set \(\mathbb{Z}\).
Well-Ordering Principle#
Well-Ordering Principle [Humphreys & Prest]
Any non-empty set \(X \subseteq \mathbb{P}\) of positive integers has a smallest element (i.e., an element that is less than or equal to every member of the set \(X\)).
In other words, we have a set \(X\) of positive integers which, for some reason, we know is non-empty (i.e., it contains at least one element). Then the well-ordering principle guarantees a least element \(k\) of \(X\).
Equivalently, there is no unending strictly-decreasing sequence of positive integers.
Extended Integers#
An extended integer has the form
\(m + n\sqrt{10}\)
where \(m\) and \(n\) are ordinary integers.
Extended Integer Addition
Extended Integer Subtraction
Extended Integer Multiplication
Extended Integer Division
\( \begin{aligned} \frac{a + b\sqrt{10}}{m + n\sqrt{10}} &= \frac{a + b\sqrt{10}}{m + n\sqrt{10}} \times \frac{m - n\sqrt{10}}{m - n\sqrt{10}} \\ &= \frac{a \times m - 10b \times n + (b \times m - a \times n) \sqrt{10}}{m^2 - 10n^2} \\ \end{aligned} \)
\(m + n\sqrt{10}\) is a divisor of \(a + b\sqrt{10}\) iff their ratio is another extended integer.
\( \begin{aligned} 2 + \sqrt{10} \mid 12 + 3\sqrt{10} \leftrightarrow & \frac{12 + 3\sqrt{10}}{2 + \sqrt{10}} = 1 + \sqrt{10} \end{aligned} \)
Indivisible Extended Numbers are not primes because they do not satisfy Theorem 1.1.
[EXAMPLE]
Show that the extended integer \(2\) is not prime according to Theorem 1.1.
Let \(4 + \sqrt{10}\) and \(4 - \sqrt{10}\) be extended integers.
\((4 + \sqrt{10}) \times (4 - \sqrt{10}) = 6\)
\(2 \mid 6 = 3\)
Theorem 1.1 says
\(p \mid ab \rightarrow (p \mid a \lor p \mid b)\)
However
\( (2 \nmid 4 + \sqrt{10}) \land (2 \nmid 4 - \sqrt{10}) \)
Therefore, the extended integer \(2\) is not prime.
More first-order statements#
Lagrange’s Theorem#
Every natural number is the sum of four squares.
Acknowledgements#
Bressoud, David M. (1989). Factorization and Primality Testing. Springer Undergraduate Texts in Mathematics.
Crandall, Richard & Carl Pomerance. (2005). Prime Numbers: A Computational Perspective. Springer.
Davenport, Harold. (2008). The Higher Arithmetic: An Introduction to the Theory of Numbers. Cambridge University Press.
Humphreys, J. F. & M. Y. Prest. (2008). Numbers, Groups, and Codes. 2nd Ed. Cambridge University Press.
LeVeque, William J. (1996). Fundamentals of Number Theory. Dover.
[ h ] Vaughan, Robert. (2023). A Course of Elementary Number Theory. CMPSC/MATH 467 Factorization and Primality Testing. The Pennsylvania State University.
Wagstaff Jr., Samuel S. (2013). The Joy of Factoring. AMS Student Mathematical Library.