Lemma 1

Let $a,b,q, r \in \Z$ such that $a=b\cdot q + r$
Then $\mathrm{gcd}(a,b) = \mathrm{gcd}(b,r)$

Euclid's Algorithm (a, b)

$x = a$
$y = b$
while $y \neq 0$
$r = x \ \mathrm{mod} \ y$
$y = r$
return $x$

Bezout's Theorem

Let $a,b \in \Z^+$.
There exists $s,t \in \Z$ such that:
$s\cdot a + t\cdot b = \mathrm{gcd}(a,b)$

Lemma 2

Let $a,b,c \in \Z^+$
If gcd$(a,b) = 1$ and $a|bc$, then $a|c$

Lemma 3

Let $p$ be a prime number and $a_1, a_2, ..., a_n$ be integers.
If $p|a_1\cdot a_2 \cdot ... \cdot a_n$, then there exists $1 \leq i \leq n$ with $p|a_i$

Theorem

Let $m \geq 2$ be a positive integer and $a,b,c \in \Z$ such that $ac \equiv bc \pmod{m}$ and gcd$(c,m) = 1$.
Then $a\equiv b \pmod{m}$