Chapter 1: Properties of Integers
Divisors, Multiples, and Divisibility
Introduction (high school level)
Goals of this page
Understand the fundamental properties of integers and define the notions of divisor, multiple, and divisibility. Learn how to compute the greatest common divisor and the least common multiple and the relationship between them.
1. What are integers?
An integer is one of the numbers $\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$.
The set of all integers is denoted by $\mathbb{Z}$.
Classification of numbers
- Natural numbers $\mathbb{N}$: $1, 2, 3, \ldots$ (positive integers)
- Integers $\mathbb{Z}$: $\ldots, -2, -1, 0, 1, 2, \ldots$
- Rational numbers $\mathbb{Q}$: numbers expressible as a fraction ($\frac{p}{q}$ with $p, q \in \mathbb{Z}$, $q \neq 0$)
Inclusions: $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q}$.
2. Divisibility
For integers $a, b$, if there exists an integer $k$ such that $b = ka$, then
"$a$ divides $b$" or "$b$ is divisible by $a$", written
$$a \mid b$$In this case $a$ is called a divisor of $b$, and $b$ is called a multiple of $a$.
Note: the case $a \neq 0$ is usually assumed. For $a = 0$, see the remark in §3.
- $3 \mid 12$ ✓ ($12 = 3 \times 4$)
- $5 \mid 15$ ✓ ($15 = 5 \times 3$)
- $4 \nmid 10$ ✗ ($10$ is not divisible by $4$)
3. Basic Properties of Divisibility
For integers $a, b, c$ the following hold:
- Reflexivity: $a \mid a$ (every integer divides itself).
- Transitivity: if $a \mid b$ and $b \mid c$, then $a \mid c$.
- Linear combinations: if $a \mid b$ and $a \mid c$, then $a \mid (bx + cy)$ for any integers $x, y$.
(Proof of 1)
Since $a = 1 \cdot a$, we have $a \mid a$.
(Remark on $a = 0$: the equation $0 = k \cdot 0$ holds for any integer $k$, so by the definition $0 \mid 0$ is true. However, some textbooks leave $0 \mid 0$ undefined or treat it separately. Beginners may safely focus on the case $a \neq 0$.)
(Proof of 2)
From $a \mid b$ we have $b = ka$ for some integer $k$.
From $b \mid c$ we have $c = lb$ for some integer $l$.
Hence $c = lb = l(ka) = (lk)a$.
Since $lk$ is an integer, $a \mid c$.
(Proof of 3)
From $a \mid b$ we have $b = ka$, and from $a \mid c$ we have $c = la$.
$$bx + cy = kax + lay = a(kx + ly)$$Since $kx + ly$ is an integer, $a \mid (bx + cy)$.
4. Divisors and Multiples
A positive divisor of a positive integer $n$ is a positive integer that divides $n$.
$12 = 1 \times 12 = 2 \times 6 = 3 \times 4$
Hence the positive divisors of 12 are $1, 2, 3, 4, 6, 12$, six in total.
5. Greatest Common Divisor (GCD)
A divisor common to two or more positive integers is called a common divisor.
The largest common divisor is called the greatest common divisor, written
$$\gcd(a, b) \text{ or } (a, b)$$Divisors of 12: $1, 2, 3, 4, 6, 12$.
Divisors of 18: $1, 2, 3, 6, 9, 18$.
Common divisors: $1, 2, 3, 6$.
Greatest common divisor: $\gcd(12, 18) = 6$.
GCD of three or more integers
The greatest common divisor of three or more integers can be computed pairwise in order:
$$\gcd(a, b, c) = \gcd(\gcd(a, b),\, c)$$This generalizes to any number of integers:
$$\gcd(a_1, a_2, \ldots, a_n) = \gcd(\gcd(a_1, \ldots, a_{n-1}),\, a_n)$$Proof
Set $d = \gcd(a, b, c)$, $g = \gcd(a, b)$, and $d' = \gcd(g, c)$. We show $d = d'$.
(Proof of $d \mid d'$)
Since $d = \gcd(a, b, c)$, we have $d \mid a$ and $d \mid b$. Thus $d$ is a common divisor of $a$ and $b$, so by the definition of the greatest common divisor $g = \gcd(a, b)$, we have $d \mid g$. Also $d \mid c$. Hence $d$ is a common divisor of $g$ and $c$, so by the definition of $d' = \gcd(g, c)$ we have $d \mid d'$.
(Proof of $d' \mid d$)
Since $d' = \gcd(g, c)$, we have $d' \mid g$ and $d' \mid c$. Since $g = \gcd(a, b)$, we have $g \mid a$ and $g \mid b$. Combined with $d' \mid g$, this gives $d' \mid a$ and $d' \mid b$. Also $d' \mid c$. Hence $d'$ is a common divisor of $a, b, c$, so by the definition of $d = \gcd(a, b, c)$ we have $d' \mid d$.
Since $d \mid d'$ and $d' \mid d$ with $d, d' > 0$, we conclude $d = d'$. $\blacksquare$
Pairwise computation:
- $\gcd(48, 60) = 12$
- $\gcd(12, 36) = 12$
Hence $\gcd(48, 60, 36) = 12$.
Speed-up via early termination
If $\gcd$ becomes $1$ at any intermediate step, no further computation is necessary, since for any integer $c$ we have $\gcd(1, c) = 1$.
Compute $\gcd(7, 12, 100, 999)$.
- $\gcd(7, 12) = 1$ — terminate here.
Once $\gcd = 1$ is reached, the answer is $1$ regardless of the remaining $100, 999$.
6. Least Common Multiple (LCM)
A multiple common to two or more positive integers is called a common multiple.
The smallest positive common multiple is called the least common multiple, written
$$\mathrm{lcm}(a, b) \text{ or } [a, b]$$For positive integers $a, b$,
$$\gcd(a, b) \times \mathrm{lcm}(a, b) = ab$$Set $d = \gcd(a, b)$; then $a = da'$ and $b = db'$ with $\gcd(a', b') = 1$.
$da'b'$ is a multiple of $a = da'$ (since $da'b' = a \cdot b'$) and a multiple of $b = db'$ (since $da'b' = b \cdot a'$), hence it is a common multiple. Because $a'$ and $b'$ are coprime, every common multiple of $a$ and $b$ is a multiple of $da'b'$, so $\mathrm{lcm}(a, b) = da'b'$.
Therefore
$$\gcd(a, b) \times \mathrm{lcm}(a, b) = d \times da'b' = d^2a'b' = (da')(db') = ab$$$\mathrm{lcm}(12, 18) = \dfrac{12 \times 18}{6} = \dfrac{216}{6} = 36$
Verification: the least common multiple of $12, 24, 36, \ldots$ and $18, 36, \ldots$ is indeed 36. ✓
LCM of three or more integers
As for the GCD, the LCM can be computed pairwise in order:
$$\mathrm{lcm}(a, b, c) = \mathrm{lcm}(\mathrm{lcm}(a, b),\, c)$$Proof
Set $L = \mathrm{lcm}(a, b, c)$, $m = \mathrm{lcm}(a, b)$, $L' = \mathrm{lcm}(m, c)$. We show $L = L'$.
(Proof of $L' \mid L$)
$L$ is a common multiple of $a, b, c$, so $a \mid L$ and $b \mid L$. Since $m = \mathrm{lcm}(a, b)$ is the smallest common multiple of $a, b$, we have $m \mid L$. Also $c \mid L$. Hence $L$ is a common multiple of $m$ and $c$, so by the definition of $L' = \mathrm{lcm}(m, c)$, $L' \mid L$.
(Proof of $L \mid L'$)
Since $m = \mathrm{lcm}(a, b)$, we have $a \mid m$ and $b \mid m$. Since $m \mid L'$, $a \mid L'$ and $b \mid L'$. Also $c \mid L'$. Hence $L'$ is a common multiple of $a, b, c$, so by the definition of $L = \mathrm{lcm}(a, b, c)$, $L \mid L'$.
Since $L' \mid L$ and $L \mid L'$ with $L, L' > 0$, we conclude $L = L'$. $\blacksquare$
- $\mathrm{lcm}(4, 6) = 12$
- $\mathrm{lcm}(12, 10) = 60$
Hence $\mathrm{lcm}(4, 6, 10) = 60$.
Pitfall: GCD × LCM = abc does not hold for three or more integers
For two integers, $\gcd(a, b) \times \mathrm{lcm}(a, b) = ab$ always holds, but this relation fails for three or more integers.
Counterexample. Take $a = 2,\, b = 3,\, c = 6$:
- $\gcd(2, 3, 6) \times \mathrm{lcm}(2, 3, 6) = 1 \times 6 = 6$
- $abc = 2 \times 3 \times 6 = 36$
Since $6 \neq 36$, the identity fails. Intuitively, the two-variable formula $\gcd \times \mathrm{lcm} = ab$ corrects for the overlap of common factors exactly once; for three or more variables the overlap structure becomes more complex, and $\gcd(a,b,c)$ alone cannot capture this correction.
Therefore, to compute an LCM of three or more integers, do not use
$\mathrm{lcm}(a, b, c) = \dfrac{abc}{\gcd(a, b, c)}$.
Use the pairwise rule $\mathrm{lcm}(\mathrm{lcm}(a,b),\, c)$ instead.
7. Worked Examples
Compute $\gcd(48, 60)$ and $\mathrm{lcm}(48, 60)$.
Solution
Divisors of 48: $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$.
Divisors of 60: $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$.
Common divisors: $1, 2, 3, 4, 6, 12$.
$\gcd(48, 60) = 12$.
$\mathrm{lcm}(48, 60) = \dfrac{48 \times 60}{12} = 240$.
Given $a \mid b$ and $a \mid c$, prove $a \mid (2b - 3c)$.
Solution
From $a \mid b$, $b = ka$; from $a \mid c$, $c = la$ (with $k, l$ integers).
$$2b - 3c = 2ka - 3la = a(2k - 3l)$$Since $2k - 3l$ is an integer, $a \mid (2b - 3c)$.
8. GCD / LCM Calculator
Enter two positive integers; the calculator computes their greatest common divisor and least common multiple.
$\gcd$ = 6, $\mathrm{lcm}$ = 36
Verification: $\gcd \times \mathrm{lcm}$ = 216, $a \times b$ = 216 ✓
9. Exercises
Problems
- List all positive divisors of 24 and state their count.
- Compute $\gcd(36, 48)$ and $\mathrm{lcm}(36, 48)$.
- Compute $\mathrm{lcm}(6, 10, 15)$ by pairwise computation.
- Given $a \mid b$ and $a \mid c$, prove $a \mid (5b + 7c)$.
Show solutions
1.
$24 = 1 \times 24 = 2 \times 12 = 3 \times 8 = 4 \times 6$
Positive divisors: $1, 2, 3, 4, 6, 8, 12, 24$ — 8 divisors.
2.
Divisors of 36: $1, 2, 3, 4, 6, 9, 12, 18, 36$.
Divisors of 48: $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$.
Common divisors: $1, 2, 3, 4, 6, 12$ → $\gcd(36, 48) = 12$.
$\mathrm{lcm}(36, 48) = \dfrac{36 \times 48}{12} = \dfrac{1728}{12} = 144$.
3.
- $\mathrm{lcm}(6, 10) = \dfrac{6 \times 10}{\gcd(6, 10)} = \dfrac{60}{2} = 30$
- $\mathrm{lcm}(30, 15) = \dfrac{30 \times 15}{\gcd(30, 15)} = \dfrac{450}{15} = 30$
Hence $\mathrm{lcm}(6, 10, 15) = 30$.
4.
From $a \mid b$, $b = ka$; from $a \mid c$, $c = la$ (with $k, l$ integers).
$$5b + 7c = 5ka + 7la = a(5k + 7l)$$Since $5k + 7l$ is an integer, $a \mid (5b + 7c)$. $\blacksquare$
Summary
Key points
- Integers $\mathbb{Z}$: the natural numbers extended in the negative direction.
- Divisibility: $a \mid b$ ⇔ there exists an integer $k$ with $b = ka$.
- Greatest common divisor: the largest among the common divisors.
- Least common multiple: the smallest positive common multiple.
- GCD × LCM relation: $\gcd(a,b) \times \mathrm{lcm}(a,b) = ab$.
Frequently Asked Questions (FAQ)
- What is divisibility of integers?
- When an integer $a$ divides an integer $b$, one says "$a$ divides $b$" and writes $a \mid b$. This means there exists an integer $k$ such that $b = ka$.
- What is the relationship between the greatest common divisor and the least common multiple?
- For two positive integers $a, b$ the identity $\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b$ always holds. This relation lets one quantity be computed easily from the other.
- How can the greatest common divisor be computed efficiently?
- The Euclidean algorithm is efficient. Iterate $\gcd(a, b) = \gcd(b, a \bmod b)$; the divisor at the step when the remainder becomes $0$ is the greatest common divisor.