Copyright © University of Cambridge. All rights reserved.
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 |
Where the top row is the number itself, and then each row shows
what this would equal if $p=0, 1, 2$ mod $3$. As we can see, there
is always a zero in each row, and so in any sequence of $3$ numbers
where the difference is $2$, one will always divide by three, and
so cannot be prime. So as $3$ itself is the only prime number
divisible by $3$, the only AP of difference $2$ must include $3$,
and so the only prime AP of common difference $2$ is $3, 5, 7$
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$.