\part{Fundamentals} \chapter{Numbers} Number theory studies integers, integer functions, and numbers with close relations to integers such as the rational numbers. More specific areas of number theory may look at algebraic numbers and transcendental numbers (algebraic and transcendental number theory), however elementary number theory tends to focus on just integers, possibly rational numbers on occasion. Though readers are quite familiar with numbers, we define them for completeness. \section{Natural numbers} \begin{definition}[Natural numbers] The \emph{natural numbers} are numbers where each number has a successor. The set of natural numbers is denoted $\mathbb{N}$. \[ \mathbb{N} = \{0,1,2,3,4,5,...\} \] \[ \mathbb{N} = \{ n+1 : n \in \mathbb{N} \} \cup \{ 0,1 \} \] \end{definition} The natural numbers are simple enough, yet much can be said about them and there are many unanswered questions related to them. A few neat properties can be seen by breaking the number up into a sum of its ones, tens, hundreds, etc. This is generalized by the \emph{basis representation theorem}. \begin{theorem}[Basis representation theorem] For any natural numbers $n,b$, there is a unique sequence $(d_i)_{i=0}^{k}$ with $d_i < b$that can represent $n$ in the following way. \[ n = \sum^{k}_{i=0} d_i b^i \] \end{theorem} This theorem is responsible for the machinery behind the basic addition algorithm learnt at school; the basis representation theorem with $b=10$ provides the justification to add multidigit numbers by adding ones digits together, tens digits together ans so forth, and borrowing is the necessary remedy when the $d_i \geq b$. One caveat with natural numbers is that subtraction isn't always well defined even though addition is. For example $4-5 \notin \mathbb{N}$. This is because although every number has a successor, not every number has a predecessor ($0$ ruins the fun for us). An important property of natural numbers is that it is 'well-ordered'; any subset of the natural numbers has a least element. This property is crucial in many low-level proofs in number theory. \subsection{Integers} \begin{definition}[Integers] The \emph{integers} are an extension of the natural numbers such that each number also has a predecessor. The set of integers is denoted $\mathbb{Z}$. \[ \mathbb{Z} = \{ ...,-3,-2,-1,0,1,2,3,...\} \] \[ \mathbb{Z} = \{b-a : a,b \in \mathbb{N} \} \] \end{definition} Working with integers, the mathematician can be sure that addition, subtraction, and multiplication are closed in $\mathbb{Z}$. \subsection{Rational numbers} Both the natural numbers and integers are closed under multiplication, but we require the rational numbers ensure closure under division. Although one can minus any 2 integers to produce another integer, one cannot divide any 2 integers to get any type of number we have discussed; the rational numbers are the set of numbers closed under division. \begin{definition} The \emph{rational numbers} are an extension of the integers such that the quotient of two integers is always well defined. The set of rational numbers is denoted $\mathbb{Q}$. \[ \mathbb{Q} = \{ \frac{a}{b} : a,b \in \mathbb{Z} \} \] \end{definition} As readers may know, there are also \emph{irrational numbers}; numbers that can be approximated as close as desired by rational numbers, however cannot be represented as a fraction of two integers. Examples of these are $\sqrt{2}$ and $\pi$; this is described more in Transcendental Number Theory and Real Analysis. \section{Divisibility} We define divisibility as the following relation on the integers. \begin{definition}[Divisibility relation] Given two integers $a,b$, $a$ \emph{divides} $b$ iff $a$ can be multiplied by some integer to obtain $b$. We denote this relation as $a|b$. \[a,b \in \mathbb{Z}\] \[ a | b \iff \exists k \in \mathbb{Z} (ak=b) \] \end{definition} Here are a few basic properties of divisibility. \begin{proposition} \[ a|a \] \[ a|b \land b|c \implies a|c\] \end{proposition} Those familiar with basic order theory may note that this makes $|$ a partial order on $\mathbb{N}$. We can prove many other useful properties of the divisibility relation. \begin{proposition} \[ a|b \implies an|bn\] \[ an|bn \land a \neq 0 \implies a|b\] \[ a,b > 0 \land a|b \implies a \leq b\] \end{proposition} A basic way of classing integers is by their \emph{parity}; whether they're odd or even. This is directly related to a number's divisibility by $2$. An \emph{even number} is a number divisible by 2 \[n \text{ is even } \iff 2|n\] An \emph{odd number} is a number that is not even. \[n \text{ is odd } \iff 2|(n-1)\] The concept of divisibility is familiar from arithmetic, but a rigorous treatment of our arithmetic intuitions is vital to proving higher theorems. \emph{Euclid's division lemma} will be our first step in this vain. \subsection{Euclid's division lemma} We can decompose any number with respect to another number in the following way. \begin{lemma}[Euclid's division lemma] Every natural number $n$ can be represented with a unique $d$ and a unique $r$ less than $d$ in the following manner. \[ n= dq+r\] \[ \forall n,d \in \mathbb{N} [ \exists! r \in \mathbb{N} \cap [0,d) [ n =qd+r ] ]\] \end{lemma} Although basic, it is a strong tool that proves useful in much of elementary and algebraic number theory. \subsection{Multiples and factors} \begin{definition} A \emph{multiple} of $a$ is some integer that $a$ divides; an integer that equals $a$ multiplied by some integer. \[m \text{ is a multiple of } a \iff a | m\] \end{definition} Given an integer $n$, there are an infinite amount of multiples of $n$ since one can just multiply $n$ by anything to construct a new multiple. This means $n$ goes into infinitely many numbers, the smallest of which (ignoring negative multiples) is $n$ itself. $n$ may have infinite multiples, but what can we say about the nnumbers that $n$ is a multiple \emph{of}? This leads us to a new concept of \emph{divisors}. \begin{definition} A \emph{factor} or \emph{divisor} of $a$ is some integer that divides $a$; an integer that can 'go into' $a$ with no remainder. \[d \text{ is a factor of } a \iff d | a \] \end{definition} Unlike multiples, a number $n$ has a finite amount of divisors; the largest being $n$ itself and the smallest being $1$. \subsection{Lowest common multiple} \begin{definition} The \emph{lowest common multiple} $\mathrm{lcm} : \mathbb{Z}^2 \to \mathbb{N}$ is a function of two elements $a,b$ that returns the smallest number that both $a$ and $b$ divide. \[\mathrm{lcm}(a,b) = \min\{ n \in \mathbb{N} : a|n \land b|n \} \] \end{definition} The idea of an LCM is useful in problems where one wants to see where two methods of incrementing first reach an identical point. For example, if store A sells strawberries in lots of 6 and store B sells strawberries in lots of 8, what is the minimum amount of strawberries that one can obtain by going to either store? \subsection{Greatest common factor} \begin{definition} The \emph{greatest common factor (GCF)} or \emph{greatest common divisor (GCD)} $\mathrm{gcd} : \mathbb{Z}^2 \to \mathbb{N}$ is a function of two elements $a,b$ that returns the largest number that divides both $a$ and $b$. \[\mathrm{gcd}(a,b) = \max \{ n \in \mathbb{N} : n|a \land n|b \} \] \end{definition} \begin{proposition} \[ \mathrm{gcd}(a,b) \mathrm{lcm} (a,b) = ab\] \end{proposition} \begin{proposition} \[ \mathrm{gcd}(a,\mathrm{lcm}(b,c)) = \mathrm{lcm}(\mathrm{gcd}(a,b) , \mathrm{gcd}(a,c)) \] \end{proposition} Note that if you extend this function to contain more than 2 values this proposition does not hold. This is because if you consider $a,b,c$, there may be factors that $b,c$ have in common that aren't shared with $a$, excluding it from the GCD. \subsection{Euclidean algorithm} There exists a particularly efficient algorithm to calculate the GCD of 2 numbers that was known by the ancient Greek, particularly Euclid. The Euclidean algorithm does this by first applying Euclid's divison lemma, noticing that for any $\mathrm{gcd}(a,b)$ where by loss of generality $a \leq b$, we equivalently have some $\mathrm{gcd}(a,da+r)$ for some $d\in \mathbb{Z}$ and some $r \in [0,a) \cap \mathbb{Z}$. Since any factor of $a$ is a factor of $da$, our GCD must also be a factor of $r$, so $\mathrm{gcd}(a,da+r)=\mathrm{gcd}(a,r)$. The idea is that for each iteration of this process the problem is reduced to a simpler GCD calculation that yields an identical answer. Being that mathematics can be seen as a body of theorems, Euclid's algorithm not only facilitates calculations but may be employed in proofs, being a steeping stone in one's intuition about numbers. Let's develop the theory that Euclid had in mind. \begin{proposition} \[ m,n \in \mathbb{Z} \implies \mathrm{gcd}(m,0)=m \land \forall q \in \mathbb{Z} [ \mathrm{gcd} (m,n) = \mathrm{gcd} (m-qn,n) ] \] \end{proposition} \begin{algorithm} \begin{algorithmic} \STATE $m \gets \max(a,b)$ \STATE $n \gets \min(a,b)$ \WHILE{$ m \% n > 0$} \STATE $v \gets m$ \STATE $m \gets n $ \STATE $n \gets v \% n$ \ENDWHILE \STATE $d \gets n$ \end{algorithmic} \end{algorithm} Though the previous proposition is often used as motivation for this efficient algorithm, we can also use the proposition elsewhere in number theory to prove various things. By pairing the Euclidean algorithm proposition with induction one can prove the following \begin{proposition} \[ [\forall c\in \mathbb{Z} [ c|a \land c|b \implies c|d ] ] \iff d = \mathrm{gcd}(a,b) \] \end{proposition} This proposition can also be proven using more advanced tools like Euclid's lemma, the fundamental theorem of arithmetic or \emph{Bézout's lemma}. The fundamental theorem of arithmetic is traditionally proven by Euclid's lemma, and Euclid's lemma is proven by Bézout's lemma in modern times. Indeed, Bézout's lemma tends to be a useful tool for streamlining elementary proofs in number theory. \subsection{Bézout's lemma} Bézout's lemma is highly related to a process called the extended Euclidean algorithm. At the end of this algorithm one is left with an equation which is the key inspiration (and indeed the proof) for Bézout's lemma. There is also an extension of the Euclidean algorithm used to find solutions of the equation This identity follows from the extended Euclidean algorithm and will prove vital in our analysis of coprimality. It is also important in abstract algebra, where they classify algebraic structures on whether this identity holds. \begin{lemma}[Bézout's lemma] \[ \exists x,y \in \mathbb{Z} [ ax+by = \mathrm{gcd}(a,b) ] \] \end{lemma} There are 4 main approaches to proving Bézout's lemma \begin{itemize} \item \emph{Constructive approach}; Performing extended Euclidean algorithm \item \emph{Well-ordering approach}; Proving that the smallest RHS divides any other RHS, and that the RHS divides and is divided $\mathrm{gcd}(a,b)$ \item \emph{Inductive approach}; Consider induction with the Euclidean algorithm \item \emph{Ring theoretic approach}; Prove that $J=\{d : ax+by=d , x,y \in \mathbb{Z}\}$ is a nontrivial integral ideal of $\mathbb{Z}$, then similarly show that all elements of this ideal divides and is divided $\mathrm{gcd}(a,b)$ \end{itemize} That fourth approach uses the machinery of ring theory to do the exact same thing as that second approach, and the second approach operates on the same basis (Euclidean algorithm) of the first approach. Bézout's lemma will be useful when we study modular arithmetic; it will be used to tell us when an MMI exists for an element (we will define this later). \section{Primality} \subsection{Prime numbers} Prime numbers lie not just in the heard of number theory, but in the heart of a mathematician. This book will provide only an elementary insight into their properties, however resorting to the likes of modern algebra and complex analysis allows for some seriously gourmet proofs. \begin{definition} A natural number greater than 1 is a \emph{prime number} iff it is divisible only by 1 and itself. \[ n \in \mathbb{N} \setminus \{0,1\} \text{ is prime } \iff \{d \in \mathbb{N} : d | n \}=\{1,n\}\] A natural number greater than 1 is a \emph{composite number} iff it is not prime. \end{definition} Here we have yet another definition that is easy to understand, but bears consequences beyond even the richest of imaginations. This chapter will analyze prime numbers using elementary algebra and the results on integers and divisibility established earlier, however as we progress into modular arithmetic, we will draw upon some deeper reasoning (basic group theory sugar coated by elementary methods) to get a hold of some more interesting results. Though riveting stuff awaits when we add a bit of 'algebraic magic', studying prime numbers in an elementary setting is by no means boring. We shall demonstrate the original proof of Euclid's theorem; often hailed as one of the most elegant proofs in mathematics. \subsection{Euclid's theorem} We introduce a nice notation that goes particularly well with the theorem that we are about to prove. \begin{definition}[Primorial] The \emph{primorial} is a function returning the product of the first $n$ prime numbers. \[ n\# = \prod_{i=1}^{n} p_{i}\] \end{definition} \begin{theorem}[Euclid's theorem] There are an infinite amount of prime numbers; for any prime number, there is a larger prime number. \[ p \text{ is prime} \implies \exists q ( q \text{ is prime } \land q > p)\] \end{theorem} Assume $p$ is the $n$th prime number and consider $n\#+1$. $n\#+1$ is not divisible by any of the first $n$ primes. If $n\#+1$ is either prime itself, we are done. If it is not prime, them it must be divisible by a prime number larger than $p$. \subsection{Pair of coprime numbers} \begin{definition} A \emph{pair of coprime numbers} are a pair of integers $a,b$ such that ther GFC is $1$. \[(a,b) \text{ are coprime } \iff \mathrm{gcd}(a,b)=1\] \end{definition} In other words, a pair of coprime numbers $(a,b)$ share no factor in common. This weakens the property of being prime; where all pairs $(p,a)$ where $a < p$ share no common factor. There is much that can be said about this relationship between numbers, and it will be particularly prevalent in our study of arithmetic functions. By the Euclidean algorithm, if $n,q$ are coprime, then so are $n,n-q$. This simple fact was used by me to prove a lemma for a girl I liked. \begin{lemma}[Sofia's lemma] \[ S(n) = \{ q \in \mathbb{N} \cap[1,n-1] : \mathrm{gcd}(n,q)=1 \} \] \[ \forall n \in \mathbb{N} \setminus \{0,1,2\} [ n | \sum_{s \in S(n)} s ] \] \end{lemma} \subsection{Euclid's lemma} A lemma that characterizes an important property of prime numbers. Prime numbers are 'prime' in the sense that they cannnot be factored any further, they are also 'prime' in the sense that cannot be a factor of the product of 2 numbers without already being a factor of one of these numbers. \begin{lemma}[Euclid's lemma] \[ p \text{ is prime } \land p|ab \implies [ p|b \lor p|a ] \] \end{lemma} Digging deeper, this result is really due to coprimality of the divisor rather than primality; indeed \emph{generalized Euclid's lemma} reflects this. Euclid's lemma follows as a corollary of this more general result since prime numbers are coprime to every integer below itself. \begin{lemma}[Generalized Euclid's lemma] \[ n|ab \land \gcd(n,a)=1 \implies n|b \] \end{lemma} One way to prove this is by using the Eudlidean algorithm result with induction. Another way is by setting up a contradiction by considering a set of integers where the theorem doesn't hold and then use the minimal element of this set to trigger the contradiction. Euclid's original proof was based on interpreting $n|ab$ as $nm=ab$ as $\frac{n}{a} = \frac{b}{m}$, noticing that since $\frac{n}{a}$ is in lowest terms due to their coprimality, $b$ is a multiple of $n$ (i.e $n|b$). This is all well and good, however he required much theory in his previous propositions to prove that this final observation is legal. In modern mathematics the conventional way to prove generalized Euclid's lemma is as a corollary of Bézout's lemma; since $\mathrm{gcd}(a,n)=1$, Bézout's lemma claims a solution of $x,y$ to $ax+ny=1$. From this we have $b=abx+ny$. Since $n|abx+ny$ (the right hand side), we must also have $n|b$ (the left hand side), proving the lemma. Euclid's lemma captures a key intuition on primality (and coprimality), and is a key fact used in the even more powerful \emph{fundamental theorem of arithmetic}. \subsection{Fundamental theorem of arithmetic} Now that suficient theory on prime numbers and their basic properties have been established, it is time to introduce perhaps the most powerful tool in number theory. It is perhaps an intuitive fact, but nonetheless central in understanding the nature of numbers. We now introduce the \emph{fundamental theorem of arithmetic}. This theorem is named as such because 'arithmetic' was the old name for number theory; Gauss preferred the word 'higher arithmetic' for number theory. \begin{theorem}[Fundamental theorem of arithmetic] For any natural number greater than 1, there exists a unique representation of that number $n$ as a product of prime powers. \[ \forall n \in \mathbb{N} \setminus \{0,1\} ( \exists! (n_i)_{i=1}^{k} [ n = \prod^{k}_{i=1} p_i^{e_i} ] ) \] \end{theorem} The existence of any number being representable by products of prime powers is generally proven by induction. Here's an intuitive interpretation; assume the theorem holds for all integers up to $n-1$, to prove for $n$ we consider if it is prime or composite. If $n$ is prime, we are done. If $n$ is composite, it has two factors both less than $n$ that can be represented as products of prime powers. So the proof is recursive in nature and our inductive hypothesis 'breaks' the recursion. This result is among the most powerful in number theory, and it revolutionizes the way we view numbers. \subsubsection{Counting factors} Pairing the FTA with some basic combinatorics gives us a way to count the amount of factors a number has. \begin{proposition} Let $n=\prod^{k}_{i=1}p_{i}^{e_i}$, then $n$ has $\prod^{k}_{i=1}(e_i +1)$ factors. \end{proposition} Here's a quick example; Consider the number 420, we know tht $420=2^{2} \cdot 5\cdot 7 \cdot 3 \cdot 2$, so 420 has $3\cdot 2 \cdot 2 \cdot 2 \cdot 2=48$ factors. How convenient a little combinatorics can be! \subsubsection{Applications to GCD and LCM} \begin{proposition} Let $n=\prod^{k}_{i=1}p_{i}^{e_i} \prod^{l}_{i=1}q_{i}^{f_i}$ and $m=\prod^{k}_{i=1}p_{i}^{g_i} \prod^{j}_{i=1}r_{i}^{h_i}$ where $q_i \neq r_j$ for any $i,j \in \mathbb{Z}$ \[\mathrm{gcd}(n,m) = \prod^{k}_{i=1}p_{i}^{\min (e_i, g_i)}\] \end{proposition} \subsection{Naive factorization algorithm} Though the fundamental theorem of arithmetic ensures the existence of some unique product of prime powers for each number, there is no notably efficient algorithm to calculate this representation. There is, however, an ancient algorithm called the \emph{sieve of Eratosthenes} that can calculate the unique prime factorization of a number, even if it is not very efficient. \begin{proposition}[Sieve of Eratosthenes] \[ n \text{ is composite } \implies \exists p \in \mathbb{N} \cap [1,n) [ p|n \land p \text{ is prime} \land p \leq \sqrt{n} ]\] \end{proposition} The main takeaway from the sieve of Eratosthenes is that instead of checking to see that no number preceding it divides $n$, we can restrict our attention to primes, and better yet, ones less than or equal to $\sqrt{n}$. FTA offers all the justification for the correctness of this sieve; since every number is a product of primes, any compositve number must have a prime as its factor. Any prime whose square is greater than $n$ (so $p^2 > n$) cannot have $p$ as its sole prime factor since any repeated multiplication of $p$ leaves us with a number greater than $n$; if $p$ is a factor of $n$ then there must be some other, smaller prime factor that we can check. Therefore we require that $p^2 \leq n$, or equivalently $p \leq \sqrt{n}$. This result permits a much more efficient algorithm for checking primality than blindly checking for some nontrivial divisor, and the ancient Greeks made use of it. A concrete algorithm for the sieve of Eratosthenes is as follows. \begin{algorithm} \begin{algorithmic} \STATE $D \gets \{ n \}$ \WHILE{$ \exists d \in D ( d \text{ is composite} )$} \FOR{$ a \in \mathbb{N} \cap [2,\sqrt{d}]$} \IF{$a|d$} \STATE $D \gets D \setminus \{d\}$ \STATE $D \gets D \sqcup \{a, \frac{d}{a} \}$ \STATE \textbf{break} \ENDIF \ENDFOR \ENDWHILE \end{algorithmic} \end{algorithm} \subsection{Types of prime numbers} Some mathematicians have restricted their study to prime numbers of a certain forms. The reason for this is because mathematicians seek to understand how primality interacts with other mathematical properties, in hopes of finding interesting results. For instance, numbers of the form $2^n -1$ have some properties that permit relatively efficient algorithms for checking their primalities. \subsubsection{Fermat prime} \subsubsection{Mersenne prime} \begin{definition}[Mersenne number] \[M_n = 2^n -1\] \end{definition} \begin{definition}[Mersenne prime] A \emph{Mersenne prime} is a Mersenne number that is prime. \end{definition} Mersenne primes are of high interest to number theorists attempting to find large prime numbers since they are related to a corpus of useful results. The first of which being a necessary condition for a Mersenne number to be a Mersenne prime. \begin{proposition} \[ M_n \text{ is prime } \implies n \text{ is prime } \] \end{proposition} This instantly rules out many Mersenne numbers from being Mersenne primes; now all that is required is an efficient primality test for Mersenne numbers with prime exponents. \begin{theorem}[Lucas-Lehmer primality test] \end{theorem} This result provides the basis for the algorithm of the \emph{Lucas-Lehmer primality test}. This algorithm finds use in GIMPS (Great Internet Mersenne Prime Search); a project that seeks to use distributed computing to record Mersenne prime numbers, the largest at the time of writing being $M_{136279841}$ (18/02/2026). There are many unanswered questions relating to Mersenne primes; it is unknown whether or not Mersenne primes are infinite in multitude. The Lenstra-Pomerance- Wagstaff conjecture supposes that there are infinite and that the number of Mersenne primes less than $x$ is asymptotic to $e^{\gamma$}\log_2 (\log_2 (x))$.