Prove or disprove the following statement in modular arithmetic.

  1. If $a\equiv b \mod m$, then $ a^2\equiv b^2 \mod m$
  2. If $a\equiv b \mod m$, then $a^2\equiv b^2 \mod m^2$
  3. If $a^2\equiv b^2\mod m^2$, then $a\equiv b\mod m$

My proofs.

  1. $$ a\equiv b \mod m \implies (a-b) = mr, r\in\mathbb{Z}$$ $$ a^2-b^2 = (a+b)(a-b) = (a+b)mr = ms \text{ where } s = (a+b)\cdot r$$ So the first statement is true

  2. $$ a\equiv b \mod m \implies (a-b) = mr, r\in\mathbb{Z}$$ $$a^2-b^2 = (a+b)(a-b) = (a+b)mr$$ but $(a+b)\neq ms$ $\forall s\in\mathbb{Z}$ in general. So the second one is false.

  3. $$a^2-b^2 = m^2r, \exists r\in\mathbb{N}$$ $$a^2-b^2= (a+b)(a-b) $$ Then I kind of got stuck here. I'm not sure how to continue it. Am I missing some properties I don't know? Or there is a algebra trick that could be applied here?

  • 1
    $\begingroup$ Try to find a counterexample. $\endgroup$ – Karatug Ozan Bircan Dec 7 '11 at 21:25
  • $\begingroup$ Please move (4) to a new question, since it is unrelated to the others. $\endgroup$ – Bill Dubuque Dec 7 '11 at 21:32
  • 2
    $\begingroup$ #1 is ok. For #2 it would make your argument more convincing, if you gave a counterexample, i.e. an example of the situation, where the claim faild. After all, conceivable it might happen that $a-b$ is always divisible by $m^2$, if $a+b$ is not. Also, if $m=2$, then the claim actually holds, so... Similarly for #3. If you find a counterexample, where $m^2$ divides $a+b$, then there is hope that $m$ may not divide $a-b$ even though $m^2$ divides $a^2-b^2$... $\endgroup$ – Jyrki Lahtonen Dec 7 '11 at 21:33
  • $\begingroup$ Small point, when you say $r\in \mathbb{N}$, you actually want $\mathbb{Z}$. For example, $1 \equiv 6 \pmod{5}$, but there is no natural number $r$ such that $5r = 1-6 = -5$. $\endgroup$ – Alex Dec 7 '11 at 21:34

For Question 3, you are told that $m^2$ divides $a^2-b^2$, and are asked whether (necessarily) $m$ divides $a-b$.

Note that $a^2-b^2=(a-b)(a+b)$. Maybe the "factor" $m^2$ comes in whole or in large part from $a+b$, not from $a-b$. Let's see whether we can find an example. Let $m=3$, so $m^2=9$. Make $a+b$ divisible by $9$, for example by taking $a=8$, $b=1$. Then $a-b=7$, very much not divisible by $3$.

There is no example with $m=2$, but you can use the same idea to find an example with $m=4$. We want $(a-b)(a+b)$ to be divisible by $16$, with $a-b$ not divisible by $4$. We can for example take $a=15$, $b=1$, or $a=13$, $b=3$, or $a=7$, $b=1$. For all these examples, $a^2\equiv b^2\pmod{4^2}$ but $a \not\equiv b\pmod{4}$.

Now make up your own counterexample!


You should try to find a counterexample for #2. Just stating an intuitive reason why your argument in #1 fails for #2 is not enough to disprove it. For instance, in the case $m = 2$, then the result does hold. If you find a single instance where it doesn't hold, then you know it cannot be universally true.

For #3, think about how $x^2 = a$ has two distinct solutions in $\mathbb{R}$. Does something similar happen modulo $m$, for some $m$?


HINT $\: $ for $\rm (3),\ \ m^2\ |\ a^2 - b^2\ \Rightarrow\ m\ |\ a-b\ $ fails if $\rm\: m > 1 = a - b\:.\:$ Then $\rm\:a^2-b^2 = 2\:b+1\:$ so any odd number with a square factor $\rm\:m^2 \ne 1\:$ yields a counterexample.


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.