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 a**^{2} __=__ b^{2} (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)

a^{2} = b^{2} + 2mbk + m^{2}k^{2}

a^{2} = b^{2} + m(2bk + mk^{2}) 2bk + mk^{2} is an integer, say t

a^{2} = b^{2} + mt

Therefore a^{2} __=__ b^{2} (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?

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 a**^{2} __=__ b^{2} (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)]$.

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...

Re: Help with a congruence proof

The original statement is false. In post #1, you proved the converse.

Re: Help with a congruence proof

So by proving the converese I disporved the original statement?

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.

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.

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.

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 a**^{2} __=__ b^{2} (mod p), then a __=__ b (mod p), where p is prime.

You answer it like this:

The statement is false.

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