Showing a statement $ax \equiv bx \pmod n$ where $x \neq 0$, then $a \equiv b \pmod n$

904 Views Asked by At

So I was given a question like this

Showing that the following statement

If $ax \equiv bx \pmod n$ where $x \neq 0$, then $a \equiv b \pmod n$ is not always true (provide a counterexample).

My solution

I saw the cancellation law so

if $ax ≡ ay \pmod n$ and $(a, n) = 1$ then $a ≡ b \pmod n$. If $n$ is prime this is simply

If $ax ≡ ay \pmod n$ and $a \neq 0 \pmod n$ then $a ≡ b \pmod n$. Note the similarity with the familiar algebraic law if congruence is replace by equality:

If $ax = ay$ and $a \neq 0$ then $a = b$. The result for primes is equivalent to

If $ab ≡ 0 \pmod n$ then $x ≡ 0 \pmod n$ or $y ≡ 0 \pmod n$.

Is this correct for this question?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $a=0$, $x=2$, $b=2$ and $n=4$.

$0\times 2 \equiv 2\times 2 \pmod{4}$ but $0\not\equiv 2 \pmod{4}$