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

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.