Divisibility and Modular Arithmetic

Divisibility

Definition Divisibility Relationships

We say that an integer $b$ divides an integer $a$ if there exists an integer $k$ such that:$$a = kb.$$We write $b\mid a$.
We can also use the following formulations:

$b$ is a divisor of $a$,
$b$ is a factor of $a$,
$a$ is a multiple of $b$.

Example

Consider the numbers $10$ and $5$.
Since we can write $\textcolor{olive}{10} = \textcolor{colorprop}{2}\times \textcolor{colordef}{5}$, we can say that:

$\textcolor{colordef}{5}$ divides $\textcolor{olive}{10}$,
$\textcolor{colordef}{5}$ is a divisor (or factor) of $\textcolor{olive}{10}$,
$\textcolor{olive}{10}$ is divisible by $\textcolor{colordef}{5}$,
$\textcolor{olive}{10}$ is a multiple of $\textcolor{colordef}{5}$.

Notes

Let $a$ and $b$ be two integers.

$1$ divides every integer $a$ because $a=1\times a$ (hence $1\mid a$).
If $a$ is a multiple of $b$ and $a\neq 0$, then $|a|\ge |b|$.
If $a$ divides $b$ and $b$ divides $a$, with $a\neq 0$ and $b\neq 0$, then $a=b$ or $a=-b$.

Proposition Linear combinations

Let $a,b,c$ be integers.
If $a\mid b$ and $a\mid c$, then for all integers $m$ and $n$,$$a \mid (mb+nc).$$

Proof

Suppose $a \mid b$ and $a \mid c$.
By definition, there exist integers $k$ and $\ell$ such that$$b = ka \quad \text{and} \quad c = \ell a.$$Now let $m$ and $n$ be any integers. We consider the linear combination $mb + nc$:$$\begin{aligned}mb + nc &= m(ka) + n(\ell a) \\ &= (mk + n\ell)a.\end{aligned}$$Since $m,k,n,\ell$ are integers, the term $(mk+n\ell)$ is an integer.
Therefore, by definition, $a$ divides $mb+nc$.

Euclidean Division (Division with Remainder)

Theorem Euclidean Division

Given any two integers $\textcolor{olive}{a}$ and $\textcolor{colordef}{b}$ with $\textcolor{colordef}{b}>0$, there exist unique integers $\textcolor{colorprop}{q}$ and $\textcolor{orange}{r}$ such that$$\textcolor{olive}{a}=\textcolor{colordef}{b}\,\textcolor{colorprop}{q}+\textcolor{orange}{r}\quad\text{and}\quad0\le \textcolor{orange}{r}<\textcolor{colordef}{b}.$$

$\textcolor{olive}{a}$ is the $\textcolor{olive}{\text{dividend}}$,
$\textcolor{colordef}{b}$ is the $\textcolor{colordef}{\text{divisor}}$,
$\textcolor{colorprop}{q}$ is the $\textcolor{colorprop}{\text{quotient}}$,
$\textcolor{orange}{r}$ is the $\textcolor{orange}{\text{remainder}}$.

Proof

This proof models sharing through repeated subtraction.
Consider the following algorithm for $\textcolor{olive}{a}\in\mathbb{N}$ and $\textcolor{colordef}{b}\in\mathbb{N}^*$:

Initialization: Set $\textcolor{orange}{r}=\textcolor{olive}{a}$ and $\textcolor{colorprop}{q}=0$.
Loop: While $\textcolor{orange}{r}\ge \textcolor{colordef}{b}$ do: $$ \textcolor{orange}{r}\leftarrow \textcolor{orange}{r}-\textcolor{colordef}{b} \quad\text{and}\quad \textcolor{colorprop}{q}\leftarrow \textcolor{colorprop}{q}+1. $$

Termination: Since $\textcolor{colordef}{b}>0$, $\textcolor{orange}{r}$ decreases at each step and remains non-negative. It eventually reaches $\textcolor{orange}{r}<\textcolor{colordef}{b}$ in finite time.
Invariant: The relation $\textcolor{olive}{a}=\textcolor{colordef}{b}\textcolor{colorprop}{q}+\textcolor{orange}{r}$ is preserved at each iteration. Upon termination, we have $0\le \textcolor{orange}{r}<\textcolor{colordef}{b}$.
Uniqueness: If $\textcolor{olive}{a}=\textcolor{colordef}{b}q+r=\textcolor{colordef}{b}q'+r'$ with $0\le r,r'<\textcolor{colordef}{b}$, then $\textcolor{colordef}{b}(q-q')=r'-r$. The right-hand side satisfies $-(\textcolor{colordef}{b}-1)\le r'-r\le \textcolor{colordef}{b}-1$, so the only multiple of $\textcolor{colordef}{b}$ in this range is $0$. Hence $r=r'$ and $q=q'$.

