Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Try to find a counterexample. –  the symplectic camel Dec 7 '11 at 21:25
    
Please move (4) to a new question, since it is unrelated to the others. –  Bill Dubuque Dec 7 '11 at 21:32
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$... –  Jyrki Lahtonen Dec 7 '11 at 21:33
    
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$. –  Alex Dec 7 '11 at 21:34

3 Answers 3

up vote 1 down vote accepted

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!

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.