Integer Divisibility

Definition 1. If $a$ and $b$ are integers such that $a \neq 0$, then we say "$a$ divides $b$" if there exists an integer $k$ such that $b=ka$. If $a$ divides $b$, we also say "$a$ is a factor of $b$" or "$b$ is a multiple of $a$" and we write $a | b$. If $a$ doesn't divide $b$, we write a / b. For example 2|4.

Example:

1. Note that any even integer has the form $2k$ for some integer $k$, while any odd integer has the form $2k+1$ for some integer $k$. Thus $2|n$ if $n$ is even, while $2n$ if $n$ is odd.
2. Every a in $Z$ one has that $a|0$.
3. If $b$ in $Z$ is such that $|b| < a$, and $b \neq 0$, then a /   b .

Theorem 1. If $a$, $b$ and $c$ are integers such that $a | b$ and $b | c$, then $a | c$.

Proof.
Since $a | b$ and $b | c$, then there exist integers $k_1$ and $k_2$ such that $b = k_1a$ and $c = k_2b$. As a result, we have $c = k_1k_2a$ and hence $a | c$.

Example.
Since 6 | 18 and 18 | 36, then 6 | 36.

The following theorem states that if an integer divides two other integers then it divides any linear combination of these integers.

Theorem 2. If $a$, $b$, $c$, $m$ and $n$ are integers, and if $c | a$  and $c | b$, then $c | (ma + nb)$.

Proof.
Since $c | a$ and $c | b$, then by definition there exists $k_1$ and $k_2$  such that $a = k_1c$ and $b = k_2c$. Thus $ma + nb = mk_1c + nk_2c = c(mk_1 + nk_2)$, and hence c | (ma + nb).

Share :