Divisibility

Divisibility is the true starting point of number theory because it turns the integers into a structured system: numbers are no longer viewed merely as “quantities”, but as elements that either fit together or do not. With a single relation, $a\mid b$ , it is possible to express everything from simplification and factorization criteria to the core of certain procedures such as the Euclidean algorithm, which makes it possible to compute greatest common divisors in seconds even for large numbers. Moreover, it constitutes the technical foundation of ideas that appear repeatedly in applied mathematics and computation: congruences, modular arithmetic, validations, codes, and, later on, cryptography. Mastering divisibility is, in essence, learning to detect invisible patterns within the integers and to transform them into procedures that always work.

Learning Objectives
At the end of this set of notes, the student will be able to:

Understand the divisibility relation between integers.
Understand the definition of divisibility and its properties.
Develop mathematical proofs of results and theorems related to divisibility.

TABLE OF CONTENTS
Definition of divisibility
Fundamental properties of divisibility
Proposed Exercises

Definition of divisibility

The informal idea of “a divides b” becomes precise when it is expressed as a relation between integers. We say that an integer $a$ divides an integer $b$ if $b$ can be written as an exact multiple of $a$ . This definition is the basis of the rest of these notes, because it transforms phrases such as “fits exactly” into a verifiable criterion.

Definition. Let $a,b\in\mathbb{Z}$ with $a\neq 0$ . We say that $a$ divides $b$ , and we write $a\mid b$ , if and only if there exists an integer $k\in\mathbb{Z}$ such that $b=ka$ . Otherwise, we write $a\nmid b$ .

$a\mid b := (\exists k \in \mathbb{Z})(b = ka )$

In this definition, the number $k$ is called the quotient (or factor) associated with the divisibility. For example, stating $6\mid 42$ is equivalent to stating that there exists $k\in\mathbb{Z}$ such that $42=6k$ ; in this case, it suffices to take $k=7$ .

It is important to consider

The condition $a\neq 0$ is essential. If we attempted to allow $a=0$ , the divisibility condition would require the existence of $k\in\mathbb{Z}$ such that $b=0\cdot k$ . However, $0\cdot k=0$ for all $k$ , so the only possibility would be $b=0$ . In that case, there would be no $k$ “determined” by the relation, since any $k\in\mathbb{Z}$ satisfies $0=0\cdot k$ . In other words, the informal expression $k=b/a$ becomes $k=0/0$ , which is undefined. To avoid this degeneration, in which the notion of quotient ceases to be meaningful, the condition $a\neq 0$ is imposed. For this reason, the relation $0\mid b$ is not considered valid.
By contrast, $a\mid 0$ is true for all $a\in\mathbb{Z}$ with $a\neq 0$ , because it suffices to take $k=0$ , and the equality $0=a\cdot 0$ holds.

From this definition, an equivalence follows that we will use repeatedly: stating that $a\mid b$ is the same as stating that $b$ belongs to the set of integer multiples of $a$ , that is, $b\in a\mathbb{Z}$ , where $a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}$ . This way of writing emphasizes that divisibility is not a “trick”, but rather a way of describing highly structured subsets within $\mathbb{Z}$ .

Fundamental properties of divisibility

