The Improving Mathematics Education in Schools (TIMES) Project
The Improving Mathematics Education in Schools (TIMES) Project
Primes and prime factorisation
Number and Algebra : Module 16Years : 78
June 2011
A fundamental technique in mathematics is to break something down into its component parts, and rebuild it from those parts. Thus we can factor any whole number into a product of prime numbers, for example
60 = 22 × 3 × 5
and this prime factorisation is unique, apart from the order of the factors. Conversely, if we are given the prime factors of a number, we can reconstruct the original whole number by multiplying the prime factors together,
(2 × 2) × (3 × 5) = 4 × 15 = 60 or (2 × 5) × (2 × 3) = 10 × 6 = 60
and we will always get the same original number, whatever order we choose for multiplying the prime factors.
In other situations, however, such processes do not work nearly as straightforwardly, as can be illustrated using the analogy of chemistry. Every compound can be broken down uniquely into its elements, but if we are given the elements, there are often a great many different compounds that can be formed from them.
Prime factorisation is a very useful tool when working with whole numbers, and will be used in mental arithmetic, in fractions, for finding square roots, and in calculating the HCF and LCM.
The definition of prime numbers
The discussion above shows that for the purposes of prime factorisation, we need to distinguish three types of whole numbers. We leave aside the numbers 0 and 1, and then organise the remaining whole numbers 2, 3, 4, 5, … into:
Prime numbers and composite numbers need to be defined rather carefully:
The phrase ‘greater than 1’ is needed in the definition of prime numbers to exclude 1.
We do not want 1 to be a prime number, otherwise the factorisation of numbers into primes would not be unique. For example, we could write
60 = 22 × 3 × 5 = 1 × 22 × 3 × 5 = 12 × 22 × 3 × 5 = …
The phrase ‘greater than 1’ is needed in the definition of composite numbers to exclude 1, which has no prime factors and so is not the product of two or more prime numbers. The phrase also excludes 0, which is divisible by every whole number and so has no sensible prime factorisation.
The number system we are talking about is the set of whole numbers 0, 1, 2, 3, …, and
the phrase ‘whole number factor’ makes the restriction in the definitions quite clear. Students often realise that a prime number like 5 has other factors if larger number systems are considered, for example,
5 = (−5) × (−1) and 5 = 2 × 2.
It is better to be precise than to invite arguments about what may be implied, but unsaid.
A composite number can be represented by at least two different rectangular arrays.
For example, 12 can be represented by rectangular arrays in three ways:
A prime number like 5, however, can only be represented by a rectangular array
with just one row.
Prime factorisation and its uniqueness
The two basic facts about prime factorisation are:
The first part is easy to prove. If the number is not prime, keep factoring it into smaller factors. The process must stop because the factors get smaller at every step, but each factor is bigger than 1. When the process can’t be continued any further, the factors are all primes.
The proof of the uniqueness statement involves mathematics that is beyond the K10 Syllabus. The proof is included in an appendix at the end if this module.
This theorem is known as The Fundamental Theorem of Arithmetic
There are infinitely many primes
Euclid’s Elements has a wonderful and simple proof by contradiction of the fact that there are infinitely many prime numbers.
Take any finite collection of primes, say 2, 5, 7 and 11. Multiply them together and add 1 to give
2 × 5 × 7 × 11 + 1 = 770 + 1 = 771.
The resulting number 771 is not divisible by 2, or by 5, or by 7, or 11, because the remainder will be 1 after division by each of these primes. Hence either 771 is a prime different from 2, 5, 7 and 11, or its prime factorisation involves primes different from 2, 5, 7 and 11. (In this case, 771 happens to have prime factorisation 771 = 3 × 257.)
If there were only finitely many primes, we could multiply them all together and add 1, and the resulting number would have a prime factorisation that did not involve any primes on our finite list. This, of course, would be a contradiction.
The previous section used a proof by contradiction. This is a very dramatic way of proving theorems, because it starts off by assuming that the theorem is false, and then argues logically from this assumption to a contradiction. Proof by contradiction is probably best introduced to students by using it to prove that there are infinitely many whole numbers.
Suppose by way of contradiction that there were only finitely many whole numbers. If this were the case, we could sort through them and find the largest whole number N. Then N + 1 would be a whole number greater than N. This is a contradiction, because N was chosen to be the greatest whole number. Hence there are infinitely many whole numbers.
Here is a systematic way of writing down all the prime numbers, and all the composite numbers, up to 100.
The 25 circled numbers are the primes up to 100, and the 74 crossedout numbers (not including 0 and 1) are the composite numbers up to 100.
The patterns within the sequence of prime numbers are notoriously complicated, and have generated some of the most famous solved and unsolved problems in mathematics. Apart from the obvious fact that all primes end in 1, 3, 7 or 9, except for 2 and 5, there are no other obvious patterns.
The table does give some hint that the primes become more widely spaced on average as the numbers get bigger. This is intuitively clear once one observes that more and more prime numbers are used in the sieving process as the numbers get bigger.
Exercise 1
a Imagine the sieving process extended to all numbers up to 200. Identify all the composite numbers from 100 to 200 that are sieved by 11 and 13, but were not
sieved by 2, 3, 5 or 7.
b Identify the first times there are gaps of exactly 4, 6 and 8 between successive prime numbers.
prime testing and factorising a number
Testing whether a reasonably large number is prime is a massive computing problem. One important insight, however, greatly reduces the amount of computation required.
Students will have noticed from the Sieve of Eratosthenes that when finding all primes up to 100, it was only necessary to sieve by the primes 2, 3, 5 and 7. When they sieved by the next prime 11, they would have found that all the multiples of 11 were already crossed out, because the first multiple of 11 not crossed out already would be 11 × 11 = 121, which is greater than 100. The general principle is:
Any number n that is to be tested in school mathematics should thus yield to the following plan of attack:
It is usual to write the prime factorisation in index form with the primes in increasing order,
60 = 22 × 3 × 5.
Exercise 2
List the primes that are needed when the Sieve of Eratosthenes is applied to find all the primes up to 1000.
Exercise 3
How many final zeroes are there in the number 30! = 30 × 29 × 28 × … × 2 × 1?
Awareness of prime divisors can greatly simplify mental arithmetic problems. Combining factors of 2 and 5 together is always useful:
15 × 14 = 30 × 7 = 210 and 825 ÷ 25 = 1650 ÷ 50 = 3300 ÷ 100 = 33.
In other situations, dealing separately with different prime divisors can be helpful:
17 × 33 = 51 × 11 = 561 and 616 ÷ 28 = 308 ÷ 14 = 154 ÷ 7 = 22.
Powers of 2 and powers of 5 are particularly easy to work with:
8 × 17 = 4 × 34 = 2 × 68 = 136  (double, double, double 17)  
496 ÷ 8 = 248 ÷ 4 = 124 ÷ 2 = 62  (halve, halve, halve 496)  
112 × 125 = 56 × 250 = 28 × 500 = 14 × 1000 = 14000  (halve, halve, halve 112) 
Exercise 4
Calculate mentally using primes:
75 × 12, 714 ÷ 21, 17 × 55, 1325 ÷ 25, 1072 ÷ 16.
Once the prime factorisation of a number has been obtained, all its factors can quickly be written down. For example,
60 = 22 × 3 × 5;
so the complete list of factors of 60 is
22 × 3 × 5 = 60  21 × 3 × 5 = 30  1 × 3 × 5 = 15  
22 × 1 × 5 = 20  21 × 1 × 5 = 10  1 × 1 × 5 = 5  
22 × 3 × 1 = 12  21 × 3 × 1 = 6  1 × 3 × 1 = 3  
22 × 1 × 1 = 4  21 × 1 × 1 = 2  1 × 1 × 1 = 1 
and the total number of factors is
(2 + 1) × (1 + 1) × (1 + 1) = 12,
because the power of 2 in the factor can be 1, 2 or 22 (3 choices), the power of 3 can be 1 or 3 (2 choices), and the power of 5 can be 1 or 5 (2 choices).
Exercise 5
a  List all the factors of 256 and 210.  
b  Prove that a number is a square if and only if it has an odd number of factors.  
c  Find a site to play Kenken online. This puzzle requires one to think about all the ways to factor a given number. 
Prime factorisation and square roots
Once the index laws have been established for wholenumber indices, wholenumber square roots can be found from the prime factorisation of a number by halving the indices, provided that all the indices are even. For example,
784 = 24 × 72, so = 22 × 71 = 28.
Cube roots can be found by dividing the indices by 3:
216 = 23 × 33, so = 2 × 3 = 6,
and nth roots by dividing the indices by n.
In later years, surds can be simplified in a similar way,
360 = 23 × 32 × 51; so = 21 × 31 × = 6.
Exercise 6
List in index form all the whole number square roots, cube roots and higher roots of 230.
Prime factorisation and the HCF and LCM
The HCF and LCM of two whole numbers can be found from their prime factorisations. The method is easier once the zero index has been introduced. For example,
784 = 24 × 30 × 50 × 72 and 210 = 21 × 31 × 51 × 71.
The HCF is found by taking the smaller index of each prime, and the LCM by taking the larger index of each prime, so
HCF(784, 210) = 21 × 30 × 50 × 71 = 14
LCM(784, 210) = 24 × 31 × 51 × 72 = 11 760.
If the zero index has not been introduced when students study this material, then the situation where a prime is missing from one of the prime factorisations will need to be explained separately:
‘When a prime is missing from one prime factorisation, exclude the prime power from the HCF, but include the prime power in the LCM.’
Three general results about the HCF and LCM of two whole numbers
The last three parts of the next exercise are true for any two whole numbers. The calculations below can quickly be adapted for any pair of numbers, once their prime factorisations have been found.
Exercise 7
a Find the prime factorisations of 540 and 792
b Hence find the LCM and HCF of 540 and 792.
c Show that every common multiple is a multiple of the LCM.
d Show that every common factor is a factor of the HCF.
e Show that HCF × LCM = 540 × 720.
A concise layout for finding the HCF and LCM and both prime factorisations
The working on the right below shows a concise way to lay out the working for find the HCF and LCM of two numbers, using the same numbers 336 and 840 as in the example above:
We have also incidentally found the prime factorisations of 336 and 840,
336 = 24 × 3 × 7 and 840 = 23 × 3 × 5 × 7.
Exercise 8
Repeat the method with the numbers 7920 and 2376, including the prime factorisations.
In Years 9−10, we begin to factor polynomials into irreducible polynomials. Irreducible polynomials play a role in algebra analogous to the role of prime numbers in arithmetic. For example,
x2 − 9 = (x + 3)(x − 3).
Moreover, factoring of polynomials can be used to factor numbers. For example, 91 can be factored using the identity above,
91 = 102 − 32 = (10 + 3)(10 − 3) = 13 × 7,
The word ‘prime’ in school syllabuses is very definitely restricted to whole numbers. Students often ask, however, whether opposites of primes, like −5, can sensibly be called ‘primes’. It is quite possible to construct such a definition—a prime in the set of integers is an integer other than 0, 1 and −1 whose only integer factors are itself, its opposite, 1 and −1.
With this definition, every integer can be factored into prime integers, but the factorisation is only unique if primes in the factorisation are allowed to be replaced by their opposites. For example,
−60 = 2 × 2 × 3 × (−5) and −60 = 2 × (−2) × (−3) × (−5).
Primes and the complex numbers
The following factorisation of the prime 5 involving the imaginary number i shows that primes have to be defined quite differently when working with complex numbers:
5 = 4 + 1 = 22 − i2 = (2 + i)(2 − i).
Although primes were probably known to the Egyptians, the first known study of them occurs in the Elements of the Greek mathematician Euclid about 300BC. Euclid proved that every number can be factored uniquely into primes, and also proved that there are infinitely many prime numbers.
Eratosthenes described his sieve some 50 years later.
Two unsolved problems — Goldbach’s conjecture
and twin primes
In 1742, Goldbach famously conjectured that every even number greater than 2 is the sum of two prime numbers. For example,
4 = 2 + 2, 14 = 11 + 3, 104 = 97 + 7.
No mathematician has been able to establish whether or not this conjecture is true, making it one of the world’s longeststanding unsolved mathematical problems.
A prime pair consists of two primes with a difference of 2, like 3 & 5, 11 & 13, 71 & 73. Prime pairs stand out in the list of primes up to 100. Although the problem has been around for nearly 200 years, nobody has yet been able to establish whether there are infinitely many prime pairs, or whether the prime pairs form a finite list that terminates
with a ‘largest prime pair’.
Mathematics is full of unsolved problems. Wikipedia is a good place to find links to the present state of these and other outstanding problems. Both the Goldback Conjecture and the twin prime conjecture are thought to be true
There is no known algorithm for generating arbitrarily large prime numbers. Thus at any point in mathematical history, there has always been a ‘largest known prime’. In recent years, massive computing power has been used to find very large prime numbers, and at the time of writing, the largest known prime is 243 112 609 − 1, discovered on 23rd August, 2008, but see Wikipedia for further details and updates. Prime numbers of this type are called Mersenne primes, and the index of 2 in such a prime must be a prime number.
Exercise 9
a  Find the first number in the series 22 − 1, 23 − 1, 25 − 1, 27 − 1, … that is not a prime number, where the indices in the sequence are the primes in order.  
b  Use the difference of squares identity to prove that 2n − 1 is not prime when n is an even number greater than 2. (Slightly harder arguments are needed to prove that 2n − 1 is not prime when n is an odd composite number.) 
Applications of primes in security codes
One of the most important problems in everyday life is the secure transmission of information. Prime numbers are used in computing as a means of encoding information so that it can be kept secure. Although in theory, every whole number is a product of primes, in practice it is very hard to find the actual factorisation of a very large number, even using high speed modern computers.
For example, if you were given the number 410 000 137 and told to factor it, it would take you some time, even with a calculator, to find that it is in fact 4549 × 9013. Computer scientists exploit this fact to build codes that are very hard to break, using very large prime numbers.
Primes in sequence — Australia’s Fields Medal
The primes 3, 7, 11 form an arithmetic sequence of three primes. (An arithmetic sequence is a sequence that increases at each step by a common difference, which in this case is 4.) The primes 5, 11, 17, 23, 29 form an arithmetic sequence of five primes — in this case the common difference is 6. In 2004, Terence Tao from Australia and Ben Green from the UK proved that there are arithmetic sequences of primes of any given length. For this and other work, Tao in 2006 became the first Australian to be awarded a Fields Medal, which is considered to be equivalent to a Nobel Prize in Mathematics..
Exercise 10
Find an arithmetic sequence of six or more primes. The record at the time of writing is a sequence of 25 primes found in 2008, but see Wikipedia for more details.
Sequences of successive composite numbers
In contrast to these difficult questions about primes, the following exercise easily shows that there are sequences of arbitrary length consisting only of successive composite numbers.
Exercise 11
For any whole number n greater than 1, prove that the following is a sequence of n − 1 successive composite numbers:
n! + 2, n! + 3, …, n! + n.
Describe a million successive composite numbers.
Appendix — Proving the
fundamental theorem of arithmetic
Here is a proof of the prime factorisation theorem. As noted in the module, it is the uniqueness that is difficult to prove. Three initial lemmas are needed, each
of which is important in its own right.
Subtracting before finding the HCF
When finding the HCF of two numbers, it is often useful to subtract them. For example, when asked to find the HCF of 30 and 26, it is natural to subtract the two numbers and find instead the HCF of 26 and 4. The HCF of 26 and 4 is 2, and this is also the HCF of
30 and 26.
The following lemma justifies this procedure.
Lemma 1: Let a and b be whole numbers, not both zero, with a ≤ b. Then
HCF(a, b − a) = HCF(a, b).
Proof:  First, if d is a divisor of a and of b, then d is a divisor of b − a. Secondly, if d is a divisor of a and of b − a, then d is a divisor of b because a = b − (b − a). 
Euclid shows in his Elements how to continue this subtraction procedure, with the numbers getting smaller at each step, until one of the numbers is zero. Then the other number is the HCF.
For example, applying this process to 30 and 26:
30 − 26 = 4,  so HCF(30, 26) = HCF(26, 4).  
26 − 6 × 4 = 2,  so HCF(26, 4) = HCF(4, 2).  
4 − 2 × 2 = 0,  so HCF(4, 2) = HCF(2, 0). 
Hence the HCF of 26 and 30 is 2. Notice that the second step can be interpreted as subtracting 4 from 26 six times, or as dividing 26 by 4 and getting quotient 6 and remainder 2 − the two processes are, of course, identical. Similarly the third step is either two subtractions of 2, or a single division.
Starting from the secondlast step and working upwards, we can express 2 as a sum of integer multiples of the original numbers 30 and 26:
2 = 26 − 6 × 4 = 26 − 6(30 − 26) = 7 × 26 − 6 × 30.
This process is formalised in the following lemma to prove that it can be carried out in every case.
The lemma is only stated in the case where the HCF of the two numbers is 1, because that is all that is needed on the later proof, but the exercise following the lemma quickly extends it to the general case.
Lemma 2:  Let HCF(a, b) = 1, where a and b are whole numbers, not both zero, with a < b. ax + by = 1. 
Proof:  We prove the result using mathematical induction on b, a × 0 + b × 1 = 1. 
Thus we may assume that b ≥ 2, and since HCF(a, b) = 1, it follows that 0 < a < b. Hence a and b − a are nonzero whole numbers less than b, with HCF(a, b − a) = 1 by Lemma 1. Thus by the induction hypothesis we can choose integers x and y so that
ax + (b − a)y = 1.
Hence a(x − y) + by = 1, as required.
Exercise 12
Let a and b be two whole numbers, not both zero, with HCF d.
a Prove that the HCF of and is 1.
b Use part a and Lemma 2 to prove that there exist integers x and y so that ax + by = d.
Exercise 13
a  Use the Euclidean algorithm to find the HCF of 21 and 13, and explain why the algorithm, when applied to two successive numbers in the Fibonacci sequence, runs backwards through the Fibonacci sequence. 

