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

Can you guys help me find an example for a,b,n that let:

$$a \not\equiv 0\pmod{n} $$ $$b \not\equiv 0\pmod{n} $$ But: $$ab \equiv 0\pmod{n} $$

I think I tried everything...

Thank you

share|cite|improve this question
$4\not\equiv0\pmod 6,3\not\equiv0\pmod 6,$ but $12?$ – lab bhattacharjee Nov 29 '12 at 19:23
Try $n=ab$ with $a,b>1$. – anon Nov 29 '12 at 19:24
up vote 1 down vote accepted

$n=ab$ works for any $a,b$ that are integers $>1$.

share|cite|improve this answer

$n \not \equiv 0 \pmod {n^2}$ but $n^2 \equiv 0 \pmod {n^2}$

share|cite|improve this answer

An example can be found for any $n$ that is not prime. For example, $2 \not\equiv 0 \mod{4}$, but $2 \cdot 2 \equiv 0 \mod{4}$.

Thus if $n$ is not prime, then $n \mid ab$ does not imply $n \mid a$ or $n \mid b$. In other words, Euclid's lemma is true only for primes.

share|cite|improve this answer

Hint: $12 \equiv 0\bmod 12$, $16 \equiv 0\bmod 16$, etc. but ...

share|cite|improve this answer
But $12\ne16$. ${}$ – anon Nov 29 '12 at 19:45
No, what I mean is $12 \equiv 0\bmod 12,6\not \equiv 0\bmod 12,2\not \equiv 0\bmod 12$ and $16 \equiv 0\bmod 16,8\not \equiv 0\bmod 16,2\not \equiv 0\bmod 16$. – glebovg Nov 30 '12 at 0:26
Right. However, it is not often you see a sequence beginning with 12 and 16 used to represent composite numbers. The strange choice of numbers misled me as to your intention. – anon Nov 30 '12 at 2:13

We seek integers $\rm\:a,b,c\:$ such that $\rm\:c\mid ab\:$ but $\rm\:c\nmid a,b.\:$ We can easily reduce this to a simpler set-theoretic analog. Let $\rm\:A,B,C\:$ be the multisets of prime factors of $\rm\:a,b,c,\:$ respectively, e.g. if $\rm\:a = 12\:$ then $\rm\:A = \{2, 2, 3\}.\:$ Notice divisibility is equivalent to containment: $\rm\:c\mid b\!\iff\! C\subseteq B,\:$ and multiplication corresponds to union: $\rm\:AB\:$ has prime multiset $\rm = A\cup B.\:$ Thus our problem translates into an equivalent problem on multisets of primes

$$\begin{eqnarray}\rm c\ \mid\,\ a\times b\, &&\rm but\ \ \ c\ \nmid\,\ a,b \\ \rm\iff\ \ C\subseteq A\cup B &&\rm but\ \ C\not\subseteq A,B \end{eqnarray}$$

Clearly such a "splitting" of $\rm\,C\,$ exists iff $\rm\:C\:$ has two or more elements, i.e. iff $\rm\:c\:$ is composite.

share|cite|improve this answer
What? Have you seen the tag? – glebovg Nov 30 '12 at 0:28
@glebovg The question is tagged "elementary number theory", and the answer is, indeed, elementary number theory. The point of the answer is to give some conceptual insight, which is something students may not intuit from seeing random specific examples. Rather than downvote, if something is not clear, then why don't you simply ask for an explanation, and I'll be happy to elaborate. I cannot do that yet, since your comment does not allow me to infer what may be unclear to you. – Bill Dubuque Nov 30 '12 at 0:47

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.