math.wiki
Logic, proof and discrete math › Proof techniques › Direct proof › Proving statements about even and odd numbers
Open on the map
Discrete Mathematics and Proof

Proving statements about even and odd numbers

Even and odd are about pairing things up. How do you turn that into a statement precise enough to prove things about every integer, including ones you could never pair by hand?

You need
Even and odd numbersGrade 2
Unlocks
Proof by casesDiscrete Mathematics and ProofThere are infinitely many primesDiscrete Mathematics and Proof
Where you are 2 in Direct proof
Logic, proof and discrete math6
Proof techniques14
Direct proof2
Proving statements about even and odd numbers
Proving statements about divisibility

When you reach for it

Whenever a claim mentions even or odd integers, or can be settled by asking whether some quantity is even or odd. Pairing objects (even and odd numbers) decides the parity of one number you can see. A proof has to decide it for a number written as a letter, for every integer at once, negative ones and 0 included. The move is always the same: replace the word “even” or “odd” by an equation, do algebra, and read the word back off the result.

This lesson takes two days. Part 1 sets out the definitions and proves the rules for sums, differences, products and powers. Part 2 uses parity as a tool: to show an equation has no integer solution, and to show a puzzle position can never be reached.

The procedure

Part 1: the definitions and the parity rules

An integer n is even if n = 2k for some integer k. It is odd if n = 2k + 1 for some integer k. Whether an integer is even or odd is its parity.

The definitions cover all of \mathbb{Z}. Zero is even, since 0 = 2 \cdot 0. Negative integers have a parity too: -6 = 2(-3) is even and -1 = 2(-1) + 1 is odd. For a positive integer, k is the number of pairs and the +1 is the one left over, which is exactly the pairing picture. The word “integer” on k is not decoration: 7 = 2 \cdot \tfrac{7}{2} does not make 7 even.

Theorem 1. Every integer is even or odd, and no integer is both.

Proof. Let n be an integer. By the division algorithm (used here without proof), dividing n by 2 gives n = 2q + r with q an integer and r equal to 0 or 1. If r = 0, then n is even; if r = 1, then n is odd.

Now suppose some integer were both, so that n = 2k and n = 2m + 1 for integers k and m. Then 2k = 2m + 1, so 2(k - m) = 1. Here k - m is an integer. But no integer j has 2j = 1: if j \le 0 then 2j \le 0, and if j \ge 1 then 2j \ge 2. This is impossible, so no integer is both even and odd. \square

The second half is what makes “not even” and “odd” interchangeable in a proof, a fact used in proof by contradiction.

Theorem 2 (sums and differences). For integers a and b, the sum a + b is even when a and b have the same parity and odd when they differ. The difference a - b has the same parity as a + b.

Proof. Two evens and two odds are proved in What may be assumed and what must be shown; Example “One letter or two” there shows why the two odd integers need two letters. For the mixed case, let a = 2k and b = 2m + 1. Then a + b = 2(k + m) + 1, and k + m is an integer, so a + b is odd. By the commutative property the order does not matter.

For the difference, write a - b = (a + b) - 2b. If a + b = 2j, then a - b = 2(j - b); if a + b = 2j + 1, then a - b = 2(j - b) + 1. Either way a - b has the parity of a + b. \square

Theorem 3 (products). A product of integers is odd exactly when every factor is odd.

For two factors this is two facts already proved: an even integer times any integer is even, and an odd times an odd is odd (exercises in What may be assumed and what must be shown; the second is also used in Modus ponens, chaining, and a common fallacy). For more factors, multiply one factor at a time: as long as every factor is odd, each new product is odd times odd, and once an even factor appears the product is even times an integer and stays even. (That “one at a time” is an informal induction.)

Powers. Taking every factor equal to n, Theorem 3 says that for any whole number p \ge 1, n^p is odd exactly when n is odd. So n^5, n^2 and n^{100} all have the parity of n. The exponent p = 0 is excluded, since n^0 = 1 is odd for every nonzero n.

