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?

  • 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!