Can this be solve using modular arithmetic? $k$ is prime $\Rightarrow$ $8k+1$ is prime

Question

Is the following statement true or false?

$\forall k \in \mathbb{N}, k$ is prime $\Rightarrow$ $8k+1$ is prime

The answer is that the statement is false because if $k=7$, then $k$ is prime but $8k+1=57$ is not prime.

Is there are way to solve this problem using modular arithmetic? If yes, what is the process of solving it and how do I select the right modulo?

Answer 1

There are infinitely many primes $p\equiv1\pmod 3$ (Dirichlet's theorem). And for these primes, $8p+1\equiv 0\pmod 3$, so $8p+1$ is not prime.

I am not sure if this is what you are asking for.

Answer 2

The answer is you can just use the first $k$ in your sequence of primes as modulus.

If for some prime $p$, the sequence of numbers $k_n$ defined by

$$k_n = \begin{cases}p, & n = 0\\8k_{n-1}+1, &n > 0\end{cases}$$

are all primes, we will have

$$k_{p-1} = 8^{p-1} p + 8^{p-2} + 8^{p-2} + \cdots 1 = 8^{p-1} p + \frac{8^{p-1}-1}{7}$$

is also a prime. If $p \ne 2$ nor $7$, then $\gcd(p,8) = 1$ and Fermat little theorem leads to

$$p | 8^{p-1} - 1 \quad\implies\quad p | \frac{8^{p-1}-1}{7} \quad\implies\quad p | k_{p-1}$$

This contradict with the assumption the sequence $k_n$ start at $k_0 = p$ are all primes. Since we know the sequence $k_n$ starting with $k_0 = 2$ or $7$ are not all primes. We can conclude start with any prime $p$, the operation $k \mapsto 8k+1$ will fail to produce a prime after some finite step.