Elementary Number Theory and Methods of Proof

Properties of Integers
Proving Existential Statements
Universal Statements and Basic Techniques of Direct Proof
Common Mistakes
Getting Proofs Started
Disproof by Counterexample
Proof by Contradiction

We begin with some basic number theory. The set of integers is closed under addition, subtraction, and multiplication. Consequently, sums, differences, and products of integers are integers. Does this property hold for division? Integers come in one of two forms, an integer is either even or it is odd.

Definition: An integer n is even if, and only if, n = 2k for some integer k. An integer n is odd if and only if, n = 2k + 1 for some integer k. Symbolically, if n is an integer, then

n is even $ an integer k such that n = 2k.

n is odd $ an integer k such that n = 2k + 1.

These are equivalence relationships, it follows that both the conditional (p only if q) and its converse (p if q) are true.

Some practice with our definition:

  1. Is 0 even?
  2. Is -515 odd?
  3. If a and b are integers, is 6a2b3 even? Why?
  4. If a and b are integers, is 10a2 + 6b3 + 1 even? Why?

Definition: If n and d are integers and d ,0 then n is divisible by d if, and only if, n = dk for some integer k. We say d divides n, denoted d | n. Symbolically, d | n $ k Z such that n = dk.  

The negation of d divides is a universal statement: " integers k, n dk. (In words: the quotient n/d is not an integer.)

The floor of x, or greatest integer in x, denoted x , is the integer immediately to the left of x on the number line. So 1.95 = 1 and  -1.95 = -2. Similarly, the ceiling of x, denoted x , is the integer immediately to the right of x on the number line. So 1.1 = 2, and  -1.1 = -1.

Definition: Given any real number x, the floor of x, denoted x , is the unique integer n such that n < x < n + 1.

Definition: Given any real number x, the ceiling of x, denoted x , is the unique integer n such that n - 1 < x < n.

Question: " x, y , x - y = x - y ?

Constructive Proofs of Existence, Ex. 3.1.3 top

Prove the following:

  1. $ an even integer n that can be written in two ways as a sum of two prime numbers.
    Solution: Let n = 14. Then 14 = 11 + 3 = 7 + 7 and 3, 7, and 11 are all prime numbers.
  2. $ an integer k such that 14r + 6s = 2k, where r and s are integers.
    Solution: Let k = 7r + 3s. Then k is an integer since it is the sum of products of integers; and by substitution, 2k = 2(7r + 3s).

Nonconstructive Proof of Existence
Either (a) existence of a value of x that makes Q(x) true is guaranteed by an axiom or a previously proved theorem or (b) the assumption that there is no such x leads to a contradiction.

Disadvantage: May give virtually no clue about where or how x may be found. Particularly for computers, it is better to have specific directions for the calculation of the quantity in question.

Proving Universal Statements

Method of Exhaustion
Even for finite sets, this method may take unreasonable time. A computer program with exponential complexity could take centuries to solve a problem with as little as 32 variables. However an algorithm with polynomial complexity may solve the same problem in a few hours.

Method of Generalizing from the Generic to the Particular top

To show that every element of a domain satisfies a certain property, suppose x is a particular but arbitrarily chosen element of the domain and show that x satisfies the property. Suppose the property is of the form "" x D, if P(x) then Q(x)." To show this statement is true we suppose x is a particular but arbitrarily chosen element of D that satisfies P(x), and then show that x satisfies Q(x). This is called the method of direct proof. The steps are:

  1. Express the statement to be proved in the form "" x D, if P(x) then Q(x)."
  2. Start the proof by supposing that x is a particular but arbitrarily chosen element of D for which the hypothesis P(x) is true.
  3. Show that the conclusion Q(x) is true by using definitions, previously established results, and the rules for logical inference.

Theorem 3.1.1 If the sum of any two integers is even, then so is their difference.

[Formal Restatement:] " m and n Z, if m + n is even then m - n is even.

