1. ## More Congruence

if $\displaystyle a\equiv b \ \mbox{(mod m)}$, then $\displaystyle a^2\equiv b^2 \ \mbox{(mod m)}$

Here is what I tried but it didn't go anywhere.

$\displaystyle m|(a-b)\rightarrow (mx)^2=(a-b)^2\rightarrow m^2x^2=a^2-2ab+b^2$

2. Originally Posted by dwsmith
if $\displaystyle a\equiv b \ \mbox{(mod m)}$, then $\displaystyle a^2\equiv b^2 \ \mbox{(mod m)}$

Here is what I tried but it didn't go anywhere.

$\displaystyle m|(a-b)\rightarrow (mx)^2=(a-b)^2\rightarrow m^2x^2=a^2-2ab+b^2$
$\displaystyle a \equiv b\ \Rightarrow aa \equiv ba\ \Rightarrow aa \equiv bb\ \Rightarrow a^2\equiv b^2\ (\text{mod}\ m)$.

3. Originally Posted by undefined
$\displaystyle aa \equiv ba\ \Rightarrow aa \equiv bb$.
How does a turn into b?

4. Originally Posted by dwsmith
How does a turn into b?
MathWorld property #8.

Let and , then

5. Originally Posted by undefined
MathWorld property #8.

Let and , then

I don't see how that is justifying a=b

6. Originally Posted by dwsmith
I don't see how that is justifying a=b
I never wrote a=b. "a turning into b" is not the same as a=b, if you meant to convey this then you need to be more clear.

All we need is $\displaystyle ba \equiv bb$.

It's perhaps a little confusing since the letters overlap.

Let's rewrite the mathworld property as follows

Let $\displaystyle x\equiv x'$ (mod m) and $\displaystyle y \equiv y'$ (mod m), then

$\displaystyle xy \equiv x'y'$ (mod m)

So here

x=b
x'=b
y=a
y'=b

7. ## An alternative

dwsmith,

An alternative, more along the lines of your original argument is take where you noted that if $\displaystyle a\equiv{b}\,\pmod{m}$, then m divides a-b; and then note that if m divides a-b, it divides $\displaystyle (a-b)(a+b)=a^2-b^2$, so $\displaystyle a^2-b^2$ is then a multiple of m as well.

--Kevin C.

8. Originally Posted by TwistedOne151
dwsmith,

An alternative, more along the lines of your original argument is take where you noted that if $\displaystyle a\equiv{b}\,\pmod{m}$, then m divides a-b; and then note that if m divides a-b, it divides $\displaystyle (a-b)(a+b)=a^2-b^2$, so $\displaystyle a^2-b^2$ is then a multiple of m as well.

--Kevin C.
Why are we able to just to multiple (a+b) without multiplying the left side by (a+b)?

9. Never mind, I have it.

10. I like TwistedOne151's approach, but it's good to know what kinds of rules you can apply with congruences, which can make things easier in general, for example

$\displaystyle ab+cd\equiv a'b'+c'd'\ (\text{mod}\ n)$

as long as

$\displaystyle a\equiv a'\ (\text{mod}\ n)$
$\displaystyle b\equiv b'\ (\text{mod}\ n)$

etc.

This will help later on; for example, using Euler's theorem, you will be able to do this manipulation:

$\displaystyle a^{2\varphi(n)}\equiv \left(a^{\varphi(n)}\right)^2 \equiv 1^2 \equiv 1\ (\text{mod}\ n)$

given that gcd(a,n)=1.