Multiples. In the same way ca is even when c is even, and has the parity of a when c is odd. So 3a has the parity of a, while 4a is always even.

The rules together, where every entry has been proved:

aba + ba - bab
eveneveneveneveneven
evenoddoddoddeven
oddevenoddoddeven
oddoddevenevenodd

With these rules the parity of a long expression is found piece by piece, without expanding anything. A proof may cite them as theorems, the same way it cites the definitions.

Part 2: parity as a tool for impossibility

Two sides, two parities. If, for every choice of integers, one side of an equation is even and the other is odd, the equation has no integer solution. A solution would make one number both even and odd, against Theorem 1.

Theorem 4. A sum of r odd integers has the parity of r.

Proof. Write the odd integers as 2k_1 + 1, \ldots, 2k_r + 1. Their sum is 2(k_1 + \cdots + k_r) + r. The first part is even, so by Theorem 2 the sum has the parity of r. \square

Invariants. In a puzzle where moves change a position, an invariant is a quantity that no move changes. If the parity of some count is the same before and after every move, then every reachable position has the starting parity. A target with the other parity can never be reached, however many moves are tried. Proving this takes two lines: check what one move does to the count, and compare the start with the target.

Worked examples

Examples 1 to 4 go with Part 1, and Examples 5 to 7 with Part 2.

Example 1

Writing integers in the defining form

Show that -9 is odd and 0 is even, and that 4m^2 - 6m + 3 is odd for every integer m.

Solution

Each claim is settled by producing the integer k the definition asks for. For -9, take k = -5: -9 = 2(-5) + 1. The k for a negative odd number is the next integer down, not -4, since 2(-4) + 1 = -7. For 0, take k = 0: 0 = 2 \cdot 0.

For the expression, pull a 2 out of everything except a 1:

4m^2 - 6m + 3 = 2(2m^2 - 3m + 1) + 1.

Since m is an integer, 2m^2 - 3m + 1 is an integer (sums and products of integers are integers), so the expression is odd. Check at m = 2: 16 - 12 + 3 = 7, odd.

Example 2

A direct proof from the definitions

Prove: if a is odd and b is even, then a^2 + 3b is odd.

Solution

Proof. Let a be odd and b even. Then a = 2k + 1 and b = 2m for some integers k and m, with two letters because nothing says the two are related. Then

\begin{aligned} a^2 + 3b &= 4k^2 + 4k + 1 + 6m \\ &= 2(2k^2 + 2k + 3m) + 1. \end{aligned}

Since 2k^2 + 2k + 3m is an integer, a^2 + 3b is odd. \square

The rules from Part 1 give a second proof: a^2 is odd (odd times odd), 3b is even (a multiple of an even), and odd plus even is odd. Both are complete; the second reuses theorems instead of redoing their algebra.

Example 3

A power too large to expand

Prove that n^7 - 5n is even for every integer n.

Solution

Writing n = 2k + 1 and expanding (2k + 1)^7 would work but takes eight terms. The rules do it in one line.

Proof. Let n be an integer. By the rule for powers, n^7 has the parity of n. Since 5 is odd, 5n also has the parity of n. So n^7 and 5n have the same parity, and by Theorem 2 their difference is even. \square

Check at n = 3: 2187 - 15 = 2172, even. The proof never asked whether n itself is even or odd; it only needed the two terms to agree.

Example 4

The parity of an expression from the parities of its letters

For integers a and b, when is 3a + 5b odd? When is ab + a + b odd?

Solution

Since 3 and 5 are odd, 3a has the parity of a and 5b has the parity of b. So 3a + 5b has the parity of a + b: it is odd exactly when a and b have different parities.

For ab + a + b, enter each piece’s parity in a table, using the rules row by row.

