The result of exercise suggests that the second apparent blind alley in the discussion of...

The result of exercise suggests that the second apparent blind alley in the discussion of Example 1 might not be a blind alley after all. Write a new proof of Theorem based on this observation.

Exercise

Prove that the product of any two consecutive integers is even.

Example 1

The Square of an Odd Integer

Prove: The square of any odd integer has the form 8m + 1 for some integer m.

Solution Begin by asking yourself, “Where am I starting from?” and “What do I need to show?” To help answer these questions, introduce variables to represent the quantities in the statement to be proved.

Formal Restatement:∀ odd integers n, ∃ an integer m such that n2 = 8m + 1. From this, you can immediately identify the starting point and what is to be shown.

Starting Point:Suppose n is a particular but arbitrarily chosen odd integer.

To Show:∃ an integer m such that n2 = 8m + 1.

This looks tough. Why should there be an integer m with the property that n2 = 8m + 1? That would say that (n2 − 1)/8 is an integer, or that 8 divides n2 − 1. Perhaps you could make use of the fact that n2 − 1 = (n − 1)(n + 1). Does 8 divide (n − 1)(n + 1)? Since n is odd, both (n − 1)and (n + 1)are even. That means that their product is divisible by 4. But that’s not enough. You need to show that the product is divisible by 8. This seems to be a blind alley.

You could try another tack. Since n is odd, you could represent n as 2q + 1 for some integer q. Then n2 = (2q + 1)2 = 4q2 + 4q + 1 = 4(q2 + q)+ 1. It is clear from this analysis that n2 can be written in the form 4m + 1, but it may not be clear that it can be written as 8m + 1. This also seems to be a blind alley.*

Yet another possibility is to use the result of Example 2. That example showed that any integer can be written in one of the four forms 4q, 4q + 1, 4q + 2, or 4q + 3. Two of these, 4q + 1 and 4q + 3, are odd. Thus any odd integer can be written in the form 4q + 1 or 4q + 3 for some integer q. You could try breaking into cases based on these two different forms

It turns out that this last possibility works! In each of the two cases, the conclusion follows readily by direct calculation. The details are shown in the following formal proof:

Theorem

The square of any odd integer has the form 8m + 1 for some integer m.

Proof:

Suppose n is a [particular but arbitrarily chosen] odd integer. By the quotient-remainder theorem, n can be written in one of the forms

4q or 4q +1 or 4q +2 or 4q + 3

for some integer q. In fact, since n is odd and 4q and 4q + 2 are even, n must have one of the forms

4q +1 or 4q + 3.

Case 1 (n=4q+1 for some integer q):[We must find an integer m such that n2 = 8m + 1.] Since n = 4q + 1,

Let m = 2q2 + q. Then m is an integer since 2 and q are integers and sums and products of integers are integers. Thus, substituting,

n2 = 8m + 1 where m is an integer.

Case 2 (n=4q +3 for some integer q):[We must find an integer m such that n2 = 8m + 1.] Since n = 4q + 3,

[The motivation for the choice of algebra steps was the desire to write the expression in the form 8•(some integer) + 1.]

Let m = 2q2 + 3q + 1. Then m is an integer since 1, 2, 3, and q are integers and sums and products of integers are integers. Thus, substituting,

n2 = 8m + 1 where m is an integer.

Cases 1 and 2 show that given any odd integer, whether of the form 4q + 1 or 4q + 3, n2 = 8m + 1 for some integer m. [This is what we needed to show.]

Example 2

Representations of Integers Modulo 4

Show that any integer can be written in one of the four forms

n = 4q or n = 4q +1 or n = 4q +2 or n = 4q + 3

for some integer q.

Solution Given any integer n, apply the quotient-remainder theorem to n with d = 4. This implies that there exist an integer quotient q and a remainder r such that

n = 4q + r and 0 ≤ r<4.

But the only nonnegative remainders r that are less than 4 are 0, 1, 2, and 3. Hence

n = 4q or n = 4q +1 or n = 4q +2 or n = 4q + 3

for some integer q.