Prove that if is composite then there are integers and such that divides but not or .

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

- If and , then .
- .
- If and , then .
- If then either or .
- If then either or .

Proof of 1: We proceed by induction on . First, note that the proposition is trivial for . Suppose now that the proposition is true for . Then for all , we have , so .

Proof of 2: Note that the proposition is trivial if or $b = 0$. There are two cases to consider. (1) If and have the same sign, we have

. (2) If and have opposite signs, without loss of generality say . Then

.

Proof of 3: If then we have for some integer . Thus

.

Proof of 4: Suppose by way of contradiction that and . Then using the previous propositions we have the following.

. Hence . Similarly, if , then .

Proof of 5: First note that . Now suppose otherwise; then without loss of generality, . Hence

, a contradiction.

We now approach the main problem. Let be composite; then by definition we have for some integers and with . Clearly . Now suppose by way of contradiction that . Then we have for some integer . Now , so , so . Thus , a contradiction, so does not divide . Similarly, does not divide .

### Like this:

Like Loading...

*Related*