# Prove that if $p$ and $8p-1$ are prime numbers then $8p+1$ is composite

Prove that if $p$ and $8p-1$ are prime numbers then $8p+1$ is composite.

I don't know where to start... I would appreciate some hints. Thank you!

As for "where to start" on a question like this: I'd start by finding primes $p$ such that $8p-1$ is prime, and seeing if the prime factorizations of $8p+1$ have anything in common. A list of primes such as this one is useful. For $p < 100$, I find

$$3, 23, 25 = 5 \times 5$$ $$13, 103, 105 = 3 \times 5 \times 7$$ $$19, 151, 153 = 3^2 \times 17$$ $$61, 487, 489 = 3 \times 163$$ $$79, 631, 633 = 3 \times 211$$

and from this you get the idea that if $p$ and $8p-1$ are both prime, then perhaps $8p+1$ must be divisible by 3.

So let $p$ be a prime such that $8p-1$ is also prime. If $p$ is prime, either $p = 3k+1$ or $p = 3k-1$ for some integer $k$. (I'm omitting the $p = 3$ case, which needs to be treated separately.) If $p = 3k-1$ then $8p-1 = 24k-9 = 3(8k-3)$, so $8p-1$ is divisible by 3, and therefore $8p-1$ is not prime. So we must have $p = 3k+1$, and then $8p+1 = 24k+9 = 3(8k+3)$, so $8p+1$ is not prime.

• Brilliant, thank you! – lmc Feb 2 '17 at 17:25

If $8p-1$ is prime, we have $p \neq -1 \mod 3$.

This leaves us with $p=3$ (do this case by hand) or $p = 1 \mod 3$, but then $8p+1 = 0 \pmod 3$.

If $8p-1$ is prime, then it is not divisible by 3.

$8p$ is also not divisible by 3, since $p$ is a prime number.

However, every third number must be divisible by 3. That means that $8p+1$ is divisible by 3, which means it is composite.

First assume $p>3$, then $p\equiv\pm1\bmod6$.

If $p\equiv-1\bmod6$ then $8p-1\equiv2(-1)-1\equiv3\bmod6$, but this implies $3\mid8p-1$ and so $8p-1$ is composite (by the restriction on $p$ above, $8p-1>23$). Therefore for $p$ and $8p-1$ to be prime, $p\equiv1\bmod6$, but this means $8p+1\equiv2(1)+1\equiv3\bmod6$ and so $3\mid8p+1$, leading to $8p+1$ being composite ($8p+1>25$).

This leaves $p=2$ and $p=3$ to be tested. If $p=2$, $8p-1=15$ is composite; if $p=3$, $8p-1=23$ is prime but $8p+1=25$ is composite. Therefore the proposition is proven true.