# Thread: Quadratic Residue

1. ## Quadratic Residue

Prove that if c is odd, then $(\frac{2}{c}) = (-1)^{\frac{(c^{2}-1)}{8}}$.

I know I'm supposed to use the theorem that states $(\frac{2}{p}) = (-1)^{\frac{p^{2}-1}{8}}$, where p is an odd prime. But I'm not confident that stating that c is simply an odd prime is enough to satisfy this.

2. Originally Posted by kyldn6
Prove that if c is odd, then $(\frac{2}{c}) = (-1)^{\frac{(c^{2}-1)}{8}}$.

I know I'm supposed to use the theorem that states $(\frac{2}{p}) = (-1)^{\frac{p^{2}-1}{8}}$, where p is an odd prime. But I'm not confident that stating that c is simply an odd prime is enough to satisfy this.

I think this is false: check $\binom{2}{9}=-1\neq (-1)^{\frac{9^2-1}{8}}$ ...

Tonio

3. What is the symbol? The Jacobi symbol? Because the Legendre symbol is defined only for primes. If it's the Jacobi symbol, then it's true and you can prove it using the definition of the Jacobi symbol and the corresponding property of the Legendre symbol.

4. Originally Posted by tonio
I think this is false: check $\binom{2}{9}=-1\neq (-1)^{\frac{9^2-1}{8}}$ ...

Tonio
$\left(\frac{2}{9}\right)=1$ if the symbol is Jacobi's. Note that when the Jacobi symbol $\left(\frac{m}{n}\right)$ is 1, it does not mean that $m$ is a square (mod $n$).

5. Yes it is the Jacobi symbol.

6. Let $c=p_1^{\alpha_1}\hdots p_k^{\alpha_k}$ . By definition, $\left(\frac{2}{c}\right)=\left(\frac{2}{p_1}\right )^{\alpha_1}\hdots\left(\frac{2}{p_k}\right)^{\alp ha_k}$. Using the corresponding property of the Legendre symbol we have that this is $\left((-1)^{(p_1^2-1)/8}\right)^{\alpha_1}\hdots \left((-1)^{(p_k^2-1)/8}\right)^{\alpha_k} = (-1)^{(\alpha_1(p_1^2-1)+\hdots +\alpha_k(p_k^2-1))/8}$. Now what you want to show is ${(\alpha_1(p_1^2-1)+\hdots +\alpha_k(p_k^2-1))/8} \equiv (c^2-1)/8 \mod 2$.

Does this help a bit?

7. Yes thank you so much.

8. If its not too much trouble and if someone feels like it, could someone post the last half of the proof, I'm fairly confident I have it here but I'm not 100% confident.