a⊙b=0 if and only if a=0 ∨ b=0.

301 Views Asked by At

I don't see how this holds, or maybe I'm understanding modular arithmetic incorrectly. If $n = 12$ then $a ⊙ b = 0$ can be satisfied by $a = 3$ and $b = 4$ no?

I see how this holds when I write the proof for it.

If $(a * b)$ mod $n = 0$, $a * b = n$.

We can rewrite $a ⊙ b = 0$ as: $ab + kn = 0$, now as $ab + ab(k) = 0$.

Factoring out an $ab$ we get $ab( 1 + k) = 0$.

Since $k$ is $a \geq 0$, $a*b = 0$, meaning $a ∨ b = 0$.

But I still don't see how this makes sense!

1

There are 1 best solutions below

4
On BEST ANSWER

This hold for prime numbers. Because if $a \times b$ is the choosen prime n, then $a$ or $b$ is $n$ and the other is 1