Proof:
Suppose m and n are [particular but arbitrarily chosen] integers so that m + n is even. [We must show that m - n is even.] By definition of even, m + n = 2k for some integer k. Subtracting n from both sides gives m = 2k - n. So

m - n

=

(2k - n) - n

by substitution

 

=

2k - 2n

by combining like terms

 

=

2(k - n)

by factoring.

But k - n is an integer because it is a difference of integers. Hence m - n equals 2 times an integer, and so by definition of even, m - n is even.

Directions for Writing Proofs of Universal Statements
Writing proofs is similar to writing a computer program based on a set of specifications: organize your thoughts, declare your variables, document thoroughly [italicized brackets here], and follow a logical progression. Some general directions for proof writing:

o        Write the theorem to be proved.

o        Clearly mark the beginning of your proof with the word proof.

o        Make your proof self-contained.

o        Write proofs in complete English sentences.

This is true because if m = 14 and n = 6, then m + n = 20, which is even,
and m - n = 8 which is also even.

Suppose m and n are odd numbers. Then by definition of odd, m = 2k + 1
and n = 2k + 1 for some integer k.

Suppose m and n are integers and m + n is even. Then by definition of even,
m +n = 2k for some integer k. Then m = 2k - n, and so m - n is even.

Suppose p is a prime number. If p is prime [incorrect use of "if", the
primeness of p is not in doubt as we have supposed it]
, then p
cannot be written as a product of two smaller positive integers.

Getting Proofs Started top
Understanding the ideas of generalizing from the generic particular and the method of direct proof, allows one to write the beginnings of a proof even for a theorem not well understood. The beginning of a proof should be clearly marked and contain:

1.      The names of the variables and state the kinds of objects they are.

2.      Supposition of the hypothesis of the if-then statement.

3.      What is to be shown.

Given the statement

" x D, if P(x) then Q(x),

the beginning of our proof should contain " x D, suppose P(x) and a remark on what is to be shown.

Example: Write the beginning of a proof for the statement "" G, if G is a complete, bipartite graph then G is connected."
Starting point: Suppose G is a particular but arbitrarily chosen complete, bipartite graph.
To show: G is connected.
Our final solution for the beginning of a proof is then:
Proof: Suppose G is a particular but arbitrarily chosen complete, bipartite graph. [We must show that G is connected.]

Disproof by Counterexample top
Consider the question of disproving the statement " x D, if P(x) then Q(x). Showing that this statement is false is equivalent to showing that its negation is true. The negation of this statement is $ x in D such that P(x) and not Q(x). So by finding a value of x in D for which P(x) is true and Q(x) is false, we prove the negation of the original statement. The value of x for which the negation of a statement is true is called a counterexample. To disprove a universally quantified conditional statement, one need only find a single counterexample.

Proof by Contradiction top
This technique is based on assuming the existence of elements in the domain that satisfy the hypothesis and not the conclusion, which then leads logically to a contradiction. Sometimes the negation of a statement is easier to disprove (leads to a contradiction) than the original statement is to prove.

Example: Prove that there is no rational number j/k whose square is 2. In other words, show that the square root of 2 is irrational. (This statement is a good candidate for proof by contradiction since we could not check all possible rational numbers to demonstrate that none has a square root of 2.)

Proof: Suppose (j/k)2 = 2 for some integers j and k, which have no common factors.
Now if the original choice of j/k is not in lowest terms, we can factor out any common factors and replace it with its equivalent lowest-term form.

(j/k)2

=

2

by assumption

j2

=

2k2

multiply by k2

So j2 is even. This implies the j is even. Thus j = 2n for some integer n. Now,

2k2 = j2 = (2n)2 = 4n2

2k2

=

4n2

from above

k2

=

2n2

divide by 2

Thus k2 is even, and so k is even. We now have that both j and k are even and therefore have a common factor of 2. This is a contradiction to our assumption. Hence the assumption is false and we have proven that there is no rational number whose square is 2, i.e. the square root of 2 is irrational.