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.
Answer
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.$
No comments:
Post a Comment