Definition

Let $a$ and $b$ be two integers such that $a \neq 0$. We say that $a$ divides $b$ if there exists an integer $c$ such that $b= ac$ If $a$ divides $b$, we say that $a$ is a factor or a divisor of $b$. We can say also that $b$ is a multiple of $a$.

Notation: $a|b$ means $a$ divides $b$. $a \nmid b$ means $a$ does not divide $b$

Theorem 1

Let $a,b,c \in \Z$ with $a \neq 0$.

1. If $a|b$ and $a|c$ then $a|(b+c)$
2. If $a|b$, then $a|bc$ for every integer $c$
3. If $a|b$, and $b|c$, then $a|c$.

Proof

Prove if $a|b$ and $a|c$ then $a|(b+c)$:

Let $a,b,c \in \Z$ with $a \neq 0$. Assume that $a|b$ and $a|c$. Then we have:

$b = as$ for some integer $s$,
$c = at$ for some integer $t$

Thus we have:
$b + c = as+at = a(s+t)$,

in other words $a|(b+c)$.

Corollary

Let $a,b,c \in \Z$ with $a \neq 0$. If $a|b$ and $a|c$ then $a|(mb+nc)$ for all integers $m$ and $n$.

Theorem 2 - Division Algorithm

Let $a,d \in \Z$ with $d > 0$. There exists unique integers $q$ and $r$ such that:

• $0 \leq a < d$
• and $a = dq + r$

We write:

1. $q = a \ div \ d$
2. $r = a\bmod\ d$

Definition - Modulus

Let $a,b,m \in \Z$ with $m \geq 2$. We say that $a$ is congruent to $b$ modulo $m$ is $m|(a-b)$. We write $a \equiv b \pmod{m}$.

Theorem 3

Let $a,b,c,d,m \in \Z$ with $m \geq 2$. If $a \equiv b (mod m)$ and $c \equiv d (mod m)$, then

1. $a+c \equiv b+d\pmod{m}$
2. $ac \equiv bd\pmod{m}$

Arithmetic Modulo

Let $m\geq 2$ be an integer and $\Z_m = {0,1,2,...,m-1}$.

We define

• $a + \ _mb = (a+b) \pmod{m}$
• $a\cdot \ _mb = (a\cdot b) \pmod{m}$

This structure satisfies several properties: Closure, Associativity, Commutativity, Identity elements, Additive & Multiplicative inverses, Distributivity