Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
+1 for showing your work. – lhf Sep 14 '12 at 12:19
up vote 2 down vote accepted

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

share|cite|improve this answer
This is exactly what I was hoping for thanks. – Moderat Sep 14 '12 at 13:16

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.

For the second question, note that squares are congruent to 0, 1, or 4, mod 8. But you cannot sum three numbers from this list to get 7 mod 8.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.