Algebra Solutions: 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$ ,

If $a \geq 0$ and $b > 0$ , then $a \leq ab$ .
$|ab| = |a|\cdot|b|$ .
If $a|b$ and $b \neq 0$ , then $|a| \leq |b|$ .
If $ab = 0$ then either $b = 0$ or $a = 0$ .
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$ .

Algebra Solutions

An integer which divides a product need not divide either factor

No comments:

Post a Comment