primality of $\frac{(2^{19}+1)}{3}$ and $\frac{(2^{23}+1)}{3}$

Question

This is from an exercise in Burton's Number theory book. I have a hard time solving this. How could we prove that $\displaystyle\frac{(2^{19}+1)}{3}$ and $\displaystyle\frac{(2^{23}+1)}{3}$ are primes. I know that the primes dividing the numbers are of the form are $38k+1$ and $46k+1$ respectively. How can we proceed without a computer? Any hints. Thanks beforehand.

Answer 1

In general, if $q>3$ is prime and $p$ a prime divisor of $N=\frac{2^q+1}{3}$, then, as you argued, $p=2qk+1$ for some $k$.

So: $2^{(p-1)/2}\equiv (-1)^k\pmod p$.

If $k$ is even, then $2$ is a square modulo $p$ which means that $p\equiv \pm 1\pmod{8}$ or $2qk\equiv 0,6\pmod{8}$ or $qk\equiv 0,3\pmod{4}$. But since $k$ is even, this requires $k$ to be divisible by $4$, so $p\equiv 1\pmod{8q}$.

If $k$ is odd, then $2$ is not a square modulo $p$ so $p\equiv 3,5\pmod{8}$ so $qk\equiv 1,2\pmod{4}$, which means that $k\equiv q\pmod{4}$. So $p\equiv 1+2q^2\pmod{8q}$.

So you can check only the primes $p\equiv 1,1+2q^2\pmod{8q}$, for $p<\sqrt{N}$.

For $q=19$, $p\equiv 1,115\pmod{152}$. But there are no primes $p$ matching these conditions less than $\sqrt{N}<419.$

For $q=23$, $p\equiv 1,139\pmod{184}$, and $\sqrt{N}<1673$. So the first prime to check is $p=139.$ The next to check is $691$.

In the case of $q=41$, you'd need to check $p\equiv 1,83\pmod{328}$. But now you might have to check up to $\sqrt{N}\approx 857,000$.