Definition 1.6.3
A natural number is prime if it is greater than 1 and not divisible by any natural number other than 1 and itself.



Proposition 1.6.4
Any natural number other than 1 can be written as a product of prime numbers.


Proof
By Induction.
Base Case: \(n = 2:\) 2 is a prime number and it is a product of prime numbers (only one factor).

Inductive Case: Suppose that for any number \(r\), we have \(2 \leq r < n\) and \(r\) is a product of prime numbers. Now, take \(n\). We have two cases. If \(n\) is a prime number, then \(n\) is a product of prime numbers and we’re done. Otherwise, \(n\) is not a prime number and we can write \(n\) as a product of two integers \(a\) and \(b\) (\(n = ab\)) such that \(1 < a < n\) and \(1 < b < n\) (by ?). We can now apply the inductive hypothesis to conclude that both \(a\) and \(b\) can be written as a product of prime numbers. There \(n = ab\) is also a product of prime numbers. \(\ \blacksquare\)

Theorem 1.6.6
There are infinitely many prime numbers.


Suppose for the sake of contradiction that there are finitely many primes \(p_1,p_2,...,p_k\). Consider \(p = p_1p_2...p_k + 1\). We know that \(p\) is greater than any of the prime numbers \(p_1,p_2,...,p_k\). By Proposition 1.6.4, we can express \(p\) as a product of prime numbers. Observe now that \(p\) can not be divisible by any of the prime numbers \(p_1, p_2, ..., p_k\) (Why? for any \(p_i\), \(\frac{(p_1p_2...p_k)+1}{p_i} = p_1..p_{i-1}p_{i+1}...p_k + \frac{1}{p_i}\) which is not an integer). Therefore, we must have \(p\) be a prime number. This is a contradiction and therefore, there are infinitely many primes. \(\ \blacksquare\)

Proposition 1.6.7
Given integers \(a\) and \(d\) with \(d \geq 1\), there exists unique integers \(q\) and \(r\) such that $$ \begin{align*} a = qd + r \end{align*} $$ where \(0 \leq r < d\).


Proof
We are given \(a\) and \(d\) such that \(d \geq 1\).
We want to find unique integers \(q\) and \(r\) such that \(r < d\).

We have two cases:
\(a \geq 0\): If \(d > a\), then we just take \(q = 0\) and \(r = a\).
Otherwise, suppose that \(d \leq a\). By Induction on a. Assume that for all non-negative integers smaller than \(a\), we can find such integers. In particular, suppose it holds for \(a - d\), then there exists integers \(q'\) and \(r\) such that

$$ \begin{align*} (a - d) &= q'd + r \quad (\text{where } 0 \leq r < d) \\ a &= q'd + d + r \\ a &= q'(d + 1) + r \end{align*} $$

And we are done.

Case \(a > 0\): If \(a\) is divisible by \(d\), then there exists integer \(q\) such that \(a = qd\). So we can set \(r = 0\) and we are done.
Otherwise, \(-a > 0\) so by the first case (\(a \geq 0\)) there exists integers \(q'\) and \(r'\) such that \(-a = q'd + r'\) with \(0 < r' < d\). So

$$ \begin{align*} -a &= q'd + r' \\ a &= -q'd - r' \\ a &= -q'd - d + d - r' \\ a &= (-q' - 1)d + (d - r') \\ &= (-q' - 1)d + (d - r'). \end{align*} $$

So \(q = (-q' - 1)\) and \(r = d - r'\) with \(0 < d - r' < d\) and we are done.

To show that \(q\) and \(r\) are unique, suppose for the sake of contradiction that they are not. Therefore suppose that \(a = qd + r = q'd + r'\) where \(0 \leq r,r' < d\). Subtracting the equations, we see that

$$ \begin{align*} (q - q')d = r - r' \end{align*} $$

But this means that \(r - r'\) is divisible by d. However \(|r - r'| \leq \max\{r,r'\} < d\), so we must have \(|r - r'| = 0\). This implies that \((q' - q)d = 0\) and so \(q' = q\) as we wanted to show. \(\ \blacksquare\)


References