A prime is a whole number above 1 whose only positive divisors are 1 and itself. Every whole number above 1 has a prime divisor, a composite number has one that is at most its square root, and there are infinitely many primes. The fundamental theorem of arithmetic says that each number above
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
test a number for primes by trial division up to its square root, and use the sieve;
prove that there are infinitely many primes;
state and prove the fundamental theorem of arithmetic, and use prime factorisations to decide when a number is a square or a cube.
Building blocks
You can build 12 as 2×6 or as 3×4. Keep breaking: 12=2×2×3, and the pieces will not break any further. These pieces are the primes.
A prime is an integer p>1 whose only positive divisors are 1 and p. An integer above 1 that is not prime is composite. The number 1 is neither. If 1 were a prime, factorisation would not be unique: 6=2×3=1×2×3.
Every number has a prime divisor
Take n>1 and let d be its smallest divisor above 1. If d had a divisor c with 1<c<d, then c would divide n and be smaller than d. That cannot be. So d is prime.
If n is composite, write n=ab with 1<a≤b. Then a2≤ab=n, so a≤n. A composite number has a prime divisor that is at most its square root. To test n, try the primes up to n. To test 97, try 2, 3, 5 and 7. None divides it, so 97 is prime.
The sieve of Eratosthenes lists all primes up to N. Write the numbers from 2 to N. Circle 2 and cross out its other multiples. Circle the next number left, and cross out its multiples. Stop when you pass N: the numbers left are prime.
A ten by ten grid of the numbers 1 to 100. The 25 primes up to 100 are in blue squares: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. The other numbers are grey, and the number 1 is crossed out. A note says that only the multiples of 2, 3, 5 and 7 need to be crossed out, because 11 times 11 is already more than 100.
There are infinitely many primes
This proof is about two thousand three hundred years old, and it is in Euclid's Elements.
Suppose there were only finitely many primes, p1,p2,…,pk.
Form N=p1p2⋯pk+1. It is bigger than 1, so it has a prime divisor p.
The prime p is one of the pi, so p divides the product p1⋯pk.
Then p divides N−p1⋯pk=1. No prime divides 1, so the list was not complete.
Be careful. The proof does not say that N itself is prime. Indeed 2×3×5×7×11×13+1=30031=59×509.
Primes can also be far apart. The numbers n!+2,n!+3,…,n!+n are n−1 composite numbers in a row, because k∣n!+k for 2≤k≤n.
Euclid's lemma
Euclid's lemma. If a prime p divides a product ab, then p∣a or p∣b.
This is the special property of primes. It fails for 6, as lesson 1 showed. We prove it in course 2 with Bezout's identity. By repeating it, if p divides a product of many factors, it divides one of them.
The fundamental theorem of arithmetic
Theorem. Every integer n>1 can be written as a product of primes, and the product is unique apart from the order of the factors.
Existence. Suppose some numbers have no factorisation, and let n be the smallest. It is not prime, so n=ab with 1<a,b<n. Both a and b are smaller than n, so both have factorisations. Joining them gives one for n, which is impossible.
Uniqueness. Suppose p1p2⋯pr=q1q2⋯qs, all primes. The prime p1 divides the right side, so by Euclid's lemma it divides some qj. A prime that divides a prime is equal to it, so p1=qj. Cancel it from both sides and repeat. The two lists hold the same primes, the same number of times.
We write the factorisation with exponents, n=p1a1p2a2⋯pkak. For example 360=23⋅32⋅5. This is the canonical form. School books in India call it the prime factorisation, and some books say "standard form".
Squares, cubes and powers
The theorem lets us read properties straight from the exponents.
n is a perfect square exactly when every exponent is even. 360=23⋅32⋅5 is not, and 360×10=24⋅32⋅52=602 is.
n is a perfect kth power exactly when every exponent is a multiple of k.
If ab is a perfect square and a and b share no prime, then a and b are both perfect squares. Each prime of ab sits wholly inside a or wholly inside b, with its even exponent.
Primes above 3. Every prime p>3 leaves remainder 1 or 5 on division by 6, since the other remainders give a multiple of 2 or 3. So p=6k±1, and p2−1=(p−1)(p+1) is a multiple of 24.
Practise with new numbers
Try it in Python
The program runs the sieve, counts the primes up to 1000, and factorises Euclid's numbers 2×3×⋯×p+1.
Common mistakes
Calling 1 a prime. It is not. The first prime is 2, the only even prime.
Testing divisors past the square root. You only need the primes up to n.
Thinking that p1⋯pk+1 is always prime. It has a new prime factor, which may be a smaller number than itself.
Trusting a pattern.n2+n+41 is prime for n=0 to 39, and 402+40+41=412.
Remember these
A composite n has a prime factor at most n.
There are infinitely many primes (Euclid).
Euclid's lemma: if p∣ab, then p∣a or p∣b.
Every n>1 is a product of primes in exactly one way.
n is a perfect kth power when every exponent in its factorisation is a multiple of k.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Is 221 prime? Which primes do you need to try?
Write 1188 in canonical form.
Find the smallest whole number k for which 1188k is a perfect cube.
Give a run of five consecutive composite numbers.
Explain why p2−1 is divisible by 24 for every prime p>3.
References
David M. Burton, Elementary Number Theory, Chapter 3, sections 3.1 to 3.3 on the fundamental theorem, the sieve and the infinitude of primes.
NCERT, Mathematics Textbook for Class X, Chapter 1 (Real Numbers), for the fundamental theorem of arithmetic.
Enroll free in Division, Divisibility Rules and Primes
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.