\part{Numbers}


\chapter{Types of 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.

\begin{theorem}[Fermat's last theorem]
\[\forall n \in \mathbb{N} \setminus \{0,1,2\} [ \nexists a,b,c \in \mathbb{Z} [ a^n + b^n = c^n ] ]\]
\end{theorem}

Though readers are quite familiar with numbers, we define them for completeness.

\section{Natural numbers}

\begin{definition}
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).

\section{Integers}

\begin{definition}
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}$.


\section{Rational numbers}

Both the natural numbers and integers are closed under multiplication, but we require the rational numbers ensure closure 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{Z} = \{ \frac{a}{b} : a,b \in \mathbb{Z} \} \]
\end{definition}


As readers might know, there are also \emph{irrational numbers}; numbers that can be approximated as close as desired by rational numbers, alas they 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.



\chapter{Integer sequences}

Just like the natural numbers, integers have a straightforward definition but have extremely deep properties. Sometimes we can identify that a certain group of numbers have some special 'pattern' or 'property', while other numbers don't. A sequence is often used as notation to describe such numbers since integers are countable and well ordered.


The $n$th \emph{even number} is every second number starting from $0$
\[ ( 2n )_{n \in \mathbb{N}} \]
\[ (0,2,4,6,8,10,...) \]

The $n$th \emph{odd number} is every second number starting from $1$. The idea is that it captures the numbers that are not even.
\[ ( 2n+1 )_{n \in \mathbb{N}} \]
\[ (1,3,5,7,9,11,...) \]

The $n$th \emph{square number} is the result of squaring $n$
\[ ( n^2 )_{n \in \mathbb{N}} \]
\[ (0,1,4,9,16,25,36,49,64,81,100,... ) \]

Here is a neat little fact about square numbers that I fondly recall stumbling across as a kid (though this proposition was familiar to the ancient Indians).
\begin{proposition}
The sum of the first $n-1$ odd numbers is the $n$th square number.
\[ n^2 = \sum^{n-1}_{k=0} (2k+1)\]
\end{proposition}


The $n$th \emph{triangle number} is a number obtained by adding up the first $n$ numbers.
\[ S_n = \sum^{n}_{k=0} k \]
\[ (0,1,3,6,10,15,21,28,36,45,55,... ) \]


Integer sequences such as these have arisen from curiosity about the integers, however many integer sequences have their origins in enumerative combinatorics; a field of math that studies counting problems. Some 'combinatorial' sequences are studied in a number theory setting, and some 'number theory' sequences are borrowed by combinatorics to calculate a quantity; number theory and combinatorics are quite intimately related. 

Some 'integer sequences' are best interpreted rather as 'arithmetic functions' due to certain behaviours they exhibit when forming arithmetic on them. An entire chapter will be delegated to the study of the integer sequences of number theory (or at least integer sequences that I feel are historically number theoretic) as well as arithmetic functions. Though integer sequences studied in and of themselves find themselves in that chapter, integer sequences will be scattered throughout this book with the concepts they arise from.


Above all, there is one integer sequence that has perpetually fascinated and eluded mathematicians for millennia, and they are perhaps the most elegant and enigmatic class of integers in mathematics entirely. They are no other than the \emph{prime numbers}; though we'll have to develop some theory on divisibility before we can discuss them.


\chapter{Divisibility}


\section{Divisibility}

We define divisibility as the following relation on the integers.

\begin{definition}
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}

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. 

\section{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 \in \mathbb{N} ( \exists! d \in \mathbb{Z}, 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.
\section{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$.


\section{Lowest common multiple}


\begin{definition}
The \emph{lowest common multiple} $\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.
\[\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?


\section{Greatest common factor}

\begin{definition}
	The \emph{greatest common factor (GCF)} or \emph{greatest common divisor (GCD)} $\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$.
\[\gcd(a,b) = \max \{ n \in \mathbb{N} : n|a \land n|b \} \]
\end{definition}



\begin{propostion}
\[ \gcd(a,b) \lcm (a,b) = ab\]
\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.


\section{Euclidean algorithm}

We first develop the theory that Euclid had in mind.
\begin{proposition}
\[ m,n \in \mathbb{Z} \implies \gcd(m,0)=m \land \forall q \in \mathbb{Z} [ \gcd (m,n) = \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}




\section{Bézout's lemma}

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 = \gcd(a,b) ] \]
\end{lemma}





\chapter{Primality}

\section{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.

\section{Euclid's theorem}

We introduce a nice notation that goes particularly well with the theorem that we are about to prove.
\begin{definition}
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$.



\section{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 \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}

\section{Euclid's lemma}



\begin{lemma}[Euclid's lemma]
\[ p \text{ is prime } \land p|ab \implies [ p|b \lor p|a ]  \]
\end{lemma}

One can extend this notion to a numbers coprime to one factor rather than just prime numbers.


\begin{lemma}[Generalized Euclid's lemma]
\[ c|ab \land \gcd(c,a)=1 \implies c|b \]
\end{lemma}


\begin{proposition}
\[ a|a \]
\[ a|b \land b|c \implies a|c\]
\[ a|b \implies an|bn\]
\[ an|bn \land a \neq 0 \implies a|b\]
\[ a,b > \land a|b  \implies a \leq b\]
\end{proposition}

\section{Naive factorization algorithm}

\begin{proposition}
\[ n \text{ is composite } \implies \exists p [ p \text{ is prime} \land p \leq \sqrt{n} ]\]
\end{proposition}

\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}



\section{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.

\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^{n_i} ] ) \]
\end{theorem}

\section{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.

-

- sieve of Eratosthenes
- Fermat prime
- Mersenne prime

\section{Relationship with Riemann zeta function}

Daddy Euler had a strong penchant for infinite products and, like all mathematicians, for prime numbers. This is definitely reflected in his proposition on the Riemann Zeta function factorization.