b  Use your calculations to find integers x and y so that 21x + 13y = 1, and explain the position of x and y in the Fibonacci sequence. 
The prime number 5 is a divisor of 210. Our experiences of factoring numbers should convince us that whenever 210 is factored as a product, the prime 5 will be a divisor of one of the factors. For example, 5 is a divisor of one the factors in each factoring below:
210 = 21 × 10, 210 = 35 × 6, 210 = 2 × 105, 210 = 15 × 14.
The formal statement of this result is Lemma 3 below, which will provide us with the key step in proving the uniqueness of prime factorisation. Its proof requires Lemma 2.
Lemma 3:  Let p be a prime divisor of ab, where a and b are nonzero whole numbers. Then p is a divisor of a or p is a divisor of b. 
Proof:  Suppose that p is not a divisor of a. Then HCF(a, p) = 1 because p is prime, so by Lemma 2 we can choose integers x and y so that ax + py = 1. 
Multiplying both sides by b gives
abx + pby = b.
Hence p is a divisor of b, because p is a divisor of both ab and pby.
Exercise 14
Let p be whole number greater than 1. Prove that p is a prime number if and only if p is
a divisor of either a or b, for all whole numbers a and b such that ab is a multiple of p.
We now have the machinery necessary to prove both parts of the The Fundamental Theorem of Arithmetic.
Part 1
Every whole number n greater than 1 can be written as a product of primes.
Proof:  We prove the result using mathematical induction on n, if n is prime there is nothing to prove. Thus we can assume n is composite, so we can factor n as n = a × b, where a and b are whole numbers greater than 1 and less than n. 
Since a and b are less than n, it follows by the induction hypothesis that each is a product of primes. The product of these is a factorisation of n into primes, as required.
Part 2
This prime factorisation is unique, apart from the order of the prime factors.
Proof:  We proceed by contradiction and mathematical induction, the result being clear

