4
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Brilliant, thank you! $\endgroup$ – lmc Feb 2 '17 at 17:25
7
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.