Common Divisor

Can you find out what numbers divide these expressions? Can you prove that they are always divisors?

Age

14 to 18

Challenge level

Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving

Being curious Being resourceful Being resilient Being collaborative

Problem

In this problem you will get the chance to discover some surprising results. Can you prove that they are always true?

Part A

Evaluate $1^3 - 1$, $2^3 - 2$, $3^3 - 3$ and $4^3 - 4$.

What is the largest integer that divides all of these?

Can you prove that it divides $n^3 - n$ for all positive integers $n$?

You should find that your answers are always multiples of 6.

If a number is divisible by 6, which two prime numbers must it be divisible by?

To prove that the expression is always divisible by these two prime numbers, you could start by factorising $n^3 - n$.

Part B

Evaluate $1^5 - 1^3$, $2^5 - 2^3$, $3^5 - 3^3$ and $4^5 - 4^3$.

What is the largest integer that divides all of these?

Can you prove that it divides $n^5 - n^3$ for all positive integers $n$?

Work out which numbers you need to be able to divide by.

Factorising the general expression might be helpful again.

You can consider the cases $n$ even ($n=2k$) and $n$ odd ($n=2k+1$) separately.

Part C

Find the largest integer which divides every member of the following sequence: $$ 1^5-1,\ 2^5-2,\ 3^5-3,\cdots\, n^5-n.$$

Work out which prime numbers you need to be able to divide by.

Factorise the expression. Can you show that the expression can be divided by these prime numbers?

You can consider different cases, perhaps starting with $n$ being a multiple of 5 $(n=5k)$.

Part D

Show that $2^{2n} -1$ can always be divided by three.

You can try some values of $n$ and see what happens.

Factorising might again be helpful!

You can consider the expression $2^n$ and what this can be divided by.

Did you know ... ?

Although number theory - the study of the natural numbers - does not typically feature in school curricula it plays a leading role in university at first year and beyond. Having a good grasp of the fundamentals of number theory is useful across all disciplines of mathematics. Moreover, problems in number theory are a great leisure past time as many require only minimal knowledge of mathematical 'content'.

We are very grateful to the Heilbronn Institute for Mathematical Research for their generous support for the development of this resource.

Student Solutions

Part A: What is the largest integer that divides $1^3 - 1$, $2^3 - 2$, $3^3 - 3$, $4^3 - 4$, $n^3 - n$?

Note that in their solutions, some people use the notation $3|12$ to mean "3 is a multiple of 12" or "3 divides 12"

Wiktor from LAE Tottenham in the UK, Mahdi from Mahatma Gandhi International School in India, Nikita from Jersey College for Girls in Jersey and David sent in similar answers. This is Wiktor's work:

Part B: What is the largest integer that divides $1^5 - 1^3$, $2^5 - 2^3$, $3^5 - 3^3$,$4^5 - 4^3$ and $n^5 - n^3$?

Nikita, David, Wiktor and Mahdi all began in the same way. This is Nikita's work:

Mahdi's proof is very similar, but David proved the statement without writing out the cases algebraically. David wrote:

$n^5-n^3 = n^3(n+1)(n-1)$

If $n$ is even, $8|n^3$

If $n$ is odd, then one of $(n-1), (n+1)$ is divisibly by $4$ and the other is divisible by $2$. So $(n-1)n^3(n+1)$ is necessarily divisible by $8.$

Part C: Find the largest integer which divides every member of the following sequence: $$ 1^5-1,\ 2^5-2,\ 3^5-3,\cdots\, n^5-n.$$

Nikita, David and Mahdi's work all begins in the same way. This is Mahdi's work:

David considered five cases without writing them out algebraically:

$n^5-n=(n-1)n(n+1)(n^2+1)$

If $n\equiv 0 \text{ (mod 5})$ then $5|n$

If $n\equiv 1 \text{ (mod 5})$ then $5|n-1$

