Basic results

1. Well-ordering property:

Every non-empty subset of non-negative integers has a minimum value i.e. a value that is strictly lesser than every other value.

If $s$ objects are distributed into $k$ boxes, where $s > k$, then at least one box contains more than one object.

If $P$ is a set of integers such that…

$a$ is in $P$
$\forall \text{ } k \in \mathbb{Z}$ where $k \geq a$, if $k$ is in $P$, then $k+1$ is also in $P$

… then $P$ contains all integers greater than or equal to $a$, i.e. $P = {x \in \mathbb{Z} : x \geq a}$.

Define $a \mod b$ as the remainder of $\frac{a}{b}$. Then:

$xy \mod z = ((x \mod z)(y \mod z)) \mod z$

Hence, by extension, for a positive integer k:

$x^k \mod y = (x \mod y)^k \mod y$