Primes and Prime Factorisation answers
EXERCISE 1
a 121, 143, 169, 187 b 79, 83, 89, 97
EXERCISE 2
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31
EXERCISE 3
7 zeroes
EXERCISE 4
900, 34, 935, 53, 67
EXERCISE 5
a  Factors of 256 are 20= 1, 21= 1, 22, 23, 24, 25, 26, 27, 28 = 256 factors of 210 are 1, 2, 3, 5, 7, 2 × 3, 2 × 5, 2 × 7, 3 × 5, 3 × 7, 5 × 7, 2 × 3 × 5, 2 × 3 × 7, 3 × 5 × 7, 2 × 5 × 7, 2 × 3 × 5 × 7 

b  Each factor of a number is paired with another number. If the number is a square, the square root of the number is paired with itself. 
EXERCISE 6
= 215, = 210, = 26, = 25, = 23, = 22, = 2
EXERCISE 7
a  540 = 22 × 33 × 5 and 792 = 23 × 32 × 11.  
b  LCM = 23 × 33 × 5 × 11 = 11 880 and HCF = 22 × 32 = 36.  
c  A common multiple must be a multiple of 23, of 33, of 5, and of 11. Hence it is a multiple of their product, which is the LCM.  
d  A common factor cannot have as a factor any power of 2 greater than 22, or any power of 3 greater than 32, or any other prime. Hence it is a factor of 22 × 32, which is the HCF.  
e  LCM × HCF  = (23 × 33 × 5 × 11) × (22 × 32)  
= 25 × 35 × 5 × 11  
= 540 × 720 
EXERCISE 8
a 

