11
$\begingroup$

The question is:

Suppose $p_1<p_2<...<p_{15}$ is a sequence of prime numbers in arithmetic progression, with common difference $d$. Prove that $d$ is divisible by $2,3,5,7,11$ and $13$.

Let $p_n = a+(n-1)d$, by the definition of an arithmetic sequence. It is easy to see that $a$ is odd, and I can prove that $d$ is even easily enough.

I could then show $d$ is divisble by 3 by using the technique of letting $d=3x+c$, and $a=3y+d$, and by going through each possible value of c and d, d not equal to zero, I showed that the only solution where a and d were still prime was when $c=0$ or $3$.

While I could do the same thing for showing d is divisible by 5,7,11 and 13, this is a very laborious process that takes quite a long time. Are there any faster ways of proving this? I feel there is a way to do it using modular arithmetic, but I'm not very competent with regards to modular arithmetic, so I can't think of anything.

$\endgroup$
1
  • 1
    $\begingroup$ Maybe you could start with $p_n = p_1+(n-1)d$ instead of $p_n = a+(n-1)d$? $\endgroup$ Jul 23, 2015 at 16:36

3 Answers 3

3
$\begingroup$

Hint: if $q$ is a prime and $d$ is not divisible by $q$, then $p_i \equiv p_j \mod q$ only if $i-j$ is divisible by $q$. There are only $q-1$ nonzero residue classes mod $q$...

$\endgroup$
3
  • $\begingroup$ I think I have it now. Is it basically that since there are 15 coprime numbers, unless d is divisible by $q<15$, two numbers $p_i$ and $p_j$ must not be coprime, which is a contradiction? Is what I'm saying correct? $\endgroup$
    – Cataline
    Jul 23, 2015 at 17:46
  • 1
    $\begingroup$ @Cataline I think you've got the right high-level idea. But I think the proof requires some more intermediate steps. Here's the basic idea. If two numbers $x$ and $y$ are coprime, then one of the numbers in the sequence $a, a + x, a + 2x, ..., a + yx$ must divide y. Why? Well, you need to turn to modular arithmetic. You can see that no two distinct numbers in the above sequence can be congruent (mod $y$). Then by the pigeonhole principle, and the fact that there are exactly $y$ congruences (mod $y$) i.e. $\{0, 1, ..., y-1\}$, then one of the congruences is $0$, i.e. the number divides $y$. $\endgroup$ Jul 24, 2015 at 12:52
  • 1
    $\begingroup$ Note that a direct consequence of this is, again for coprime $x$ and $y$, that at least $2$ numbers in the sequence $a, a + x, a + 2x, ..., a + 2yx$ must divide $y$. And you can use this to blast the cases of $2, 3, 5, 7$ because double each number is still less than 15. $\endgroup$ Jul 24, 2015 at 12:56
2
$\begingroup$

First we show that $d$ divides all of $2, 3, 5, 7$. Take some $q$ in the set $\{2, 3, 5, 7\}$. Since $2q < 15$ we know that there is a sub-sequence of terms of length $2q$ in our arithmetic progression. Now, if $q$ does not divide $d$, because $q$ is a prime, $d$ and $q$ must be coprime. So there must be two numbers in our progression of $2q$ terms that divide $q$. Which contradicts the fact that all are distinct primes. Call this result (1).

Now, for the cases of $q$ in the set $\{11, 13\}$. If $q$ divides $d$, then we're done. So suppose it doesn't, towards a contradiction. Well, then, we again have the case that $q$ and $d$ must be coprime. Because $q < 15$, there is always a sub-sequence of $q$ terms in our sequence. And because $d$ and $q$ are coprime, one of these terms must divide $q$. But being prime, it must actually equal $q$. Now, suppose this $q$ appears as the first term in our main sequence i.e. $p_1 = q$. Then we know there is a sub-sequence of $14$ terms in sequence to the right, and so because of coprime $d$ and $q$ one of them must also equal $q$, which is a contraction. So there is always a term to the left of $q$, call it $p_i$. Now, $p_i$ is positive, and we have that $p_i + d = q$ by our definition of arithmetic progression. And $d$ is positive, by our assumption. So $d < q$. But we know that $q \leq 13$. So $d < 13$. But we know from our earlier result (1) that $d$ divides $2, 3, 5, 7$. So $2 \times 3 \times 5 \times 7 \leq d$. Which implies $2 \times 3 \times 5 \times 7 < 13$. This is clearly false.


Note: we only needed 14 terms in our arithmetic progression for this proof to work. This result can be generalised: given any progression of $p + 1$ or more primes, for some prime $p$, then the common difference $d$ of the progression divides all primes less than or equal to $p$. For the first few primes $2, 3, 5, 7$ we need to tweak the above proof a bit. In the the general case, we rely on a lower bound for the primorial (product of all primes up to a given prime). The bound is $2^{\frac{n(n+1)}{2}}$ for some prime $p \geq 2^{n}$. This bound can be derived from Bertrand's postulate.

$\endgroup$
1
$\begingroup$

The $p_i$ are given by $p_1 = a + nd$ for $a = p_1 - d$ and $n = 1, \dots, 15$. Suppose $p \leq 13$ is prime and $p\nmid d$. Then there exists some $d'$ with $d'd\equiv 1\pmod{p}$. There exists some $0 < m < p$ with $m\equiv -ad' \pmod{p}$. Then $p_m = a + md \equiv 0\pmod{p}$. But $p_m$ is prime, so $p_m = p$.

Now note that the only three-term arithmetic progressions among primes less than $15$ are $3, 5, 7$ and $3, 7, 11$. It follows that if $p_m = p$, then $p + m < 15$. But then $p_m$ and $p_{m+p} = p_m + pd$ are both divisible by $p$, contradicting the fact that the $p_i$ are prime.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .