# Do the properties of modular arithmetic apply to incongruent relations?

Can you treat incongruences as you would congruent relations? i.e. do the following theorems still apply?

As an example, let's say you wanted to prove Euclid's Lemma which states:

If a prime $$p$$ divides the product $$ab$$ of two integers $$a$$ and $$b$$, then $$p$$ must divide at least one of those integers $$a$$ or $$b$$.

If we can show that $$p\not\mid a,b$$ implies that $$p\not\mid ab$$ then we have proven the contrapositive and thus our original statement. So, assume that $$p\not\mid a,b$$. Then by the definition of congruences,

$$a\not\equiv 0\ (mod\ p)$$ $$b\not\equiv 0\ (mod\ p)$$

If (iii) from Theorem 4.6 still holds then it follows that $$ab\not\equiv 0\ (mod\ p)$$

hence $$p\not\mid ab$$ as desired.

• Not entirely sure what you mean. Consider: $1\not\equiv 2 \pmod p$ and $2\not \equiv 1 \pmod p$ but $1\times 2\equiv 2\times 1\pmod p$. Is that a counterexample to what you were hoping for? – lulu Jul 5 '19 at 19:31
• If $p\not|a,b$ then $p\not|ab$ when $p$ is prime but there are counterexamples when $p$ is composite (such as $p=6, a=3, b=4$) – J. W. Tanner Jul 5 '19 at 21:43

This is weak. (iii) is a case of selection. in any base ( even greater than 4) $$2\cdot 1 \equiv (-1)\cdot (-2)$$ Despite, no parts being congruent. The theorem above is simply the inverse of the 0 product rule. In the absence of zero divisors ( divisor of 0 in a ring etc forming a product of 0 with another non zero element) it is true, in the presence of 0 divisors it is not.