I have a quick question regarding modular arithmetic.

If I have a Pythagorean Triple $(a, b, c)$, is it possible to consider this equation $\mod{c}$. That is to say,

Is the implication

$$a^2 + b^2 = c^2 \implies (a \mod{c})^2 + (b \mod{c})^2 \equiv 0\mod{c}$$


I attempted to prove this (rather naïvely) by remembering that

\begin{align} a + cx &= a \mod{c}\\ b + cy &= b \mod{c}\\ cz &= 0 \mod{c} \end{align}

for some $x, y, z \in \Bbb{Z}.$ Squaring these expressions gives me

$$a^2 + b^2 + 2cx(a + b) + c^2(x^2 + y^2) = cz$$

and hence that $$a^2 + b^2 \equiv 0 \mod{c}.$$

Have I made some fundamental error or is this a valid method?

Edit: Changed $c^2z^2$ to $cz$.

  • $\begingroup$ You are right: From $a^2+b^2=c^2$, we caan conclude immediately $a^2+b^2\equiv 0\pmod{c}$. $\endgroup$ – André Nicolas Apr 18 '16 at 18:23
  • $\begingroup$ Oh of course, unnecessary proof. In that case, could it then be easier to check if a triple is pythagorean by looking at $a^2$ and $b^2$ modulo $c$ ? $\endgroup$ – ÍgjøgnumMeg Apr 18 '16 at 18:27
  • $\begingroup$ If $a^2+b^2\equiv 0\pmod{c}$, it does not necessarily follow that $a^2+b^2=c^2$. But certainly if $a^2+b^2\not\equiv 0\pmod{c}$, then $(a,b,c)$ is not a triple. I do not know whether the test you suggest might speed up things in some contexts. $\endgroup$ – André Nicolas Apr 18 '16 at 18:36

It has to be true due to a mod b=a if a

Proof: Since a and b are smaller than c, $((a\mod c)^2+(b\mod c)^2)\mod c=(a^2+b^2)\mod c=c^2\mod c=0$


And yes, your method is valid too, it is just a longer version of the method above


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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