If $n\equiv \pm 2 \text{ (mod 5})$ then $5|n^2+1$ (which means $n\equiv 2 \text{ (mod 5})$ or $n\equiv 3 \text{ (mod 5)}$

If $n\equiv 4 \text{ (mod 5})$ then $5|n+1$

Nikita used the same idea but on the unfactorised expression:

Wiktor used proof by induction:

Wiktor has shown that whenever $k^5 - k$ is a multiple of $5$, $(k+1)^5 - (k+1)$ is also a multiple of $5$. This means that for each term in the sequence that is a multiple of $5$, the following term is also a multiple of $5$. Since the first few terms are multiples of $5$, this means that all the terms in the sequence must be multiples of $5$.

Part D: Show that $2^{2n} -1$ can always be divided by three.

Wiktor, Mahdi and Sahin sent in very similar proofs. This is Sahin's work:

Nikita and Wiktor sent in a different proof. This is Nikita's work:

(for all positive integers $n$)

David sent in a different proof, using modular arithmetic. My maths teacher would have said it's like using a sledgehammer to crack an egg:

Teachers' Resources

Why do this problem?

This problem can be used to introduce students to number theory and to how we can prove some divisibility facts. They offer an intriguing context for applying standard algebraic techniques.

Possible approach

This activity featured in an NRICH Secondary webinar in March 2021.

For these problems it is a good idea for students to start by working through some numerical examples (perhaps with a calculator for the later ones!).

This article on divisibility tests might be useful, and you could use Dozens as a warm up task.

Students could be asked how they can tell that a number is divisible by 6. For example, which of the following must be divisible by 6 (without actually dividing it!):

$$2574, 8961, 5972, 8981$$

They can also be asked to create a 6 digit number which must be divisible by 6. They can then be asked which numbers we need to be able to divide $n^3 - n$ by to show that it is divisible by 6. Factorising and considering the factors is helpful.

For the second two problems, students can be encouraged to write the common divisor as a product of prime numbers.

Key ideas

Problem 1: $n^3-n$

Students can find the first few values of $n^3 - n$ and see what they notice. They may possibly spot that they are even before they spot that they are all multiples of 6. Students could be asked what being divisible by 6 means. For example, can they decide whether 1428 is divisible by 6 without dividing it? (They may need reminding of how they can show a number is divisible by 3 by considering the digit sum of the number).

They could think about breaking 6 down into a product of prime factors. Students may need to be given a nudge into considering factorisation, but once they have done so they could be asked what the notice about the individual parts of this factorisation. They could substitute some values into $(n-1)n(n+1)$ first if they are unsure. They could then be asked what they know about three consecutive numbers, in particular what we know about multiples of 2 and 3.

Another approach is to consider the cases $n=2k$ and $n=2k+1$ ($n$ is even and odd) to show that the expression $n^3 - n$ has a factor of 2, and $n=3k$, $n=3k+1$, $n=3k+2$ ($n$ is a multiple of 3, or one more or two more than a multiple of 3) to show that $n^3 - n$ has a factor of 3. This is easier to do if they consider the factorised version $(n-1)n(n+1)$.

Problem 2: $n^5-n^3$

The second problem draws on the ideas of the first. This time the expressions can be divided by 24 so students need to show that it can be divided by 3 and by $2^3$. The factor of 3 can be argued from the fact that we have a product of three consecutive numbers, but the factor of $2^3$ is a little trickier. One option is to consider $n$ even and $n$ odd separately.

Problem 3: $n^5-n$

For the third problem the factorisation is a little trickier and students might need a prompt to factorise completely. The factors of 2 and 3 follow in a similar way to before. Following on from the previous ideas, students could consider the cases $n=5k$, $n=5k+1$ etc. to show that the expression always has a factor of 5.

Problem 4: $2^{2n}-1$

For the last problem, factorising gives two expressions which differ by 2. Inserting the in-between number and considering the prime factors of this will help to solve the problem.

Possible support

Students could start by working on Take Three from Five where they are introduced to the fact that numbers can be written as a multiple of 3, 1 more than a multiple of 3 or 2 more than a multiple of 3.

Students could start by considering $n^2 + n$ and showing that this is always even. The could also show that $n(n+1)(n+2)$ always has a factor of three, possibly by considering $n=3k$, $n=3k+1$ and $n=3k+2$. The fact that in any three consecutive numbers there is always a multiple of three is useful in all of the four problems.

For students who find it difficult to see that any number can be written as one of $3k, 3k+1, 3k+2$ they could consider the three following sequences: $$1, 4, 7, 10, ...$$ $$2, 5, 8, 11, ...$$ $$3, 6, 9, 12, ... $$

Finding the formulae for these three sequences shows that any number has one of the three different forms.

Or search by topic

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners