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.

  • $\begingroup$ 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? $\endgroup$ – Toby Mak Jun 30 '17 at 13:00
  • $\begingroup$ There is a whole article on MSE about this: (math.stackexchange.com/questions/483298/…) $\endgroup$ – Toby Mak Jun 30 '17 at 13:01
  • $\begingroup$ @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? $\endgroup$ – vidyarthi Jun 30 '17 at 13:04
  • $\begingroup$ 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$. $\endgroup$ – Toby Mak Jun 30 '17 at 13:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jun 30 '17 at 13:17

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

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

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.