# 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{,}\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{,}\text{}$ $-15|60\text{,}\text{}$ $7\nmid 18$ (does not divide).

The following properties of divisibility are useful.

# Proposition

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

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

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

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

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

Get *Introduction to Cryptography with Coding Theory, 3rd Edition* now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.