EXERCISE 9
a 211 − 1 = 23 × 89
b 22n − 1 = (2n + 1)(2n − 1)
EXERCISE 10
7, 37, 67, 97, 127, 157
EXERCISE 11
n! + 2 is divisible by 2, n! + 3 is divisible by 3, …, n! + n is divisible by n. The sequence has length n − 1.
EXERCISE 12
a  Assume m ÷ and m divides . So, there exists k1 and k2 such that = mk1 and = mk2. Hence a = mk1d and b = mk2d. Therefore md divides both a and b. But md ≥ d. 

b  x + y = 1 and so ax +by = d. 
EXERCISE 13
a  21 = 13 × 1 + 8 13 = 8 × 1 + 5 8 = 5 × 1 + 3 3 = 2 × 1 + 1 2 = 1 × 1 + 1 The Fibonacci sequence is obtained by adding the two previous terms 

b  21 × 5 − 13 × 8 = 1; x = 5 and y =8 These are the two preceding terms. 
EXERCISE 14
The converse of Lemma 3 needs to be proved.
Suppose p  ab implies p  a or p  b
If p is not prime, it has prime factors, pi. Therefore p must divide one of these prime factors which is a contradiction.
The Improving Mathematics Education in Schools (TIMES) Project 20092011 was funded by the Australian Government Department of Education, Employment and Workplace Relations.
The views expressed here are those of the author and do not necessarily represent the views of the Australian Government Department of Education, Employment and Workplace Relations.
© The University of Melbourne on behalf of the International Centre of Excellence for Education in Mathematics (ICEEM), the education division of the Australian Mathematical Sciences Institute (AMSI), 2010 (except where otherwise indicated). This work is licensed under the Creative Commons AttributionNonCommercialNoDerivs 3.0 Unported License.
https://creativecommons.org/licenses/byncnd/3.0/