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
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
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.
$n \not \equiv 0 \pmod {n^2}$ but $n^2 \equiv 0 \pmod {n^2}$
$n=ab$ works for any $a,b$ that are integers $>1$.
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 ...