The Improving Mathematics Education in Schools (TIMES) Project

return to index

Primes and prime factorisation

Number and Algebra : Module 16Years : 7-8

June 2011

PDF Version of module

Assumed knowledge

• Fluency in multiplication and division are essential.
• Divisibility tests, particularly by 2, 3, 5 and 11, are useful.
• Index notation with whole-number indices, and square roots, are required.
• The Highest Common Factor (HCF) and The Lowest Common Multiple (LCM), and cube and possibly higher roots, are required for the last two content items, which are
  often studied a little later than prime factorisation.

Motivation

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.

Content

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:

• the prime numbers 2, 3, 5, 7, 11, …, which cannot be factored into smaller numbers,
• the composite numbers 4, 6, 8, 9, 10, …, which can be factored into the product
  of two smaller numbers.

Prime numbers and composite numbers need to be defined rather carefully:

• A prime number is a whole number greater than 1 whose only whole number factors are itself and 1.’
• A composite number is a whole number greater than 1 that is not a prime number.

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.

Primes and rectangular arrays

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:

1. Every whole number greater than 1 is either prime or can be written as a product
   of prime numbers.
2. This prime factorisation is unique, apart from the order in which we write the
   prime factors.

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 K-10 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.

Proof by 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.

The Sieve of Eratosthenes

Here is a systematic way of writing down all the prime numbers, and all the composite numbers, up to 100.

1. Write down all the whole numbers up to 100.
2. Cross out 0 and 1 — they are exceptions.
3. Circle the next number 2, and then cross out every multiple of 2
4. Circle the next number not crossed out (which is 3), and then cross out multiples of 3.
5. Continue until all numbers are either circled or crossed out.

The 25 circled numbers are the primes up to 100, and the 74 crossed-out 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.

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:

• When testing whether a whole number n is prime, it is sufficient to test divisibility by
  all the primes up to .

Any number n that is to be tested in school mathematics should thus yield to the following plan of attack:

• Use the standard divisibility tests to test n for divisibility by the primes 2, 3, 5 and 11. These divisions tests are presented in the module, Multiples, Factors and Powers.
• Then use division to test divisibility by the remaining primes 7, 13, 17, 19, … up to .

It is usual to write the prime factorisation in index form with the primes in increasing order,

60 = 22 × 3 × 5.

Primes and mental arithmetic

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)

 

listing factors of a number

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).

Prime factorisation and square roots

Once the index laws have been established for whole-number indices, whole-number 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.

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.

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:

• At each step divide by a common prime factor, placed on the left.
• Stop when the two quotients are relatively prime.
• The product 23 × 3 × 7 = 168 of the primes on the left is the HCF.
• The product 168 × 2 × 5 = 1680 of the HCF and the numbers along the bottom is the LCM.

We have also incidentally found the prime factorisations of 336 and 840,

336 = 24 × 3 × 7 and 840 = 23 × 3 × 5 × 7.

Links forward

Irreducible polynomials

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,

Primes in the set of integers

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).

History and applications

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 longest-standing 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

The largest known prime

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.

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..

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.

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).

The Euclidean algorithm

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 second-last 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. Then there exist integers x and y so that ax + by = 1.

Proof:

We prove the result using mathematical induction on b, the result being trivial if b = 1 because then 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 non-zero 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.

Prime divisors of a product

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 non-zero 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.

Proving the theorem

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 for all prime numbers. Let n be the smallest number that has two distinct prime factorisations n = p1 … pr and n = q1 … qs, where p1, …, pr are primes (not necessarily distinct), and q1, …, qs are primes (not necessarily distinct). We can write n as a product n = p1 × (p2 … pr), where p2 … pr has a unique prime factorisation by the induction hypothesis, because p2 … pr < n. Since p1 is a prime divisor of n = p1 × (p2 … pr), it follows by Lemma 3 that either q1 is a divisor of p1 or q1 is a divisor of p2 … pr. If q1 is a divisor of p1, then q1 = p1. If, on the other hand, q1 is a divisor of p2 … pr, then q1 is one of the primes p2, …, pr, because p2 … pr has a unique prime factorisation. In either case, q1 is one of the primes p1, …, pr, and after reordering, we may assume that q1 = p1. Hence = has two distinct prime factorisations = p2 … pr and = q2 … qs, which is a contradiction because < n.

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

Hence HCF = 23 × 32 × 11 = 792 and LCM = 792 × 10 × 3 = 23 760. Also 7920 = 24 × 32 × 5 × 11 and 2376 = 23 × 33 × 11.

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 2009-2011 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 (ICE-EM), the education division of the Australian Mathematical Sciences Institute (AMSI), 2010 (except where otherwise indicated). This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
https://creativecommons.org/licenses/by-nc-nd/3.0/