PG2.1 Direct proof: even and odd numbers

Simulate

Check the claim with numbers

Add two odd numbers and the answer seems to be even every time: $3 + 5 = 8$ , and $7 + 11 = 18$ . Multiply them and the answer seems to be odd: $3 \cdot 5 = 15$ and $7 \cdot 11 = 77$ . The cell tests both claims on every pair of odd numbers from $-49$ to $49$ .

print(3 + 5, 7 + 11, 3 * 5, 7 * 11) odds = [n for n in range(-49, 50) if n % 2 == 1] pairs = [(m, n) for m in odds for n in odds] print("odd numbers:", len(odds), " pairs:", len(pairs)) print("pairs with an odd sum:", sum((m + n) % 2 == 1 for m, n in pairs)) print("pairs with an even product:", sum((m * n) % 2 == 0 for m, n in pairs))

⌘/Ctrl + Enter runs the cell

There are 50 odd numbers in the range and 2,500 pairs. Not one pair has an odd sum, and not one has an even product. Here is a bolder guess: the sum of two odd numbers is always 2 more than a multiple of 4, as in $3 + 3 = 6$ .

odds = [n for n in range(-49, 50) if n % 2 == 1] fails = [(m, n) for m in odds for n in odds if (m + n) % 4 != 2] print("3 + 3 =", 3 + 3) print("pairs where it fails:", len(fails)) print("does it fail for 1 and 3?", (1, 3) in fails, " 1 + 3 =", 1 + 3) print("does it fail when m = n?", any(m == n for m, n in fails))

⌘/Ctrl + Enter runs the cell

The bolder guess fails for 1,250 pairs, such as 1 and 3, whose sum is 4. It never fails when the two numbers are equal. Keep that in mind: one of the proofs below "proves" this false guess.

Conjecture

m

Every one of 2,500 pairs agrees. That is evidence, not a proof: there are infinitely many odd numbers, and the claim is about all of them.

Definitions, then a direct proof

A proof about even and odd numbers cannot rest on examples. It needs definitions, so that "even" becomes something algebra can work with. Here $\mathbb{Z}$ is the set of integers, as in lesson 0.2.1.

Rule: Even and odd

\begin{gathered} n \text{ is even if } n = 2k \\ n \text{ is odd if } n = 2k + 1 \\ \text{for some } k \in \mathbb{Z} \end{gathered}

So $14 = 2 \cdot 7$ is even and $-3 = 2 \cdot (-2) + 1$ is odd. Every integer is even or odd, because dividing by 2 leaves a remainder of 0 or 1.

No integer is both. If $2a = 2b + 1$ for integers $a$ and $b$ , then $a - b = \tfrac{1}{2}$ , which is not an integer.

k

⌘/Ctrl + Enter runs the cell

A direct proof of "if $P$ , then $Q$ " assumes $P$ and works forwards to $Q$ . With definitions it has three moves: unpack the hypothesis into algebra, rearrange, then pack the result into the form the conclusion's definition asks for.

Format 1

Reorder the steps

Here is a direct proof that the sum of two odd integers is even, with its lines shuffled. Put them in order.

The number $a + b + 1$ is an integer, because sums of integers are integers.
Take out the factor 2: $m + n = 2(a + b + 1)$ .
So $m + n$ is 2 times an integer, which is the definition of even.
Let $m$ and $n$ be odd integers.
By the definition of odd, $m = 2a + 1$ and $n = 2b + 1$ for some integers $a$ and $b$ .
Add them: $m + n = 2a + 2b + 2$ .

Format 2

Fill the gap

Now the product. Fill each gap as you would a quick answer, such as 2a+b, then check.

m

How to type answers

Powers with ^, brackets round a power that is a sum: r^k, r^(k+1).
Fractions with / and brackets: (1-r)/(1+r). Multiply with * or side by side: 2k+1.
Press Enter in any box to check them all.

Format 3

Find the error

This proof claims that the sum of two odd numbers is always 2 more than a multiple of 4. The simulation found that false for 1 and 3. Select the faulty line, then say what is wrong with it.

Simulate

A claim of your own to prove

Square some odd numbers and subtract 1, then divide by 4. Each row prints $n$ , $n^2$ , the quotient and the remainder.

for n in [1, 3, 5, 7, 9, -3, -7]: print(n, n**2, (n**2 - 1) // 4, (n**2 - 1) % 4) odds = [n for n in range(-999, 1000) if n % 2 == 1] print("odd squares that are 1 more than a multiple of 4:", sum(n**2 % 4 == 1 for n in odds), "of", len(odds)) print("1 more than a multiple of 4, but not a square:", [q for q in range(1, 30) if q % 4 == 1 and int(q**0.5)**2 != q])

⌘/Ctrl + Enter runs the cell

Every remainder is 0, so each odd square is 1 more than a multiple of 4: $9 = 4 \cdot 2 + 1$ and $49 = 4 \cdot 12 + 1$ . All 1,000 odd numbers from $-999$ to $999$ agree. The converse fails, though: 5, 13 and 17 are 1 more than a multiple of 4 but are not squares.

Conjecture

n

A thousand cases agree. Prove it for every odd integer with the three moves of a direct proof.

Format 4

Write it

Prove that the square of every odd integer is 1 more than a multiple of 4. That is, for every odd $n$ there is an integer $m$ with $n^2 = 4m + 1$ .

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

n

Direct proof: even and odd numbers

Check the claim with numbers

Definitions, then a direct proof

Rule: Even and odd

Reorder the steps

Fill the gap

Find the error

A claim of your own to prove

Write it

Summary card

Free further reading