I am observing if $p = k2^n+1$ (a Proth number), $k$ is odd, there is always an integer $x$, such that $k = x^2 \bmod p$, i.e. the Jacobi symbol $(\frac{k}{p})$ is always $1$. Can someone give a formal proof?

Thank you.

  • $\begingroup$ k has to be odd, so p is a Proth Number $\endgroup$ – Kurtul Mar 31 '13 at 19:45
  • $\begingroup$ Never heard that term before. (checks wikipedia). Did you mean $k2^n+1$? $\endgroup$ – user14972 Mar 31 '13 at 19:46
  • $\begingroup$ Correct I edited the Question $\endgroup$ – Kurtul Mar 31 '13 at 19:54

This is an easy exercise in Quadratic reciprocity:

$$ \left(\frac{k}{k2^n + 1}\right) = \mu \left( \frac{k2^n+1}{k} \right) = \mu \left( \frac{1}{k} \right) = \mu $$

and so we just have to figure out what $\mu$ is. When the numerator and denominator are odd, the general theorem says that $\mu$ is $1$ except in the case where both the numerator and denominator are $3 \bmod 4$, in which case $\mu$ is $-1$.

For $n \geq 2$, the denominator is $1 \bmod 4$, so $\mu$ is $1$. But what about $n=1$?

It turns out your conjecture is not true, and we can easily produce a counterexample: for $k=3$ and $n=1$, we see that $3$ is not a square modulo $7$.

To be a Proth number, wikipedia says that we're supposed to have $2^n > k$. If you restrict to this case (and everything being positive), then $k=1$ is the only allowed option when $n=1$, and in this case $1$ is a square modulo $3$.

  • $\begingroup$ Thank you, So for the case n>3, μ is 1, and the conjecture is true. $\endgroup$ – Kurtul Mar 31 '13 at 20:36

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.