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

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.

• Some basic primality tests to start with: Are both numbers in the form $4k+1$ or $4k+3$? Are they congruent to $1$ modulo $\frac{2^{19}+1}{3}$ and $\frac{2^{23}+1}{3}$ (according to Fermat's Little Theorem) respectively? – Toby Mak Jun 30 '17 at 13:00
• There is a whole article on MSE about this: (math.stackexchange.com/questions/483298/…) – Toby Mak Jun 30 '17 at 13:01
• @TobyMak The article you linked gave information on Mersenne and proth numbers, but here, it is a different one, it is more related to fermat numbers, isnt it? – vidyarthi Jun 30 '17 at 13:04
• I was referring to the section about Proth numbers at the end: Fermat numbers don't apply here since your number is not in the form $2^{2^k}+1$, but only $2^k+1$. $k$ might not be a power of two since the number are divided by $3$. – Toby Mak Jun 30 '17 at 13:06
• In the first case, you only need to check values of $p$ up to $418$, since $419^2>\frac{2^{19}+1}{3}$. There is no prime $p\equiv 1,115\pmod{152}$ in that range, so you are done. – Thomas Andrews Jun 30 '17 at 13:17

## 1 Answer

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

• Is there a general term for the numbers of the form $(2^p+1)/3$? edit: OEIS gave Wagstaff primes... – Joffan Jun 30 '17 at 17:34