Divisibility and primes
Number theory studies the integers. Its oldest ideas, divisibility and primes, now protect every secure website.
Divisibility
\(a\) divides \(b\), written \(a \mid b\), if \(b = ak\) for some integer \(k\). So \(3 \mid 12\) but \(5 \nmid 12\). Divisibility is transitive, and if \(a \mid b\) and \(a \mid c\), then \(a\) divides any combination \(bx + cy\).
The division algorithm
For any integer \(a\) and positive integer \(d\), there are unique integers \(q\) and \(r\) with \(a = dq + r\) and \(0 \le r < d\). For \(a = 47\), \(d = 5\): \(47 = 5 \cdot 9 + 2\). The remainder \(r\) is \(a \bmod d\).
a = dq + r,\ 0 \le r < dPrimes
A prime is an integer greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, .... Integers greater than 1 that are not prime are composite. 2 is the only even prime. To test whether \(n\) is prime, it suffices to check divisors up to \(\sqrt{n}\).
The fundamental theorem of arithmetic
Every integer greater than 1 can be written as a product of primes in exactly one way, apart from order: \(360 = 2^3 \cdot 3^2 \cdot 5\). Primes are the building blocks of the integers, the way atoms build molecules.
360 = 2^3 \cdot 3^2 \cdot 5There are infinitely many primes
Euclid's proof: suppose \(p_1, \ldots, p_k\) were all the primes. Then \(N = p_1p_2\cdots p_k + 1\) leaves remainder 1 when divided by each of them, so its prime factors are new primes, a contradiction. The primes thin out but never stop.
The sieve of Eratosthenes
To list primes up to \(n\), write the numbers 2 to \(n\), then repeatedly circle the smallest unmarked number and cross out its multiples. Numbers left uncrossed are prime. It is ancient but still an efficient way to generate many small primes.
The distribution of primes
The prime number theorem says the number of primes up to \(x\) is approximately \(\frac{x}{\ln x}\). There are 168 primes below 1000 and about \(\frac{1000}{6.9} \approx 145\) by the estimate. Many questions remain open, such as the twin prime conjecture that infinitely many primes differ by 2.
Worked example
Is 221 prime? \(\sqrt{221} \approx 14.9\), so test primes up to 13: 2, 3, 5, 7, 11 fail, but \(221 = 13 \times 17\). So 221 is composite. Checking only up to the square root is a huge time saver.
Key takeaways
\(a \mid b\) means \(b\) is a multiple of \(a\). The division algorithm gives a unique quotient and remainder. Every integer factors uniquely into primes, and there are infinitely many primes. Test primality by trial division up to \(\sqrt{n}\) for small numbers.
Flashcard
a divides b
Check your understanding
What is the prime factorisation of 84?