Prime sequences
This group tasks allows you to search for arithmetic progressions
in the prime numbers. How many of the challenges will you discover
for yourself?
Age
16 to 18
Challenge level
Problem
In 2004 an exciting new result was proved in Number Theory by two young mathematicians Ben Green and Terence Tao. They proved that if you look in a long enough list of the prime numbers then you will be able to find numbers which form an arithmetic progression containing as many numbers as you choose! In this question we explore some of the interesting issues surrounding arithmetic progressions of prime numbers.
An $AP-k$ sequence is $k\geq 3$ primes in arithmetic progression. See examples
This problem involves several linked parts leading up to a final challenge. Try some of the earlier questions to gain insights into the final challenge. These can be attempted in any order. You might find that you naturally ask yourself questions which are found later in the list of questions and you might find that one part helps in the consideration of another part. Of course, you are welcome to go straight to the final challenge. However, you might also wish to start with one of the earlier challenges and see how many of the other challenges you naturally discover whilst exploring the underlying mathematical structure.
| Consider some of these three questions first: | |
| Question A | |
| Question B | |
| Question C | |
| Next consider some of these three questions: | |
| Question A | |
| Question B | |
| Question C | |
| Now consider some of these three questions: | |
| Question A | |
| Question B | |
| Question C | |
When you have thought about some of the previous problems you might like to try the final challenge
In doing these problems you might like to see this list of primes
Getting Started
Think about the remainder when dividing each term by various prime numbers.
We recommend this page for further reading.
Student Solutions
Amy from Birmingham answers the first set of questions.
Can you find an arithmetic progression of four primes?
$5, 11, 17, 23$ is an arithmetic progression starting at $5$ with a difference of $6$.
This can also be extended to a progression of $5$ primes by $5, 11, 17, 23, 29$
How many prime APs beginning with $2$ can you find?
There can't be any prime APs beginning with $2$ because $2$ is the only even prime number. So the arithmetic progression difference can not be an even number. So if you add an odd number on to get to a prime, say add $2k+1$ where $k$ a whole number, so $2+2k+1 = 2k+3$ is a prime number. Then if we add on the common difference again to get $p+2k+1 = 2k+3+2k+1 = 4k+4 = 4(k+1)$ which is an even number and so cannot be a prime number. So APs beginning with $2$ can only have $2$ components, and so are not an AP.
How many other arithmetic progressions of prime numbers from the list of primes below can you find?
We know from above that they must have common differences of even numbers. Eg.
$3, 5, 7$ - difference 2
$3, 7, 11$ - 4
$3, 11, 19$ - 6
$3, 13, 23$ - 10
$3, 17, 31$ - 14
$3, 23, 43$ - 20
$3, 31, 59$ - 28
$3, 37, 71$ - 34
$3, 41, 79$ - 38
and so on. So there are lots and lots.
The only progression with common difference $10$ is $3, 13, 23$ because one of them will always divide by $3$. We know the digits in a number that divides by $3$ will always add up to $3, 6$ or $9$ so if all the digits in a number $p$ add up to $k$ then $p+10$ adds up to $k+1$ and $p+20$ adds up to $k+2$, and one of $k, k+1, k+2$ will always be divisible by $3$ as three consecutive numbers will always have one that divides by $3$.
Good answers Amy, and well done on developing your ideas to show that $3, 13, 23$ is the only prime AP with common difference $10$. Can anyone think of a more concise way of expressing Amy's ideas? Can anyone find any more of the many prime APs?
.
Clark managed to complete the next few using modular arithmetic. If you are unfamiliar with this area of maths you might want to read the article Modular Arithmetic first.
Why is $3, 5, 7$ the only prime AP with common difference 2?
Because one of them will always divide by $3$. A sequence of numbers $p, p+2, p+4$ will always have one number which divides by three. If we use modular arithmetic, and take $p, p+2, p+4$ modulo 3 then we have $3$ options.
| p | p+2 | p+4 |
| 0 | 2 | 1 |
| 1 | 0 | 2 |
| 2 | 1 | 0 |
What is the maximum length of a prime AP with common difference 6?
Using a similar method to above, we can show that a sequence of $5$ numbers of difference $6$ will always have a member that is divisible by $5$. Looking at a sequence $p, p+6, p+12, p+18, p+24$ and putting into a table as above, so a looking at what each sequence would be equal to modulo $5$ given that $p=0,1,2,3,4$
| p | p+6 | p+12 | p+18 | p+24 |
| 0 | 1 | 2 | 3 | 4 |
| 1 | 2 | 3 | 4 | 0 |
| 2 | 3 | 4 | 0 | 1 |
| 3 | 4 | 0 | 1 | 2 |
| 4 | 0 | 1 | 2 | 3 |
So the only sequence of
length $5$ with common difference $6$ is the one including $5$, as
that is the only prime divisible by $5$. So $5, 11, 17, 23,
29$
Otherwise the length of
all sequences with common difference $6$ will be $4$ or less.
Eg, $41, 47, 53, 59$ or
$61, 67, 73, 79$
Claim: If the common diference of a prime AP is $N$ then the maximum length of the prime AP is $N-1$
I have noticed a pattern in the examples above, that is the longest sequence involves starting on the prime number that is the length of the sequence. Compiling a similar table, I shall show that the sequence $p, p+N, p+2N, ... , p+(N-3)N, p+(N-2)N$ will always have one component that divides by $N-1$, so if a sequence of this length exists, it must start on the prime $N-1$. This also relies on the sequence $p, p+N, ... , p+(N-2)N$ being all primes, which is unlikely. But supposing this to be true, I shall continue. The table, as above, shows what each of $p, p+N, ... , p+(N-2)N$ would be equal to modulo $N-1$ if $p=0, 1, 2, ... , N-2$
| p | p+N | p+2N | ... | p+(N-3)N | p+(N-2)N |
| 0 | 1 | 2 | ... | N-3 | N-2 |
| 1 | 2 | 3 | ... | N-2 | 0 |
| 2 | 3 | 4 | ... | 0 | 1 |
| ... | ... | ... | ... | ... | ... |
| N-3 | N-2 | 0 | ... | N-5 | N-4 |
| N-2 | 0 | 1 | ... | N-4 | N-3 |
And so we can see, as
before, that one number in the sequence is always equal to zero mod
$N-1$, and so is divisible by $N-1$.
So if a prime AP of
length $N-1$ with common difference $N$ exists, it must start on
the prime number $N-1$, and no AP longer than $N-1$ can
exist.
What is the maximum length of a prime AP with
common difference 10?
I shall build on Amy's
description in the $3rd$ question. Using my table method with
modulo 3:
| p | p+10 | p+20 |
| 0 | 1 | 2 |
| 1 | 2 | 0 |
| 2 | 0 |
1
|
Which says exaclty what
Amy noticed, that with any starting prime, one member of the
sequence starting at $p$ with common difference $10$ will always
divide by $3$. So the only AP of length $3$ will be when the
starting prime is $3$. So $3, 13, 23$
What is the maximum length of a prime AP with
common difference 100, 1000, 10000?
Similarly as above, if
they exist the longest will be of length $3$, and start at the
number $3$. By writing $100=10^{2}$ and $200=2\times 10^{2}$ and
similarly for $1000$ and $10000$, then I can compile the table as
usual considering modulo 3.
Because $99, 999, 9999$
are all divisible by three then
| p | p+$10^{n}$ | p+$2\times 10^{n}$ |
| 0 | 1 | 2 |
| 1 | 2 | 0 |
| 2 | 0 | 1 |
for all $n$ whole
numbers. In this case, we are just considering $n=2, 3, 4$. So we
have that if a prime AP of length $3$ exists, it must start at $3$,
for reasons discussed earlier. Now to check that in the cases $n=2,
3, 4$ these exist.
For $n=2$, common
difference is $100$, so the AP would need to be $3, 103, 203$ but
$203=29\times 7$ and so this AP does not exist.
For $n=3$ the common
difference is $1000$, so the AP would be $3, 1003, 2003$ but
$1003=17\times 59$ so AP does not exist.
And for $n=4$ the common
difference is $10000$, so the AP would need to be $3, 10003,
20003$, but $10003=7\times 1429$, and so the AP does not
exist.
And so there does not
exist a prime AP with common difference $100, 1000$ or
$10000$
What are the possible lengths of prime APs with
common difference $2p$, where $p$ is prime?
Case 1) $p=3$
When $p=3$ then $2p=6$
and this case was discussed above under question $5$. The possible
lengths of prime APs are $3, 4$ or $5$/
Case 2) $p> 3$
Suppose we are starting
with a number $n$ in the sequence. Then the sequence will be $n,
n+2p, n+4p, n+6p, ...$. I claim that the sequence can only ever be
$3$ long.
I shall divide into 2
cases, when $2p-1$ is divisible by $3$ and when $2p+1$ is divisible
by $3$. I do not need to consider $2p$ divisible by $3$ as this
cannot occur, as $2p$ has prime factorisation $2p = 2 \times
p$
Case 2 A) $2p \equiv 1$
mod $3$ - eg, $p=5, 11$
Then the table of
possible progressions modulo $3$ is
| n | n+2p | n+4p |
| 0 | 1 | 2 |
| 1 | 2 | 0 |
| 2 | 0 |
1
|
And so as before we see
there is always one number divisible by $3$, and so the only
possibility is starting at $3$ and having three members in the
sequence.
Case 2 B) $2p \equiv 2$
mod $3$ - eg, $p=7, 13$
| n | n+2p | n+4p |
| 0 | 2 | 1 |
| 1 | 0 | 2 |
| 2 | 1 | 0 |
And as we would expect,
the sequence of three numbers must contain one that is divisible by
three, and so the only possibility are ones starting at $3$
Putting these together,
for all primes $> 3$ the prime AP with common difference $2p$
starts at $3$ and is three terms long, if that.
For example when $p=11,
2p=22$ and as $25$ not prime, this has no APs as we demanded the
length be longer than $2$.
This leads me to claim
that for prime APs of length longer than $3$ to exist, then the
common difference must be a multiple of $6$, so that if it is
started on a prime $> 3$, it shall never pass through a multiple
of $3$. Though it may obviously pass through other non prime
numbers, and so not exist for all multiples of $6$.
Well
done Clark! Some excellent proofs and clear points. I particularly
like that you have continued your investigation and have summed up
your findings with a new claim. Can anyone think how to prove or
disprove Clark's claim?
Can you
see how Clark's claim is linked into the final question? Can anyone
link them and prove one with the other? Can anyone prove outright
either claim?
Good
luck!
.
Prove
that if an AP-$k$ does not begin with the prime $k$, then the
common difference is a multiple of the primorial $k$#$=2 \cdot 3
\cdot 5 \cdot ... \cdot j$, where $j$ is the largest prime not
greater than $k$.
Teachers' Resources
Why do this problem?
This problem involves a significant 'final challenge' which is
broken down into a sequence of three groups of mini-challenges. The
mini-challenges are not arranged in any particular order within
each group and the problem is structured such that students are
likely to 'discover' some of the mini-challenges for themselves as
they strive to solve other mini-challenges.
These notes are designed for classes who are able to work in
groups.
At the outset all challenges are hidden to the learner to
maximise the chance of discovery for the learners.
The purpose of this is two-fold: first to scaffold learners to
help them solve a difficult challenge; second to show that
mathematics is a natural subject where certain questions naturally
arise through the consideration of other questions. This will
firstly help students to structure their mathematical thinking and
secondly to help them to realise that mathematics is not externally
or meaninglessly imposed.
Possible approach
There are three groups of 3 mini-challenges and the final
challenge. Leave these all hidden to begin with.
Throughout the challenge the focus will be on constructing
clear, concise proof and on thinking of possible extension
questions.
Very able students might wish to start on the Final Challenge,
but it will be good to give them a single mini-challenge and see
where their thinking and invention takes them. Indeed, the best and
most inventive students might even 'discover' the final challenge
for themselves.
It is suggested that the following approach be taken
1) (10 minutes) Students individually given one of the first
mini-challenges to think about and work on. Spread the different
mini-challenges amongst the group -- don't allow students to see
any of the other challenges or talk about this with their
neighbours. Students are to think about their challenges and
explicitly write down any other thoughts or questions that arise.
Encourage those that think they have an answer to construct the
clearest proof possible or to think about possible
extensions.
2) (5 minutes) A selection of students to describe their
challenge, proofs and other questions arising. It is likely that
some of the questions arising will be the problems other students
were working on directly.
3) (10 minutes) Ask the class to organise themselves in pairs
so as to get insight into solving their mini-challenge or proposed
extensions. It might be that students pair with people working on
the same mini-challenge or pair with someone who was thinking about
a related problem. Give the pairs a new challenge from the second
grouping to work on.
4) Repeat step 2 and group into 4s, whilst giving the fours a
mini-challenge from the third grouping to work on.
5) Throughout encourage the class to propose their own
extension questions.
At some point students might solve their challenges or pose
the final challenge for themselves. When appropriate move the
discussion onto the construction of a clear proof of the final
challenge. This will be ideally a group effort.
Key questions
As you think about your mini-challenge, what questions and
extensions arise?
Complete the sentence: I am finding this task difficult
because ...
Complete the sentence: I wonder if ....
Complete the sentence: I would be more able to solve my
challenge if I knew ...
Can you explain your proof clearly in words?
Possible extension
Solution of the final challenge on its own is a tough
challenge.
Possible support
This task is designed for group work -- encourage groups not
to move on until all in the group understand.
Some students might be uncomforable with posing their own
questions or verbalizing their difficulties. Encourage an
atmosphere where all questions and difficulties are valid.