Some facts about the integers

$(\mathbf{Z}, +)$ is a commutative group. $+$ is associative and commutative. The identity element is $0$ and each element $a$'s inverse is $-a$.
$(\mathbf{Z}, \cdot)$ is a commutative monoid. $\cdot$ is associative and commutative. The identity element is $1$. (No inverses required)
Distributive Law: $a(b+c) = (ab) + (ac), \forall a,b,c \in \mathbf{Z}$. (side note: the list of properties so far for reference imply that $\mathbf{Z}$ is a commutative ring with unit.
$\mathbf{Z} / \{0\}$ is closed under multiplication. In other words, if $a \neq, b \neq 0$, then $ab \neq 0$ We can also re-write this by taking its contrapositive so $ab = 0$ implies that $a = 0$ or $b = 0$.
$\mathbf{N} = \mathbf{Z}_{>0}$ is closed under $+$ and $\cdot$.
If $a, b \in \mathbf{Z} / \{0\}$, then $ |ab| \geq \max\{|a|,|b|\} $. (Note that $a > b$ means that $a - b \in \mathbf{Z}_{>0}$.)

Divisibility

Definition

Let $a, b \in \mathbf{Z}$. $a$ divides $b$ (write $a | b$) if there exists $m \in \mathbf{Z}$ such that $am = b$.
(We also say that $a$ is a factor of $b$ or $b$ is a multiple of $a$).
In fact, $a|b$ if and only if $\frac{b}{a} \in \mathbf{Z} \text{if $a \neq 0$}$.

The factors or divisors of $6$ for example are $\{\pm 1, \pm 2, \pm 3, \pm 6\}$ while the divisors of $0$ are all of $\mathbf{Z}$. We also have the set of all multiplies of integer $a$ so if $a$ is 7, then the set is $\{...,-14,-7,0,7,14,21,...\}$. Notation: we will denote the set of all multiples as

$$ \begin{align*} \mathbf{Z}a = \{na \ | \ n \in \mathbf{Z}\} \end{align*} $$

Divisibility Properties

The following are some well known propositions about divisibility.

If $a | b$ and $b | a$, then $b \in \{\pm a\}$
If $a | 1$, then $a \in \{\pm 1\}$
If $a | b$ and $b | c$, then $a | c$
If $a | b$ and $a | c$, then $a | (b + c)$
If $a | b$ and $a | c$, then $a | (mb + nc) \quad \forall m, n \in \mathbf{Z}$

Note that

$$ \begin{align*} a | b \Leftrightarrow b \in \mathbf{Z}a \Leftrightarrow \mathbf{Z}b \subseteq \mathbf{Z}c \end{align*} $$

Prime Numbers

Definition 1.6.3

A natural number is prime if (i) $n < 1$ and (ii) the only positive divisors of $n$ are $\{1, n\}$.

Proposition 1.6.4

Every $n \in \mathbf{N}$ greater than 1 is equal to a product of primes (at least one).

Proof
By Induction on $n \geq 2$.
Base Case: $n = 2:$ 2 is a prime so it’s a product of one prime.

Inductive Case $n > 2$:
Suppose that inductive hypothesis is true for any number $r$ where $2 \leq r < n$. Now, take $n$. We have two cases. If $n$ is a prime number, then $n$ is a product of primes and we’re done. Otherwise, $n$ is not a prime and has divisors other than $1$ or itself. Let these divisors be $a$ and $b$ so that $n = ab$. $a$ and $b$ are not $n$ or $1$ so we know that $1 < a < n$ and $1 < b < n$. We can now apply the inductive hypothesis to conclude that both $a$ and $b$ can be written as a product of primes. Therefore, $n = ab$ is also a product of primes. $\ \blacksquare$

Theorem 1.6.6 (Euclid)

There are infinitely many prime numbers.

Proof
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 \in \mathbf{N}$. We know that $p$ is greater than any of the primes $p_1,p_2,...,p_k$. Observe now that none of these primes $p_1, p_2,...,p_k$ can divide $p$. Why? because if any of these primes did (say it was $p_i$), then this means that $p_i \ | \ n$. But $p_i$ also divides the product $p_1p_2...p_k$. By the last fact of integers above, then $p_i \ | \ (n - p_1p_2...p_k)$. So $p_i \ | \ 1$. But that’s impossible so $p_i$ can’t divide $n$. But by Proposition 1.6.4, $p$ must be a product of primes. Therefore, there must be another prime or $p$ itself is a prime. This is a contradiction and so we can conclude that there are infinitely many primes. $\ \blacksquare$

Divison with Remainder

The way we learn division is this. Given $a, d \in \mathbf{Z}, d > 0$, then $\frac{a}{d} = q + \frac{r}{d}$. The quotient, $q \in \mathbf{Z}$ and the remainder $r \in \mathbf{Z}$. Moreover, $\frac{r}{d} \in [0,1)$. Stated differently,

Proposition 1.6.7

Given integers $a$ and $d \in \mathbf{Z}$ 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: (from my own notes (reading the book))

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

MATH417 by Charles Rezk
Algebra: Abstract and Concrete by Frederick M. Goodman