Example

$$\begin{array}{ccccccccl} \textcolor{olive}{13} &=& \textcolor{colordef}{3} & \times & \textcolor{colorprop}{4} & + & \textcolor{orange}{1} & \text{with} & 0 \leq \textcolor{orange}{1} < \textcolor{colordef}{3} \\ \textcolor{olive}{\text{Dividend}} &=& \textcolor{colordef}{\text{Divisor}} & \times & \textcolor{colorprop}{\text{Quotient}} & + & \textcolor{orange}{\text{Remainder}} & \text{with} & 0 \leq\textcolor{orange}{\text{Remainder}} < \textcolor{colordef}{\text{Divisor}}\end{array}$$

Method Check divisibility

To check whether an integer $a$ is divisible by a positive integer $b$, perform the Euclidean division of $a$ by $b$.

If the remainder is zero, then $a$ is divisible by $b$.
If the remainder is not zero, then $a$ is not divisible by $b$.

Example

Is $13$ divisible by $5$?

Answer

We perform the Euclidean division of $13$ by $5$:$$\textcolor{olive}{13}=\textcolor{colordef}{5}\times \textcolor{colorprop}{2}+\textcolor{orange}{3}.$$The remainder is $\textcolor{orange}{3}$ (which is not zero). Therefore, $\textcolor{olive}{13}$ is not divisible by $\textcolor{colordef}{5}$.

Congruences

Definition Congruent Integers

Let $n$ be an integer ($n \ge 2$).
Two integers $a$ and $b$ are said to be congruent modulo $n$ if their difference $a-b$ is divisible by $n$.
We write: $a \equiv b \pmod{n}$, or sometimes $a \equiv b \ (n)$, or $a \equiv b \ [n]$.

Proposition Same Remainder Property

Two integers $a$ and $b$ are congruent modulo $n$ if and only if $a$ and $b$ have the same remainder in the Euclidean division by $n$.

Proof

Let$$a = nq_1 + r_1\quad \text{and}\quad b = nq_2 + r_2$$be the Euclidean divisions of $a$ and $b$ by $n$, with $0 \le r_1, r_2 < n$.

If $r_1 = r_2$, then $$ a-b = (nq_1 + r_1) - (nq_2 + r_2) = n(q_1-q_2), $$ so $n\mid (a-b)$ and thus $a \equiv b \pmod{n}$.
Conversely, if $a \equiv b \pmod{n}$, then $n\mid (a-b)$. But $$ a-b = n(q_1-q_2) + (r_1-r_2), $$ hence $n\mid (r_1-r_2)$. Since $-n < r_1-r_2 < n$, the only multiple of $n$ in this range is $0$. Therefore $r_1-r_2=0$, so $r_1=r_2$.

Example

Prove that $57 \equiv 15 \pmod{7}$.

Answer

Method 1 (Remainders): $57 = 7\times 8 + 1$ (remainder $1$) and $15 = 7\times 2 + 1$ (remainder $1$). Since they have the same remainder, $57 \equiv 15 \pmod{7}$.
Method 2 (Difference): $57-15 = 42 = 7\times 6$. Since the difference is a multiple of $7$, $57 \equiv 15 \pmod{7}$.

Proposition Congruence to the Remainder

An integer is congruent to its remainder in the Euclidean division by $n$.

Proof

Let $a = nq + r$ be the Euclidean division of $a$ by $n$.
Then $a-r = nq$. Since $nq$ is a multiple of $n$, we have $n\mid (a-r)$, hence $a \equiv r \pmod{n}$.

Example

As $2019 = 201\times 10 + 9$, we have $2019 \equiv 9 \pmod{10}$.

Proposition Equivalence Relation

Congruence modulo $n$ is an equivalence relation, which means that for any integers $a, b,$ and $c$:

$a \equiv a \pmod{n}$ (reflexivity),
$a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}$ (symmetry),
$a \equiv b \pmod{n}$ and $b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n}$ (transitivity).

Proof

$a-a=0$, and $0$ is divisible by any $n\ge 2$. So $a \equiv a \pmod{n}$.
If $a \equiv b \pmod{n}$, then $a-b=kn$ for some integer $k$. Hence $b-a=(-k)n$, so $b \equiv a \pmod{n}$.
If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a-b=kn$ and $b-c=mn$ for some integers $k,m$. Summing gives $$ (a-b)+(b-c)=kn+mn \implies a-c=(k+m)n, $$ so $a \equiv c \pmod{n}$.

Example

If $x \equiv y \pmod{5}$ and $y \equiv 12 \pmod{5}$, then $x \equiv 12 \pmod{5}$. Since $12 = 5\times 2 + 2$, we can further say $x \equiv 2 \pmod{5}$.