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
    Is there any reason you want to delete your question after getting several good answers? Please note that this site helps everyone online - even though you've got the answer now, if someone had the same question as you, we'd want them to be able to see the answer here as well.2012-05-13
  • 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
    Sorry, but I don't understand by what you mean for primes q? And what is the chinese remainder theorem?2012-05-11
  • 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
    Btw, I'm confused as how you know from lhf's comment that any other p must be congruent to 11 modulo 30?2012-05-12
  • 0
    Take $p>5$. We cannot have $p\equiv 0\pmod 5$. We cannot have $p\equiv 2\pmod 5$, else $p+8$ divisible by $5$, so not prime. We cannot have $p\equiv 3\pmod{5}$, else $p+2$ not prime. Cannot have $p\equiv 4\pmod{5}$, else $p+6$ not prime. Leaves $p\equiv 1\pmod{5}$ as only possibility. Work similarly mod $6$. We cannot have $p\equiv 1\pmod{6}$, else $p+2$ is divisible by $3$. So $p\equiv -1\pmod{6}$. From $p\equiv 1\pmod{5}$ and $p\equiv -1\pmod{6}$ we conclude $p\equiv{11}\pmod{30}$. For that, easiest is by working mod $30$. (more)2012-05-12
  • 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