Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Any help with this proof would be great. Not even sure where to begin. I'm pretty much a total newbie.

If $a$ is not congruent to $0 \pmod{p}$ and $b$ is not congruent to $0 \pmod{p},$ where $p$ is a prime number, then $a*b$ is not congruent to $0 \pmod{p}.$

Also, not sure why it is necessary to assume that p is a prime number...?

share|cite|improve this question
Here is an example for $n$ composite. $3 \equiv 3 \pmod{12}$ and $4 \equiv 4 \pmod{12}$ but $3*4 \equiv 0 \pmod{12}.$ – user2468 Jul 28 '12 at 2:53
Please don't use the proof-theory tag for question like this. That denotes a subfield of mathematical logic devoted to proof-theoretical matters. – Bill Dubuque Jul 28 '12 at 3:08
noted. Sorry, won't happen again. – rookie_02 Jul 28 '12 at 7:33
up vote 0 down vote accepted

Let $Q=\{q_1,\ldots,q_m\}$ be the primes that occur in the prime factorisation of $a$, and $R=\{r_1,\ldots,r_n\}$ be the primes that occur in the prime factorisation of $b$. Then $Q\cup R$ is the set of primes that occur in the prime factorisation of $ab$. Your premise is that neither $a$ nor $b$ is a multiple of $p$. So $p\notin Q$ and $p\notin R$. Therefore $p\notin Q\cup R$ and $ab$ is also not a multiple of $p$.

share|cite|improve this answer
  1. Euclid's lemma: $ p | a b \implies p | a \lor p | b.$

  2. Contrapositive: $x \implies y$ is equivalent to $\lnot y \implies \lnot x.$

  3. De Morgan $\lnot (x \lor y)$ is equivalent to $\lnot x \land \lnot y$

So $$ p \not| a \land p \not| b \implies p \not| a b.$$

share|cite|improve this answer
But I have to admit it's a terrible proof! – user2468 Jul 28 '12 at 2:51
But it's still useful – rookie_02 Jul 28 '12 at 7:34

For the last part of your question, let $m=6$ and $a=2$, $b=3$. Then $ab\equiv 0\pmod{m}$ but $a\not\equiv 0\pmod m$ and $b\not\equiv 0\pmod{m}$. One can also pick $a=4$, $b=3$.

One can produce a similar example for any composite integer $m$: just pick $a$ and $b$, neither equal to $\pm 1$, such that $ab=m$.

Thus if $m \gt 1$, then $m$ has the property of the problem iff $m$ is prime.

share|cite|improve this answer

The condition is the contrapositive of Euclid's Lemma from your previous question.

share|cite|improve this answer

Hint $\ $ The contrapositive of your statement is $\rm\:p\:|\:ab\:\Rightarrow\:p\:|\:a\ \ or\ \ p\:|\:b,\:$ which I proved in your prior question. If $\rm\:p>1\:$ is not prime then $\rm\:p = ab\:$ for $\rm\:a,b>1\:$ so $\rm\:p = ab\:|\:ab,\,$ but $\rm\:ab\nmid a,b$.

share|cite|improve this answer

When $p$ is a prime number $\Bbb{Z}/p\Bbb{Z}$ is a field and hence in particular an integral domain. So therefore for any $a,b \in \Bbb{Z}/p\Bbb{Z}$, if $$ab = 0$$

by definition of an integral domain we must have $a=0$ or $b = 0$. This is equivalent (by the contrapositive) to saying that for any $a,b \in \Bbb{Z}/p\Bbb{Z}$ both not equal to zero, we have

$$ab \neq 0.$$

share|cite|improve this answer

Since this proof deals with congruence modulo $p$ (for some prime $p$), the first step is to ask what it means for an integer to be "congruent to $0\ \mod p$"?

Answer: It means the integer is a multiple of $p$.

The next step is to replace "congruence mod $p$" with its meaning:

If $a$ and $b$ are not multiples of $p$, then $ab$ is not a multiple of $p$.

Can you see how to prove the proposition now? Do you see why we have to assume that $p$ is prime?

share|cite|improve this answer
I see it now. Thanks – rookie_02 Jul 28 '12 at 9:16

$a$ not congruent to $0 \mod p$ and $b$ not congruent to $0 \mod p$ just mean that $a$ and $b$ are not divisible by $p$. Suppose $p$ divides $ab$. Since $p$ is prime, this means that $p$ divides $a$ or $p$ divides $b$. Contradiction.

share|cite|improve this answer

Since p does not divide a then there is a linear combination (using the extended division algorithm) ua+vp=1 where u, v are integers. Now multiply by b to get uab+vpb=b. If p divides ab then it divides the left side of this relation and so p|b.

This would also work if a and n are relatively prime. The statement is: if n is relatively prime to a, and n divides ab then n divides b.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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