## An integer which divides a product need not divide either factor

Prove that if $n$ is composite then there are integers $a$ and $b$ such that $n$ divides $ab$ but not $a$ or $b$.

We will use a couple of facts about integers. For all integers $a$ and $b$,

1. If $a \geq 0$ and $b > 0$, then $a \leq ab$.
2. $|ab| = |a|\cdot|b|$.
3. If $a|b$ and $b \neq 0$, then $|a| \leq |b|$.
4. If $ab = 0$ then either $b = 0$ or $a = 0$.
5. If $ab = 1$ then either $a = b = 1$ or $a = b = -1$.

Proof of 1: We proceed by induction on $a$. First, note that the proposition is trivial for $a = 0$. Suppose now that the proposition is true for $a = n \geq 0$. Then for all $b > 0$, we have $n < nb$, so $n+1 < nb + 1 < nb + b = (n+1)b$. $\square$

Proof of 2: Note that the proposition is trivial if $a = 0$ or $b = 0$. There are two cases to consider. (1) If $a$ and $b$ have the same sign, we have
$|ab| = ab = |a| \cdot |b|$. (2) If $a$ and $b$ have opposite signs, without loss of generality say $b < 0$. Then
$|ab| = -ab = a(-b) = |a| \cdot |b|$. $\square$

Proof of 3: If $a|b$ then we have $ak = b$ for some integer $k$. Thus
$|a| \leq |a| \cdot |k| = |ak| = |b|$.

Proof of 4: Suppose by way of contradiction that $ab = 0$ and $b \neq 0$. Then using the previous propositions we have the following.
$|a| \leq |a| \cdot |b| = |ab| = |0| = 0$. Hence $a = 0$. Similarly, if $a \neq 0$, then $b = 0$. $\square$

Proof of 5: First note that $a,b \neq 0$. Now suppose otherwise; then without loss of generality, $|a| > 1$. Hence
$1 = |1| = |ab| = |a| \cdot |b| \geq |a| > 1$, a contradiction. $\square$

We now approach the main problem. Let $n$ be composite; then by definition we have $n = ab$ for some integers $a$ and $b$ with $a,b \neq \pm 1, \pm n$. Clearly $n|ab$. Now suppose by way of contradiction that $n|a$. Then we have $kn = a$ for some integer $k$. Now $kba = a$, so $(kb-1)a = 0$, so $kb = 1$. Thus $b = \pm 1$, a contradiction, so $n$ does not divide $a$. Similarly, $n$ does not divide $b$.