# number theory and Congruence

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

-
$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

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

-

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

-

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.

-

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

-
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.

-
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