When $\Bbb Z_n$ is a domain. Counterexample to $ab \equiv 0 \Rightarrow a\equiv 0$ or $b\equiv 0\pmod n$

Suppose $$ab \equiv 0 \pmod n$$ and that $a$ and $b$ are positive integers both less than $ n$.

Does it follow that either $a | n$ or $b | n$?

• If it does follow, give a proof.

• If it doesn’t, then give an example.

For this question is this a suitable answer: No it doesn't. $3$ and $4$ are both less than $6$. $$3 \times 4 \equiv 0 \pmod {6}$$

but $4 \not \mid 6$.

No, your answer is incorrect.

Either/Or means it's sufficient that one of them abides the condition.

And in the specific example at hand, one of them indeed does, as $3|6$.

A proper counterexample would be $8\times9\equiv0\pmod{12}$.

$$[a=8,b=9,n=12]\implies[ab\equiv0\pmod{n}]\wedge[a<n]\wedge[b<n]\wedge[a\not|n]\wedge[b\not|n]$$

It is not generally true, but we can force it to be true. Suppose, mod $\,n\,$ that $\,ab\equiv 0\,$ for $\,a,b\not\equiv 0.\ $ Let $\,k\,$ be the additive order of $\,b.\,$ Then $\,a\cdot b\equiv 0\equiv n\cdot b\,\Rightarrow\, k\mid a,n\,\Rightarrow\,k\mid (a,n),\,$ so $\,(a,n)b\equiv 0.\,$ Similarly we deduce $\,(a,n)(b,n) \equiv 0,\,$ where, indeed, $\,(a,n)\mid n,\ (b,n)\mid n.\ $

For example, applied to Barak's example $\ 12\mid 8\cdot 9\ $ we get $\ 12\mid(8,12)(9,12) = 4\cdot 3.$

Thus if $\,n\,$ fails Euclid's Lemma (Prime Divisor Property) $\,n\mid ab\,\Rightarrow\,n\mid a\,$ or $\,n\mid b,\,$ then this method yields a constructive proof that $\,n\,$ is composite, by constructing a proper factor $\,(a,n)\,$ of $\,n.\,$ Indeed, $\,(a,n)\ne n\,$ else $\,n\mid a,\,$ and $\,(a,n)\ne \color{$c00}1\,$ else $\,n\mid (a,n)(b,n)=(b,n)\,\Rightarrow\,n\mid b.\,$ For example, given any polynomial $\,f(x)\in\Bbb Z_n[x]\,$ with more roots than its degree, we can quickly compute a nontrivial factor of $\,n\,$ via a $\rm\,gcd.\,$ Said failure of Eclid's Lemma is sometimes described with the language: $\,ab\,$ is a witness that $\,n\,$ is composite, i.e. $\,n\mid ab,\ n\nmid a,b$.

Said algebraically: not prime $\,\Rightarrow\,$ reducible or, contrapositively, irreducible $\,\Rightarrow\,$ prime. Since the converse always holds, we conclude: $\,\Bbb Z/n\,$ is a domain $\iff n\,$ is prime $\iff n\,$ is irreducible.

Remark $\ $ This idea is sometimes used in integer factorization algorithms to deduce a factor of $\,n\,$ from a "nontrivial" factor of a multiple of $\,n.$

The above constructive proof also generalizes to certain ideals, namely

Theorem $ $ If ideal $I\ne 1$ satisfies: ideal $\,J \supset I \Rightarrow J\,|\,I\,$ then $I$ not prime $\Rightarrow I\,$ reducible (properly).

Proof $\ $ $I$ not prime $\Rightarrow$ exists $a,b \not\in I$ and $ab \in I.$ $\ A := (I,a)\supset I \Rightarrow A|I,$ say $I = AB;$ wlog we may assume $b \in B$ since $A(B,b) = AB\,$ via $Ab = (I,a)b \subset I = AB.$ The factors $A,B$ are proper: $A = (I,a),\, a \not\in I;\,\ B \supset (I,b),\, b \not\in I.\quad$ QED

$$10 \dot \ 12 \equiv 0 \mod 15$$

But neither $10|15 $, nor $12 |15$.

Edit:

If you consider $n$ prime, then $\gcd(n , a) =1$ for $a = 1, \ldots, n-1$. Let any $\overline{a} \in \mathbb Z_n - \{\overline{0}\}$ then there exist integers $b$ and $t$ such that

$$ab + nt =1 \Rightarrow \overline{ab + nt} = \overline{1} \Rightarrow \overline{a}\ \ \overline{b} + \underbrace{\overline{n}}_{=\ 0}\ \ \overline{t} = \overline{1} \Rightarrow \overline{a}\overline{b} = \overline{1}$$

then $\overline{a}$ is invertible, it follows that $\mathbb Z_n$ is a field (every element is invertible), therefore a integral domain.