Reflexivity: $a\mid a$ .
Proof:
$\begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; Multiplicative identity in $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; Existential introduction (1)}\\ (3) &\vdash a \mid a &\text{; Definition of divisibility (2)} \\ &\blacksquare & \end{array}$
Transitivity: if $a\mid b$ and $b\mid c$ , then $a\mid c$ .
Proof:
$\begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; Definition of divisibility, Assumption}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; Definition of divisibility, Assumption}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-Compaction(1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; From(3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; From(4)}\\ &\text{Algebra within the quantifier}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; From(5)}\\ &\text{Closure of $\mathbb{Z}$ under multiplication}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; Definition of divisibility (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-ED(7)}\\ &\blacksquare& \end{array}$
Compatibility with addition and subtraction: if $a\mid b$ and $a\mid c$ , then $a\mid (b+c)$ and $a\mid (b-c)$ .
Proof:
$\begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; Definition of divisibility, Assumption}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; Definition of divisibility, Assumption}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-Compaction(1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; From(3)}\\ &\text{Algebra within the quantifier.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; From(4)}\\ &\text{Closure of $\mathbb{Z}$ under addition.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; Definition of divisibility (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-ED(6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; From(3)}\\ &\text{Algebra within the quantifier.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; From(8)}\\ &\text{Closure of $\mathbb{Z}$ under subtraction.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; Definition of divisibility (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-ED(10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{;$\wedge$-Introduction in the consequent(7,11) }\\ &\blacksquare& \end{array}$
Compatibility with products: if $a\mid b$ , then $a\mid (bc)$ for all $c\in\mathbb{Z}$ .
Proof:
$\begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; Definition of divisibility, Assumption}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; From(1), $\forall$-Introduction (arbitrary c)}\\ &\text{Algebra in }\mathbb{Z}\text{ within the existential quantifier.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; From(2), closure: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; Definition of divisibility (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; ED(4)}\\ &\blacksquare& \end{array}$

Theorem: bound on the divisor

If $b\neq 0$ and $a\mid b$ , then $|a|\le |b|$ .

Proof:

$\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; Assumption} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; Definition of divisibility, Assumption} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; Absolute value property, From(2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; From(1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; From(4), if }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; From(5)} \\ &\blacksquare& \end{array}$

Proposed Exercises

Show that the theorem “bound on the divisor” is not necessarily true if $b=0$
Consider a set $A$ and a relation $\rho$ on that set. If the elements $x,y\in A$ are such that $x$ is related to $y$ by means of $\rho$ , then it is written $x\rho y$ . The relation $\rho$ is said to be a partial order on $A$ if:
a) $(\forall x\in A) (x\rho x)$ ,
b) $(\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)$
c) $(\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z)$ .
Prove that the divisibility relation is a partial order relation on the integers.
Prove by induction that if $a\mid b_1, a\mid b_2, \cdots, a\mid b_n$ , then $a\mid \sum_{i=1}^n b_i x_i$ for any set $\{x_i\}_{i=1}^n \subset \mathbb{Z}$ . Also prove that if $a\mid b_i$ , with $i\in \{1,2,3,\cdots, n\}$ and $c$ can be written as a linear combination of those $b_i$ , then $a\mid c$ .
If $a\neq 0$ , show that the set $\{x\;:\; d\mid a\}$ is a finite set.
Consider a fixed $n\in\mathbb{Z}^+$ , and let
$S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}$
Prove:
1. $d\in S \leftrightarrow n/d\in S$
2. If the elements of $S$ are arranged in increasing order: $1=d_1 \lt d_2 \lt \cdots \lt d_t =n$ , then the corresponding elements $n\mid d_i$ with $i \in \{1,2,\cdots, t\}$ are in decreasing order.
Suppose that $a,b\in\mathbb{Z}^+$ and $ab=c$ . Prove that $\min\{a,b\}\le \sqrt{c}$ .
An integer n is said to be even if $2\mid n$ , and odd if $2\nmid n$ . Prove that the sum and the difference of:
1. two even numbers is an even number.
2. two odd numbers is an even number.
3. an even number and an odd number is an odd number.
If $n$ is an odd integer different from $\pm 1$ , prove that $n$ cannot divide two consecutive even numbers.
Let $a,b,n\in\mathbb{Z}$ be such that $|a-b|\lt |n|$ . Prove that $n$ cannot divide either $a$ or $b$ .
Suppose that $a\in\mathbb{Z}$ . Prove that:
1. $(\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1$
2. $(\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0$
Let $a,b,c\in\mathbb{Z}$ and suppose that $c\neq 0$ . Show that $ac\mid bc$ implies that $a\mid b$

What is Divisibility?