Discrete Math › Section G · Additional topics › Topic G.2
Divisibility and primes
Number theory studies the integers, and its oldest questions are about which numbers divide which and how numbers break into primes. Those questions are more than two thousand years old, yet they now underpin the encryption that protects online banking.
Whole numbers only
Ask whether 7 divides 91 and you are asking a question with no fractions allowed: is 91 a whole-number multiple of 7? (It is: \(91 = 7 \times 13\).) Number theory works entirely within the integers \(\mathbb{Z}\), and that restriction is what makes it interesting. Division does not always come out evenly, so remainders matter, and some numbers cannot be broken down at all. This topic covers divisibility, the division algorithm, the primes and the fact that every integer factors into primes in only one way. The next topic, "GCD, congruences, and modular arithmetic", builds on all of it.
Divisibility
For integers \(a\) and \(b\), \(a\) divides \(b\), written \(a \mid b\), if \(b = ak\) for some integer \(k\). Then \(a\) is a divisor of \(b\) and \(b\) is a multiple of \(a\). So \(7 \mid 91\) and \(-4 \mid 12\), but \(5 \nmid 12\). Every integer divides 0, since \(0 = a \cdot 0\). Two properties are used constantly. If \(a \mid b\) and \(b \mid c\), then \(a \mid c\). If \(a \mid b\) and \(a \mid c\), then \(a \mid bx + cy\) for any integers \(x\) and \(y\): writing \(b = am\) and \(c = an\) gives \(bx + cy = a(mx + ny)\). Note that \(a \mid b\) is a statement, true or false, while \(a/b\) is a number.
The division algorithm
When division is not exact, there is still a tidy statement. For any integer \(a\) and any positive integer \(d\), there are unique integers \(q\) and \(r\) with
Here \(q\) is the quotient and \(r\) the remainder, also written \(a \bmod d\). For \(a = 47\) and \(d = 6\): \(47 = 6 \cdot 7 + 5\). The condition \(0 \le r < d\) is what makes the answer unique, and it matters for negative numbers: \(-17 = 5 \cdot (-4) + 3\), so the remainder is 3, not \(-2\). And \(d \mid a\) exactly when the remainder is 0.
Primes and composites
A prime is an integer greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, 13, …. An integer greater than 1 that is not prime is composite: it can be written as \(ab\) with \(1 < a, b < n\). The number 1 is neither prime nor composite, a convention that keeps factorisations unique. 2 is the only even prime. A useful fact for testing: if \(n = ab\) with \(a \le b\), then \(a^2 \le ab = n\), so \(a \le \sqrt{n}\). Every composite \(n\) therefore has a prime factor no larger than \(\sqrt{n}\), and to test \(n\) it is enough to try the primes up to \(\sqrt{n}\).
Worked example: testing a number for primality
Is 391 prime? 1. Since \(\sqrt{391} \approx 19.8\), it is enough to try the primes up to 19: 2, 3, 5, 7, 11, 13, 17 and 19. 2. 391 is odd, so 2 fails; \(391 = 3 \cdot 130 + 1\), so 3 fails; it does not end in 0 or 5, so 5 fails. 3. Division: \(391 = 7 \cdot 55 + 6\), \(391 = 11 \cdot 35 + 6\) and \(391 = 13 \cdot 30 + 1\), all with non-zero remainders. 4. But \(391 = 17 \times 23\), so 391 is composite. Had no prime up to 19 divided it, 391 would be prime. Trial division is fine for small numbers but hopeless for numbers hundreds of digits long.
The fundamental theorem of arithmetic
Every integer greater than 1 can be written as a product of primes, and that product is unique apart from the order of the factors. For example, \(1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7\), and no other collection of primes multiplies to 1260. Existence was proved in the topic "Strong induction": a composite number splits into smaller factors, which split further until only primes remain. Uniqueness needs a further fact, that if a prime divides a product \(ab\) it divides \(a\) or \(b\), which is proved in the next topic. Primes are to integers what atoms are to molecules.
Reading divisors from a factorisation
Once a number is factorised, its divisors can be read off. A positive divisor of \(1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7\) is \(2^a 3^b 5^c 7^d\) with \(0 \le a \le 2\), \(0 \le b \le 2\), \(0 \le c \le 1\) and \(0 \le d \le 1\). By the product principle there are \(3 \cdot 3 \cdot 2 \cdot 2 = 36\) positive divisors: add 1 to each exponent and multiply. For instance \(72 = 2^3 \cdot 3^2\) has \(4 \cdot 3 = 12\) divisors. A number is a perfect square exactly when every exponent in its factorisation is even, which is why \(1260\) is not a square but \(1260 \cdot 35 = 2^2 3^2 5^2 7^2 = 44{,}100\) is.
Worked example: there are infinitely many primes
Euclid's argument, more than two thousand years old, is a proof by contradiction. 1. Suppose there were only finitely many primes, \(p_1, p_2, \ldots, p_k\). 2. Let \(N = p_1 p_2 \cdots p_k + 1\). Dividing \(N\) by any \(p_i\) leaves remainder 1, so no \(p_i\) divides \(N\). 3. But \(N > 1\), so \(N\) has a prime factor, and that prime is not on the list. 4. This contradicts the assumption, so the primes never run out. Note that \(N\) itself need not be prime:
The proof only needs \(N\) to have some prime factor outside the list.
Finding and counting primes
The sieve of Eratosthenes lists all primes up to \(n\). Write 2 to \(n\), then repeatedly take the smallest number not yet crossed out, keep it as prime, and cross out its other multiples. You can stop after the primes up to \(\sqrt{n}\): for \(n = 50\), crossing out multiples of 2, 3, 5 and 7 leaves the 15 primes from 2 to 47. The primes thin out but never stop. The prime number theorem says the number of primes up to \(x\) is roughly \(\frac{x}{\ln x}\): for \(x = 1000\) that estimate is about 145, while the true count is 168.
Common mistakes to avoid
First, confusing \(a \mid b\) with \(a / b\): \(3 \mid 12\) is a true statement, not the number \(\frac{1}{4}\). Second, calling 1 a prime. Third, giving a negative remainder: the division algorithm requires \(0 \le r < d\). Fourth, testing divisors beyond \(\sqrt{n}\), which wastes effort, or stopping before it, which can miss a factor. Fifth, stopping a factorisation early: \(4 \cdot 21\) is a factorisation of 84, but the prime factorisation is \(2^2 \cdot 3 \cdot 7\). Sixth, thinking Euclid's number \(p_1 \cdots p_k + 1\) must itself be prime.
Key takeaways
\(a \mid b\) means \(b = ak\) for an integer \(k\); divisibility is transitive and passes to combinations \(bx + cy\). The division algorithm gives a unique quotient and remainder with \(0 \le r < d\). A prime has exactly two positive divisors, and every composite \(n\) has a prime factor at most \(\sqrt{n}\). Every integer above 1 factors uniquely into primes, and adding 1 to each exponent and multiplying counts the divisors. Euclid proved there are infinitely many primes; the sieve finds small ones, and about \(\frac{x}{\ln x}\) lie below \(x\).
Flashcards
Flashcard
a divides b: b = ak for some integer k
Test your understanding
Question 1 of 5
What is the smallest prime factor of 323?
Question 2 of 5
By the division algorithm with d = 6, what are the quotient q and remainder r for a = −23?
Question 3 of 5
What is the prime factorisation of 504?
Question 4 of 5
How many positive divisors does 200 have?
Question 5 of 5
In Euclid's proof, N = p₁p₂…pₖ + 1 is built from a supposed complete list of primes. Which statement is correct?
