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

Rosen 149

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.

  • 1
    $\begingroup$ 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? $\endgroup$ – lulu Jul 5 '19 at 19:31
  • $\begingroup$ 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$) $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.