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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: