Help with a congruence proof

• Oct 11th 2012, 01:46 PM
notinsovietrussia
Help with a congruence proof
The question asks you to find if a statement is true, if it is, prove it. If it is not, give a counterexample.
If a2 = b2 (mod p), then a = b (mod p), where p is prime.
Note the underlined equal signs are actually meant to be congruence signs. Is there a way to insert congruence signs in this forum?

I based my proof on the properties of congruences which states that if a = b (mod m), and c = d (mod m), then ac = bd (mod m).
a = b (mod m)
a = b + mk
(a)(a) = (b + mk)(b + mk)
a2 = b2 + 2mbk + m2k2
a2 = b2 + m(2bk + mk2) 2bk + mk2 is an integer, say t
a2 = b2 + mt

Therefore a2 = b2 (mod m)

I personally don't see why this proof would not hold if the modulus is prime. Then again, I'm not great with proofs. Can I stick a "p" in place of "m" in my proof and call it a day? Or does the fact the modulus is prime complicate things?
• Oct 11th 2012, 02:31 PM
Plato
Re: Help with a congruence proof
Quote:

Originally Posted by notinsovietrussia
The question asks you to find if a statement is true, if it is, prove it. If it is not, give a counterexample.
If a2 = b2 (mod p), then a = b (mod p), where p is prime.
Note the underlined equal signs are actually meant to be congruence signs. Is there a way to insert congruence signs in this forum?

Note that $\displaystyle a^2\equiv_p b^2$ means $\displaystyle p|(a^2-b^2)$ which implies $\displaystyle p|[(a-b)(a+b)]$.
• Oct 11th 2012, 04:44 PM
notinsovietrussia
Re: Help with a congruence proof
Quote:

Originally Posted by Plato
Note that $\displaystyle a^2\equiv_p b^2$ means $\displaystyle p|(a^2-b^2)$ which implies $\displaystyle p|[(a-b)(a+b)]$.

Hmm, when I originally attempted to prove this I went down this road, but stalled. If you brought this up, it must be significant. This was my approach...

If $\displaystyle p|(a^2-b^2)$

then $\displaystyle p|[(a-b)(a+b)]$

so either $\displaystyle p|(a-b)$ or $\displaystyle p|(a+b)$

if $\displaystyle p|(a-b)$

then $\displaystyle a=b+pk$

which means $\displaystyle a\equiv_p b$

if $\displaystyle p|(a+b)$

then $\displaystyle a=-b+pk$

which means $\displaystyle a\equiv_p -b$, but since -b is not neccesarily congruent to b (mod p) we cannot conclude that $\displaystyle a\equiv_p b$.

So that's where I stalled...
• Oct 12th 2012, 12:33 AM
emakarov
Re: Help with a congruence proof
The original statement is false. In post #1, you proved the converse.
• Oct 12th 2012, 05:33 AM
notinsovietrussia
Re: Help with a congruence proof
So by proving the converese I disporved the original statement?
• Oct 12th 2012, 06:37 AM
emakarov
Re: Help with a congruence proof
Quote:

Originally Posted by notinsovietrussia
So by proving the converese I disporved the original statement?

No. If you proved A -> B, it says nothing about B -> A. The latter statement can be true or false.
• Oct 12th 2012, 08:30 AM
notinsovietrussia
Re: Help with a congruence proof
Quote:

Originally Posted by emakarov
No. If you proved A -> B, it says nothing about B -> A. The latter statement can be true or false.

I see. That makes sense. Well I handed in my assignment with the original proof because I really couldn't come up with anything better. I guess I will find out how we were supposed to prove prove/disprove it when I get it back. Thanks for the assistance.
• Oct 12th 2012, 01:48 PM
emakarov
Re: Help with a congruence proof
If you'd like, you can post the correct answer once you know it so that other people who will read the thread later may have the complete picture.

Also, the converse of an implication should not be confused with the negation. The converse of A -> B is B -> A. The negation applies to any proposition, and the negation ~(A -> B) of an implication is equivalent to A /\ ~B. Proving the negation of a statement indeed disproves that statement.
• Oct 12th 2012, 06:26 PM
johnsomeone
Re: Help with a congruence proof
Quote:

Originally Posted by notinsovietrussia
The question asks you to find if a statement is true, if it is, prove it. If it is not, give a counterexample.
If a2 = b2 (mod p), then a = b (mod p), where p is prime.

Counter-example: 3 is prime. Since $\displaystyle 1^2 \cong 1 \ mod \ 3$, and $\displaystyle 2^2 \cong 4 \cong 1 \ mod \ 3$, have that
$\displaystyle 1^2 \cong 2^2 \ mod \ 3$, but $\displaystyle 1 \ncong 2 \ mod \ 3$.