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: this definition applies verbatim when $a = 0$ as well. The examples below mostly take $a \neq 0$, but what happens at $a = 0$ is worked out in 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$: just apply the definition as it stands. Since $0 = k \cdot 0$ holds for every integer $k$, $0 \mid 0$ is true. On the other hand, for $b \neq 0$ there is no $k$ with $b = k \cdot 0 = 0$, so $0 \nmid b$. In other words, the only number $0$ divides is $0$ itself.)
(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)$$In addition, the following basic property of the GCD holds:
every common divisor of these numbers divides their greatest common divisor.
This property does not follow from the definition "largest among the common divisors" alone — being the largest and dividing all the others are different claims. It is proved from prime factorization in Chapter 2, or from Bézout's identity in Chapter 3. In this chapter we take it as given.
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$.
You do not have to list every divisor
The example above wrote out every divisor of 12 and of 18, but that approach stalls as soon as the numbers get large. In fact
$$\gcd(a, b) = \gcd(b,\ a \bmod b)$$holds, so repeating this alone yields the GCD without enumerating a single divisor. For instance
$$48 = 2 \cdot 18 + 12, \qquad 18 = 1 \cdot 12 + 6, \qquad 12 = 2 \cdot 6$$gives $\gcd(48, 18) = 6$. This is the Euclidean algorithm; its principle and proof, along with the extended algorithm, are covered in Chapter 3.
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 basic property of the GCD, $d \mid g$. Also $d \mid c$. Hence $d$ is a common divisor of $g$ and $c$, so by the same property $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 basic property of the GCD, $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]$$In addition, the following basic property of the LCM holds:
every common multiple of these numbers is a multiple of their least common multiple.
As with the GCD, this does not follow from the definition "smallest among the positive common multiples" alone. The proof of the next theorem actually establishes it for the two-number case.
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$. By the basic property of the LCM, $m \mid L$. Also $c \mid L$. Hence $L$ is a common multiple of $m$ and $c$, so by the same property $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 basic property of the LCM, $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 ✓
Note: this calculator uses the JavaScript Number type, which cannot represent integers above $2^{53} - 1 = 9007199254740991$ exactly. Beyond that range it says so instead of showing a verification mark.
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 together with zero and the negative integers.
- Divisibility: $a \mid b$ ⇔ there exists an integer $k$ with $b = ka$.
- Greatest common divisor: the largest among the common divisors (and every common divisor divides it).
- Least common multiple: the smallest positive common multiple (and every common multiple is a multiple of it).
- 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.