# Showing that if $p = k2^n+1$ with $k$ odd, then the Jacobi symbol $(\frac{k}{p})$ equals $1$

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.

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

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