# More Congruence

• Jun 26th 2010, 12:12 PM
dwsmith
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$
• Jun 26th 2010, 12:32 PM
undefined
Quote:

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)$.
• Jun 26th 2010, 12:33 PM
dwsmith
Quote:

Originally Posted by undefined
$\displaystyle aa \equiv ba\ \Rightarrow aa \equiv bb$.

How does a turn into b?
• Jun 26th 2010, 12:36 PM
undefined
• Jun 26th 2010, 12:38 PM
dwsmith
Quote:

Originally Posted by undefined

I don't see how that is justifying a=b
• Jun 26th 2010, 12:49 PM
undefined
Quote:

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
• Jun 26th 2010, 01:09 PM
TwistedOne151
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.
• Jun 26th 2010, 01:10 PM
dwsmith
Quote:

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)?
• Jun 26th 2010, 01:36 PM
dwsmith
Never mind, I have it.
• Jun 26th 2010, 01:48 PM
undefined
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.