Show that ## a^2\equiv b^2 \mod n ## need not imply that ## a\equiv b \mod n ##

[Math100]

Homework Statement

Give an example to show that $a^2\equiv b^2 \mod n$ need not imply that $a\equiv b \mod n$.

Relevant Equations

None.

Disproof:

Here is a counterexample:
Let $a=3, b=4$ and $n=7$.
Then $a^2\equiv b^2 \mod n\implies 9\equiv 16 \mod 7$.
Thus $3\not\equiv 4 \mod 7$.
Therefore, $a^2\equiv b^2 \mod n$ need not imply that $a\equiv b \mod n$.

 

[fresh_42]

Homework Statement:: Give an example to show that $a^2\equiv b^2 \mod n$ need not imply that $a\equiv b \mod n$.
Relevant Equations:: None.

Disproof:

Here is a counterexample:
Let $a=3, b=4$ and $n=7$.
Then $a^2\equiv b^2 \mod n\implies 9\equiv 16 \mod 7$.
Thus $3\not\equiv 4 \mod 7$.
Therefore, $a^2\equiv b^2 \mod n$

need does

not imply that $a\equiv b \mod n$.

 

[Prof B]

@Math100 The only correct lines in your "proof" are the first two: "Here is a counterexample: Let a=3, b=4, n=7." After that your reasoning is all wrong. I don't think this is the first time you are hearing this.

Homework exercises are opportunities to practice logical reasoning. Don't waste your time practicing illogical reasoning. Visit your teacher in office hours. Ask to go over the basics of logical reasoning. Hire a tutor if necessary.

@fresh_42 The word "need" in the problem statement is technically right because the truth value of $a^2 \equiv b^2 \pmod{n} \rightarrow a \equiv b \pmod{n}$ depends on the values of a, b, and n. The word "need" is like the arrow's second shaft in $a^2 \equiv b^2 \pmod{n} \Rightarrow a \equiv b \pmod{n}$. The second shaft in the arrow means "for all values of all variables"

 

[fresh_42]

The word "need" in the problem statement is technically right

Yes, but it sounds as if the implication would sometimes hold and sometimes not. But the implication itself does never hold, even in case the left and the right term are both true.

 

[Prof B]

$3^2 \equiv 3^2 \pmod{7} \rightarrow 3 \equiv 3 \pmod{7}$ because every statement implies every true statement.

 

[fresh_42]

Yes, but $\left(\forall \;a,b,n\in \mathbb{Z}\, : \,a^2\equiv b^2 \pmod n \Longrightarrow a\equiv b\pmod n\right)$ is always a wrong statement. That's why the existence of a triple $(a,b,n)$ falsifies it.

 

[Mark44]

@fresh_42 The word "need" in the problem statement is technically right

I agree. The phrase "need not" is appropriate here.

Yes, but $\left(\forall \;a,b,n\in \mathbb{Z}\, : \,a^2\equiv b^2 \pmod n \Longrightarrow a\equiv b\pmod n\right)$ is always a wrong statement. That's why the existence of a triple $(a,b,n)$ falsifies it.

@Prof B's example, $3^2 \equiv 3^2 \pmod{7} \rightarrow 3 \equiv 3 \pmod{7}$, shows that the given statement is not always wrong.

 

[fresh_42]

We obviously read the exercise differently. The goal of this exercise is in my opinion to demonstrate that $a^2=b^2 \Longrightarrow a=b$ cannot be used. It is not helpful to claim: It can be used sometimes.

However, as long as spoken language is used, it is basically always possible to discuss it. That's why logic uses symbols.

Besides that, my main purpose for a correction was to signal that I read it carefully.

Edit: I once had a thesis (CS) in hand with exactly this error in it, only that it was inequalities that kind of doubled the error.

 

[Mark44]

We obviously read the exercise differently. The goal of this exercise is in my opinion to demonstrate that $a^2=b^2 \Longrightarrow a=b$ cannot be used. It is not helpful to claim: It can be used sometimes.

As stated, the goal of the exercise was to provide an example showing that $a^2 \equiv b^2 \mod n$ need not imply that $a \equiv b \mod n$.

@Math 100 has given a valid counterexample, and @Prof B has given a valid example for which the implication is true. Clearly the implication is sometimes true, but need not always be true.

 

[epenguin]

YHomework Statement:: Give an example to show that $a^2\equiv b^2 \mod n$ need not imply that $a\equiv b \mod n$.
Relevant Equations:: None.

Disproof:

Here is a counterexample:
Let $a=3, b=4$ and $n=7$.
Then $a^2\equiv b^2 \mod n\implies 9\equiv 16 \mod 7$.
Thus $3\not\equiv 4 \mod 7$.
Therefore, $a^2\equiv b^2 \mod n$ need not imply that $a\equiv b \mod n$.

You have indeed got a counterexample, as asked. Why not just say so?

Here is a counterexample: $a=3, b=4$ and $n=7$.
For $3^2 = 4^2 (mod 7) = 2$
whereas $3 mod 7 = 3 ≠ 4 mod 7 = 4$.

There is no thus and therefore about it.

You do not seem to be making much progress with this course, and are continually producing answers that have the sound of mathematical language but do not prove the conclusions - and you should easily be able to see they don't

 

[mathwonk]

I.e., in the original answer, change the direction of the first implication, and change the word "Thus" to "But".