# Proofs using linear congruences

We have just covered solving linear congruences, and I am confused about how to use them in proofs. I understand that the linear congruence $$cx \equiv b \pmod m$$ has a unique solution $\bmod m$ if $\gcd(c,m) = 1$, but a general approach to problems escapes me.

Sample Questions

Prove that if $x^2 \equiv n \pmod {65}$ has a solution, then so does $x^2 \equiv -n \pmod {65}$.

Show that if $n \equiv 7 \pmod 8$, then $n$ is not the sum of three squares.

My Work

For the first one, $x^2 \equiv n \pmod {65}$ implies that $65 | (x^2 - n)$, so (I believe) that means that $n = b^2$ for some $b$, so $65 | (x^2 - b^2)$. We proved a result that said that if $a^2 \equiv b^2 \pmod p$ for some prime $p$, then $a \equiv b$ or $a \equiv - b \pmod p$. However, I don't think that is the right track to go down here because $65$ is not prime, and I'm unsure about assuming $n = b^2$ for some $b$.

For the second one, suppose to the contrary that $n = a^2 + b^2 + c^2$ for some $a, b, c$. Then $n \equiv 7 \pmod 8$ implies that $8 | (n - 7)$ so $n = 8k + 7$ for some $k$. So substituting in gives me $a^2 + b^2 + c^2 = 8k + 7$, and I'm unsure how to proceed from here.

-
+1 for showing your work. – lhf Sep 14 '12 at 12:19

Hint $\rm(1)\ \ \ x^2 \equiv n,\,\ y^2\equiv -1\:\Rightarrow\: -n\equiv x^2y^2\equiv (xy)^2.\$ But $\rm\:mod\ 65\!:\ {-}1 \equiv 64\equiv (\_ )^2.$
$\rm(2)\ \ mod\ 4\!:\ x^2\!+\!y^2\!+\!z^2 \equiv\, 3\:\Rightarrow\:x,y,z\:$ odd, by $\rm\:odd^2\equiv 1,\ even^2\equiv 0.\:$ Therefore we deduce $\rm\phantom{(2)\ \ } mod\ 8\!:\ x^2\!+\!y^2\!+\!z^2\equiv\:7\:\Rightarrow\:x,y,z\:$ odd $\rm\:\Rightarrow\:x^2\!+\!y^2\!+\!z^2\equiv 3,\:$ by $\rm\:odd^2\!\equiv\{\pm1,\pm3\}^2\equiv 1.$
For the first question, note that $65=5 \cdot 13$ and $x^2 \equiv -1$ has solutions mod 5 and mod 13. Note also that solutions of $x^2 \equiv n \bmod 65$ also give solutions mod 5 and mod 13. Combine those.