Divisibility and Prime Numbers
Learning objectives
- Use divisibility to decide when one integer is a factor or a multiple of another.
- Apply the divisibility rules for 2, 3, 5, 9 and 10.
- Recognise primes and composites and find primes with the sieve of Eratosthenes.
- Write an integer as a product of primes and explain why there are infinitely many primes.
Divisibility
An integer \(a\neq 0\) divides an integer \(b\), written \(a\mid b\), if \(b=ak\) for some integer \(k\). Then \(a\) is a divisor (or factor) of \(b\), and \(b\) is a multiple of \(a\).
\(3\mid 12\) because \(12=3\cdot 4\), but \(5\nmid 12\).
Every nonzero integer divides 0 (since \(0=a\cdot 0\)), and 1 divides every integer.
If \(a\mid b\) and \(a\mid c\), then \(a\mid (b+c)\) and \(a\mid (b-c)\).
Show proof
Write \(b=ak\) and \(c=am\). Then \(b+c=a(k+m)\) and \(b-c=a(k-m)\), and \(k+m\), \(k-m\) are integers. ∎
Show that 6 divides \(12n+18\) for every integer \(n\).
Factor: \(12n+18=6(2n+3)\), and \(2n+3\) is an integer.
Divisibility rules
By 2: the last digit is even. By 5: the last digit is 0 or 5. By 10: the last digit is 0.
By 3 (or 9): the sum of the digits is divisible by 3 (or 9).
Is 7281 divisible by 3 or by 9?
The digit sum is \(7+2+8+1=18\). Since 18 is divisible by 3 and by 9, so is 7281.
Prime numbers
A prime is an integer \(p>1\) whose only positive divisors are 1 and \(p\). An integer \(n>1\) that is not prime is composite. The number 1 is neither prime nor composite.
The numbers \(2,3,5,7,11,13\) are prime; \(4,6,8,9,10,12\) are composite. The number 2 is the only even prime.
The sieve of Eratosthenes
Press Next prime to cross out the multiples of each prime in turn. The numbers that survive to the end are prime.
Every composite number \(n\) has a prime factor \(p\) with \(p\le\sqrt n\).
Show proof
Write \(n=ab\) with \(1<a\le b<n\). Then \(a^2\le ab=n\), so \(a\le\sqrt n\). Any prime factor of \(a\) is also a factor of \(n\) and is at most \(a\). ∎
Is 97 prime?
Since \(\sqrt{97}<10\), it is enough to test the primes 2, 3, 5 and 7. None divides 97: it is odd, its digit sum 16 is not divisible by 3, it does not end in 0 or 5, and \(7\cdot 13=91\), \(7\cdot 14=98\). So 97 is prime.
Prime factorization
Every integer \(n>1\) can be written as a product of primes, and this product is unique apart from the order of the factors.
Show proof
Existence, by strong induction. If \(n\) is prime, it is a product of one prime. Otherwise \(n=ab\) with \(1<a,b<n\); by the induction hypothesis both \(a\) and \(b\) are products of primes, so \(n\) is too. Uniqueness is the deeper part; it rests on the fact that a prime dividing a product \(ab\) must divide \(a\) or \(b\).
Factor 360.
\[360=2\cdot 180=2\cdot 2\cdot 90=2\cdot 2\cdot 2\cdot 45=2^3\cdot 3^2\cdot 5\]
There are infinitely many prime numbers.
Show proof
Suppose there were only finitely many primes \(p_1,p_2,\ldots,p_m\). Let \(N=p_1p_2\cdots p_m+1\). Then \(N>1\) has a prime factor \(q\). Since \(q\) is one of the \(p_i\), it divides \(p_1\cdots p_m\), hence also divides \(N-p_1\cdots p_m=1\), which is impossible. So no finite list contains all primes. ∎
Primes thin out but never stop: there are 25 primes up to 100 and 46 primes up to 200.
Exercises
List all positive divisors of 36.
Show solution
\(1,\ 2,\ 3,\ 4,\ 6,\ 9,\ 12,\ 18,\ 36\)
Use the digit-sum rule to decide whether 4527 is divisible by 9.
Show solution
The digit sum is \(4+5+2+7=18\), which is divisible by 9, so \(9\mid 4527\) (indeed \(4527=9\cdot 503\)).
Prove that if \(a\mid b\) and \(b\mid c\), then \(a\mid c\).
Show solution
Write \(b=ak\) and \(c=bm\). Then \(c=(ak)m=a(km)\), and \(km\) is an integer.
Is 91 prime?
Show solution
Since \(\sqrt{91}<10\), test the primes up to 7. We find \(91=7\cdot 13\), so 91 is composite.
Write 504 as a product of primes.
Show solution
\(504=2\cdot 252=2^2\cdot 126=2^3\cdot 63=2^3\cdot 3^2\cdot 7\)
Find a prime \(p\) such that \(p+2\) and \(p+4\) are also prime. Why is there only one such \(p\)?
Show solution
Take \(p=3\): the numbers 3, 5, 7 are all prime. For any \(p\), the numbers \(p,\ p+2,\ p+4\) leave three different remainders on division by 3, so exactly one of them is a multiple of 3. A prime that is a multiple of 3 equals 3, and \(p+2=3\) would give \(p=1\), which is not prime; so \(p=3\).
Summary
- The integer a divides b when b = ak; sums and differences of multiples of a are multiples of a.
- Digit rules quickly test divisibility by 2, 3, 5, 9 and 10.
- A composite number n has a prime factor at most \(\sqrt n\), so testing primes up to \(\sqrt n\) decides primality.
- Every integer greater than 1 factors uniquely into primes, and there are infinitely many primes.