ababab + a + b
eveneveneveneven
evenoddevenodd
oddevenevenodd
oddoddoddodd

So ab + a + b is odd unless both a and b are even. The same answer drops out of ab + a + b = (a + 1)(b + 1) - 1: the product is odd exactly when a + 1 and b + 1 are both odd, that is, when a and b are both even. Check: a = 2, b = 4 gives 14, and a = 3, b = 4 gives 19.

Example 5

Equations with no integer solution

Show that neither equation has a solution in integers: (a) 6x - 14y = 99; (b) x^5 + 3x - 11 = 0.

Solution

(a) For any integers x and y, 6x - 14y = 2(3x - 7y) is even, and 99 is odd. An integer solution would make one number both even and odd, which Theorem 1 rules out.

(b) For an integer x, both x^5 and 3x have the parity of x, so x^5 + 3x is even, and x^5 + 3x - 11 is even minus odd, which is odd. An odd number is not 0, which is even.

Part (b) says nothing about other numbers. The left side is -7 at x = 1 and 27 at x = 2, so a real solution lies between 1 and 2; it is just not an integer.

Example 6

Odd numbers that add to 100

Can 100 be written as a sum of nine odd integers (repeats and negatives allowed)? As a sum of ten?

Solution

Nine: no. By Theorem 4, a sum of nine odd integers has the parity of 9, so it is odd, and 100 is even.

Ten: yes. A sum of ten odd integers is even, so parity does not forbid it, and an example settles it: nine copies of 1 and one 91 give 9 + 91 = 100. Parity proved the “no”; the “yes” needed an example.

Example 7

Seven cups

Satu sets seven cups on a table, all mouth up. A move turns over exactly four of them (any four). Can she reach a position with all seven mouth down?

start: 0 down after one move: 4 down target: 7 down
Figure 1Each move turns over exactly four cups. The number of mouth-down cups is 0, then 4, and it can never be 7.
Solution

Let d be the number of mouth-down cups. Suppose a move turns over four cups, j of which are mouth down. Those j go up and the other 4 - j go down, so d becomes

d - j + (4 - j) = d + 4 - 2j.

The change 4 - 2j = 2(2 - j) is even, so the parity of d never changes. It starts at d = 0, even, so d is even after any number of moves. The target has d = 7, which is odd, so it can never be reached.

The invariant does not say which even values are reachable; that takes examples. Six down takes two moves: turn cups 1 to 4, then cups 1, 5, 6 and 7, leaving cups 2 to 7 down.

Boundaries

Parity is defined for integers only. \tfrac{7}{2} and 3.5 are neither even nor odd, and the k in each definition must be an integer, or every number would be “even”.

Parity rules out integer solutions, nothing more. Example 5(b) has a real solution; parity only shows no integer works.

An invariant proves impossibility, never possibility. A target with the right parity may still be out of reach (Exercise 22). Reaching a target needs an explicit sequence of moves.

Parity is coarse. It sees only the remainder on division by 2. Some impossibilities need more, as in Exercise 13, where a factor of 4 does the work; finer remainders are the subject of proofs with divisibility.

Where this goes next

Theorem 1 says every integer lands in one of two classes, so a claim can be proved by handling the even integers and the odd integers separately: that is proof by cases. Replacing “even” by “2 times an integer” is the first instance of a general move, replacing “a \mid b” by “b = a times an integer”, developed in divisibility as a relation and proofs with divisibility. Claims such as “if n^2 is odd, then n is odd” resist a direct start and are handled by contraposition, and the argument for infinitely many primes uses the same habit of turning a word into an equation.

Exercises

Part 1: the definitions

  1. Write each integer in the form 2k or 2k + 1 with k an integer: -1, -20, -35, and 2m - 9 for an integer m.
  2. Show that 10m^2 + 6m - 7 is odd for every integer m.
  3. Is \tfrac{10}{4} even, odd or neither? Is \tfrac{12}{4}?

