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:
Definition: If n and d are integers and d ¹ ,0 then n is divisible by d if, and only if, n = d×k for some integer k. We say d divides n, denoted d  n. Symbolically, d  n « $ k Î Z such that n = d×k.
The negation of d divides n is a universal statement: " integers k, n ¹ d×k. (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:
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:
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 selfcontained.
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 ifthen 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 lowestterm
form.
(j/k)^{2} 
= 
2 
by assumption 
j^{2} 
= 
2k^{2} 
multiply by k^{2} 
So j^{2} is even. This implies the j is even. Thus j = 2n for some integer n. Now,
2k^{2} = j^{2} = (2n)^{2} = 4n^{2}
2k^{2} 
= 
4n^{2} 
from above 
k^{2} 
= 
2n^{2} 
divide by 2 
Thus k^{2} 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.