3
$\begingroup$

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
    Try to find a counterexample.2011-12-07
  • 0
    Please move (4) to a new question, since it is unrelated to the others.2011-12-07
  • 2
    #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$...2011-12-07
  • 0
    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$.2011-12-07

3 Answers 3

0

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.

3

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

1

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!