Part 1: proving and using the rules

  1. Prove from the definitions: if a is odd and b is even, then a - b is odd.
  2. Prove from the definitions: if a and b are odd, then a - b is even.
  3. Prove: if a is odd, then a^2 + 4a + 2 is odd.
  4. Prove that n^3 - n^2 + n has the parity of n for every integer n.
  5. Let a and c be odd and b even. Find the parity of (a) a + b + c, (b) abc, (c) a^2 b + c, (d) 5a - 3c + b^4, (e) (a + b)^3.
  6. For which parities of a and b is 7a + 2b odd? For which is a^2 + ab odd?

Part 2: no integer solution

  1. Show that 4x + 10y = 51 has no solution in integers.
  2. Show that x^3 + 5x^2 = 2y + 1 has no solution in integers x and y.
  3. Show that xy(x + y) = 2025 has no solution in integers. (For the product to be odd, which factors would have to be odd?)
  4. Show that x^2 - y^2 = 2026 has no solution in integers. (Factor the left side, and compare the parities of x - y and x + y.)

Part 2: odd counts and invariants

  1. Can thirteen odd integers add up to 0? Can twelve?
  2. Jarmo writes 1, 2, \ldots, 10 on a board. A move erases two numbers and writes their difference, larger minus smaller. After nine moves one number is left. Can it be 0?
  3. Seven cups stand mouth up, and a move turns over exactly three of them. Show that all seven can be turned mouth down in three moves, and that it can never be done in an even number of moves.
  4. Number the rows and columns of a chessboard and give a square at row r and column c the number r + c. A knight moves two squares in one direction and one in the other. Show that a knight that returns to its starting square has made an even number of moves.
  5. Can signs be chosen in \pm 1 \pm 2 \pm 3 \pm \cdots \pm 10 to make the total 0? To make it 1?

Reasoning

  1. In the proof that no integer is both even and odd, why does it matter that k - m is an integer?
  2. Show that n is odd exactly when n = 2j - 1 for some integer j, so “odd” could have been defined that way.
  3. Show that x^3 + x + 3 = 0 has no integer solution, and find two consecutive integers with a real solution between them. What does parity tell you about real solutions?
  4. Three cups stand mouth up, and a move turns over all three. Show that a position with exactly one cup mouth down is never reached, although the number of down cups changes parity at every move, so parity alone does not forbid it after an odd number of moves.
  5. Let a_1, a_2, \ldots, a_7 be the numbers 1, 2, \ldots, 7 in some order. Prove that (a_1 - 1)(a_2 - 2) \cdots (a_7 - 7) is even.
