Introduction to Cryptography with Coding Theory, 3rd Edition

3.1 Basic Notions

3.1.1 Divisibility

Number theory is concerned with the properties of the integers. One of the most important is divisibility.

Definition

Let $a$ and $b$ be integers with $a\ne 0\text{.}$ We say that $a$ divides $b\text{,}$ if there is an integer $k$ such that $b=ak\text{.}$ This is denoted by $a|b\text{.}$ Another way to express this is that $b$ is a multiple of $a\text{.}$

Example

$3|15\text{,}$ $-15|60\text{,}$ $7\nmid 18$ (does not divide).

The following properties of divisibility are useful.

Proposition

Let $a\text{,}b\text{,}c$ represent integers.

1. For every $a\ne 0\text{,}$ $a|0$ and $a|a\text{.}$ Also, $1|b$ for every $b\text{.}$

2. If $a|b$ and $b|c\text{,}$ then $a|c\text{.}$

3. If $a|b$ and $a|c\text{,}$ then $a|(sb+tc)$ for all integers $s$ and $t\text{.}$

Proof. Since $0=a\cdot 0\text{,}$ we may take $k=0$ in the definition to obtain $a|0\text{.}$ Since $a=a\cdot 1\text{,}$ we take $k=1$ to prove $a|a\text{.}$ Since $b=1\cdot b\text{,}$