2
$\begingroup$

How do I answer this question?

Find the largest value of $d$, and the corresponding value of $k$, for which the following theorem is true:

If all of $p, p + 2, p + 6$ and $p + 8$ are prime, then $p \equiv k \pmod d$ except in one case.

Find the value of $p$ that does not satisfy this theorem, then prove that the theorem is true in all other cases.

Thanks for any help :)

  • 0
    Oh, thats alright then.2012-05-14

2 Answers 2

5

Consider $p$, $p + 2$, $p + 6$, and $p + 8$ mod $q$ for primes $q$.

$q=2$: Since $p$ and $p+2$ are prime, we get $p\equiv 1 \bmod 2$.

$q=3$: Since $p+8$ is prime, we get $p\equiv 2 \bmod 3$.

$q=5$: Since the others are prime, we get $p\equiv 1 \bmod 5$ unless $p=5$.

That should get you started. Use the Chinese Remainder Theorem to reduce all modular restrictions to one.

  • 0
    @ChaoHir, the first two restrictions can be combined into one: $p\equiv 5 \bmod 6$. This is the essence of the [Chinese Remainder Theorem](http://en.wikipedia.org/wiki/Chinese_remainder_theorem) in general. But you can do it by hand: $p=2a+1 \implies 2a\equiv 1 \bmod 3 \implies a\equiv 2 \bmod 3 \implies a=3b+2 \implies p=6b+5$.2012-05-11
3

First, a petty logical point, since I am petty and have a background in logic. The theorem says that something or other happens at all primes except one. Then we are asked to find the prime that does not satisfy the theorem. The prime $5$ will turn out to be the weird one. However, it cannot be said not to satisfy the theorem, since the statement of the theorem has the existence of an exceptional prime built in!

But let's get to the real problem. First we find a small number of examples of positive integers $p$ such that $p$, $p+2$, $p+6$, and $p+8$ are all prime.

It is easy to verify that $p=5$ and $p=11$ work. By looking at congruences in the manner described by lhf, we can see that any other $p$ must be congruent to $11$ modulo $30$. Then a short search shows that $p=101$ and $p=191$ work.

It will turn out that a longer search is necessary in order to answer the question fully. We are looking for prime quadruplets. By going to the link, or by doing our own computation, we find that the next two prime quadruplets are $821,823,827,829$ and $1481,1483,1487,1489$.

The solution described by lhf shows that all prime quadruplets $p,p+2,p+6,p+8$, apart from $5, 7, 11, 13$ must have $p$ of the shape $30n+11$. But, in the language of the problem, does this show that $30$ is the largest $d$ for which there is a constant $k$ such that $p\equiv k\pmod{d}$? Note that $11=(90)(0)+11$, and $101=(90)(1)+11$, so the largest $d$ must divide $90$. But could the largest $d$ be $90$?

Compute. We find that $191=(90)(2)+11$. Next we find that $821=(90)(9)+11$. However, the pattern breaks at $1481$, since $1481=(30)(49)+11$. The largest $d$ must divide $90$, and must also divide $(30)(49)$. So it cannot be greater than $30$. However, we know that every $p$ except $5$ is congruent to $11$ modulo $30$, so $d=30$, and we can take $k=11$.

  • 0
    If $p$ congruent to $1$ mod $5$, then congruent to one of $1$, $6$, $11$, $16$, $21$, or $26$ mod $30$. If $p\equiv -1\pmod{6}$ then $p$ is congruent to one of $6$, $11$, $17$, $23$, or $29$ mod $30$. Note that $11$ is the only number in both lists.2012-05-12