Answers
  1. -1 = 2(-1) + 1, -20 = 2(-10), -35 = 2(-18) + 1, and 2m - 9 = 2(m - 5) + 1. So -20 is even and the other three are odd.
  2. 10m^2 + 6m - 7 = 2(5m^2 + 3m - 4) + 1, and 5m^2 + 3m - 4 is an integer, so the expression is odd.
  3. \tfrac{10}{4} = \tfrac{5}{2} is not an integer, so it is neither: parity is defined for integers only. \tfrac{12}{4} = 3 = 2 \cdot 1 + 1 is an integer, and it is odd. Parity belongs to the number, not to the way it is written.
  4. Let a = 2k + 1 and b = 2m. Then a - b = 2(k - m) + 1, and k - m is an integer, so a - b is odd.
  5. Let a = 2k + 1 and b = 2m + 1. Then a - b = 2(k - m), and k - m is an integer, so a - b is even.
  6. Let a = 2k + 1. Then a^2 + 4a + 2 = 4k^2 + 12k + 7, and this equals 2(2k^2 + 6k + 3) + 1, which is odd.
  7. n^3 and n^2 both have the parity of n, so n^3 - n^2 is even (Theorem 2). Adding n to an even number gives a number with the parity of n.
  8. (a) even: odd plus even is odd, plus odd is even. (b) even: it has the even factor b. (c) odd: a^2 b is even, plus odd. (d) even: 5a and 3c are odd, their difference is even, and b^4 is even. (e) odd: a + b is odd, and a power of an odd is odd.
  9. 2b is even and 7a has the parity of a, so 7a + 2b is odd exactly when a is odd, whatever b is. a^2 + ab = a(a + b) is odd exactly when a and a + b are both odd, that is, when a is odd and b is even.
  10. 4x + 10y = 2(2x + 5y) is even for all integers, and 51 is odd.
  11. x^3 and 5x^2 both have the parity of x, so x^3 + 5x^2 is even, while 2y + 1 is odd for every integer y.
  12. By Theorem 3, xy(x + y) is odd only if all three factors x, y and x + y are odd. But if x and y are odd, then x + y is even by Theorem 2. So the three factors are never all odd, xy(x + y) is always even, and 2025 is odd.
  13. x^2 - y^2 = (x - y)(x + y), and (x + y) - (x - y) = 2y is even, so the two factors have the same parity (Theorem 2). Since 2026 is even, Theorem 3 says one factor is even, so both are: x - y = 2s and x + y = 2t for integers s and t. Then the product is 4st, a multiple of 4, but 2026 = 4 \cdot 506 + 2 is not.
  14. Thirteen: no, the sum would be odd (Theorem 4) and 0 is even. Twelve: yes, six copies of 1 and six of -1.
  15. No. If the total is S and the move erases a \ge b, the new total is S - a - b + (a - b) = S - 2b, so the parity of the total never changes. It starts at 1 + 2 + \cdots + 10 = 55, odd, so the last number is odd.
  16. Turn cups \{1, 2, 3\}, then \{1, 4, 5\}, then \{1, 6, 7\}: cup 1 is turned three times and the rest once, so all end down. If a move turns j down cups up, the down count changes by (3 - j) - j = 3 - 2j, which is odd. So the count changes parity at every move, and after an even number of moves it is even, never 7.
  17. A knight’s move changes r + c by \pm 1 \pm 2 or \pm 2 \pm 1, which is \pm 1 or \pm 3, always odd. So the parity of r + c flips at every move. To return to the same square, and the same r + c, it must flip an even number of times.
  18. Not 0. If the terms given a minus sign add to N, the total is 55 - 2N, which is odd. To make 1, take N = 27 by giving the minus sign to 8, 9 and 10: the total is then 28 - 27 = 1, since 1 + 2 + \cdots + 7 = 28.
  19. The contradiction is that 2j = 1 has no integer solution j. Among rational numbers it has one, j = \tfrac{1}{2}, so without knowing k - m is an integer there is no contradiction.
  20. If n = 2k + 1, then n = 2(k + 1) - 1 with j = k + 1 an integer. If n = 2j - 1, then n = 2(j - 1) + 1 with k = j - 1 an integer. The two forms describe the same integers.
  21. x^3 and x have the same parity, so x^3 + x is even and x^3 + x + 3 is odd, never 0. The left side is -7 at x = -2 and 1 at x = -1, so a real solution lies between -2 and -1. Parity speaks only about integers; it says nothing about real solutions.
  22. Each move turns every cup over, so the position alternates: all up, all down, all up, and so on. Only those two positions ever occur, and neither has exactly one cup down. The down count goes 0, 3, 0, \ldots, so its parity does flip at every move, and after an odd number of moves it is odd, as 1 is. The parity test is passed and the target is still out of reach.
  23. The seven factors add to (a_1 + \cdots + a_7) - (1 + \cdots + 7) = 0, since the a_i are the same seven numbers. If every factor were odd, then by Theorem 4 a sum of seven odd integers would be odd, but 0 is even. So some factor is even, and by Theorem 3 the product is even.
kg1128 · updated 2026-10-22 · CC-BY-SA-4.0