3.2: Direct Proofs
( \newcommand{\kernel}{\mathrm{null}\,}\)
Preview Activity 1 (Definition of Divides, Divisor, Multiple, is Divisible by)
In Section 3.1, we studied the concepts of even integers and odd integers. The definition of an even integer was a formalization of our concept of an even integer as being one this is “divisible by 2,” or a “multiple of 2.” We could also say that if “2 divides an integer,” then that integer is an even integer. We will now extend this idea to integers other than 2. Following is a formal definition of what it means to say that a nonzero integer
Definition of Divides
A nonzero integer
A Note about Notation: Be careful with the notation
The definition for “divides” can be written in symbolic form using appropriate quantifiers as follows: A nonzero integer
Restated, let
divides , is a divisor of , is a factor of , is a multiple of , and is divisible by .
They all mean
Given the initial conditions, there exists an integer
In terms of division, we say that
The definition of divisibility is very important. Many students fail to finish very simple proofs because they cannot recall the definition. So here we go again:
Both integers
Example
Since
hands-on exercise
-
Use the definition of divides to explain why 4 divides 32 and to explain why 8 divides -96.
-
Give several examples of two integers where the first integer does not divide the second integer.
-
According to the definition of “divides,” does the integer 10 divide the integer 0? That is, is 10 a divisor of 0? Explain.
-
Use the definition of “divides” to complete the following sentence in symbolic form: “The nonzero integer
does not divide the integer means that ....” -
Use the definition of “divides” to complete the following sentence without using the symbols for quantifiers: “The nonzero integer
does not divide the integer . ....” -
Give three different examples of three integers where the first integer divides the second integer and the second integer divides the third integer.
hands-on exercise
Verify that
Definition of Prime & Composite
An integer
An integer
Notes:
- The integer 1 is neither prime nor composite.
- A positive integer
is composite if it has a divisor that satisfies .
With our definition of "divisor" we can use a simpler definition for prime, as follows.
Definition
An integer
Example
The integers
hands-on exercise
What are the next five primes after 23?
Sometimes, we can use a constructive proof when a proposition claims that certain values or quantities exist.
Example
Given any positive integer
- Solution
-
For each positive integer
, we claim that the integers are composite. Here is the reason. For each , where , the integer is divisible by and greater than , and hence is composite.
hands-on Exercise
Construct five consecutive positive integers that are composite. Verify their compositeness by means of factorization.
Theorem Consecutive Integers have opposite parity
This is a theorem you can refer to in later work. The proof of this theorem illustrates a technique called "Proof by Cases".
- Proof
-
Let
be any integer. is the next consecutive integer, by the meaning of consecutive.We will consider two cases.
Case 1:
is even.Since
is even, there exists an integer k such that by the definition of even. by substitution. Thus is odd by definition of odd. We have is even and is odd, so in this case, these consecutive integers have opposite parity.Case 2:
is odd.Since
is odd, there exists an integer j such that by the definition of odd. by substitution. By algebra, . Since is closed under addition, is an integer. Thus is even by definition of even. We have is odd and is even, so in this case, these consecutive integers have opposite parity.We know by the Parity Property that
is either even or odd, so we have covered all cases. Consecutive integers have opposite parity.
Proof by Cases
When writing a proof by cases be careful to
- clearly define what each case is
- prove each case thoroughly
- include a justification that all cases have been covered (this might be at the start or the end of the set of cases)
- see more examples of proof by cases in the next section
hands-on exercise
Show that
Theorem The Fundamental Theorem of Arithmetic or Prime Factorization Theorem
-
Each natural number greater than 1 is either a prime number or is a product of prime numbers.
-
let
with . Assume that
where and are prime with and . Then , and for each from 1 to , .
- Proof
-
The proof uses mathematical induction. This is a proof technique we will be covering soon.
Definition
Let
Some Mathematical Terminology
In Section 1.2, we introduced the idea of a direct proof. Since then, we have used some common terminology in mathematics without much explanation. Before we proceed further, we will discuss some frequently used mathematical terms.
A proof in mathematics is a convincing argument that some mathematical statement is true. A proof should contain enough mathematical detail to be convincing to the person(s) to whom the proof is addressed. In essence, a proof is an argument that communicates a mathematical truth to another person (who has the appropriate mathematical background). A proof must use correct, logical reasoning and be based on previously established results. These previous results can be axioms, definitions, or previously proven theorems. These terms are discussed below.
Surprising to some is the fact that in mathematics, there are always undefined terms. This is because if we tried to define everything, we would end up going in circles. Simply put, we must start somewhere. For example, in Euclidean geometry, the terms “point,” “line,” and “contains” are undefined terms. In this text, we are using our number systems such as the natural numbers and integers as undefined terms. We often assume that these undefined objects satisfy certain properties. These assumed relationships are accepted as true without proof and are called axioms (or postulates). An axiom is a mathematical statement that is accepted without proof. Euclidean geometry starts with undefined terms and a set of postulates and axioms. For example, the following statement is an axiom of Euclidean geometry:
Given any two distinct points, there is exactly one line that contains these two points.
The closure properties of the set of integers discussed in Section 3.1 are being used as axioms in this text.
A definition is simply an agreement as to the meaning of a particular term. For example, in this text, we have defined the terms “even integer” and “odd integer.” Definitions are not made at random, but rather, a definition is usually made because a certain property is observed to occur frequently. As a result, it becomes convenient to give this property its own special name. Definitions that have been made can be used in developing mathematical proofs. In fact, most proofs require the use of some definitions.
In dealing with mathematical statements, we frequently use the terms “conjecture,” “theorem,” “proposition,” “lemma,” and “corollary.” A conjecture is a statement that we believe is plausible. That is, we think it is true, but we have not yet developed a proof that it is true. A theorem is a mathematical statement for which we have a proof. A term that is often considered to be synonymous with “theorem” is proposition.
Often the proof of a theorem can be quite long. In this case, it is often easier to communicate the proof in smaller “pieces.” These supporting pieces are often called lemmas. A lemma is a true mathematical statement that was proven mainly to help in the proof of some theorem. Once a given theorem has been proven, it is often the case that other propositions follow immediately from the fact that the theorem is true. These are called corollaries of the theorem. The term corollary is used to refer to a theorem that is easily proven once some other theorem has been proven.
Example
Suppose we have proved the "Even Product Theorem": The product of any two even integers is an even integer.
Do you see how the related statement could be called a Corollary to the Even Product Theorem: The square of any even integer is even.
Why is this a corollary to the Even Product Theorem and what is the proof of this corollary?
- Solution
-
The square of any even integer is even is a corollary to the Even Product Theorem because it follows that theorem almost immediately.
The square of any even integer is even.
Proof:
Let be any even integer. Since means we know is the product of two even integers, thus by the Even Product Theorem, is even. Therefore, the square of any even integer is even.
Summary and Review
- To prove an implication
, start by assuming that is true. Use the information from this assumption, together with any other known results, to show that must also be true. - If necessary, you may break
into several cases , and prove each implication (separately, one at a time) as indicated above. - Be sure to write the mathematical expressions clearly. Use different variables if the quantities involved may not be the same.
- To get started, write down the given information, the assumption, and what you want to prove.
- In the next step, use the definition if necessary, and rewrite the information in mathematical notations. The point is, try to obtain some mathematical equations or logical statements that we can manipulate.
- If you are stuck, think about the how the proof will end & write that down. Sometimes it helps to work backwards.
Exercises
Exercise
Prove or disprove:
- Solution
-
Consider
is a nonnegative integer.
is not prime, since ( , thus the statement: is prime for all nonnegative integer is false.
Exercise
Prove if
- Hint
-
Use proof by cases.
Exercise
Let
- Show that if
is odd, then is also odd. - Show that if
is odd, then is also odd. - A corollary is a result that can be derived easily from another result. Derive (b) as a corollary of (a).
- Show that if
and are odd, then so is . - Show that if
is even, and is odd, then is even.
- Solution to (a)
-
If
is odd, then is also odd.
Proof: Let be any odd integer. By definition of odd,
by substitution. Then by algebra,
Since the set of integers is closed under multiplication and addition, .
So, by the definition of odd, is odd.
Therefore, if is odd, then is also odd.
Exercise
Prove that, for any odd integer
Exercise
Let
- Prove that if
is a multiple of 3, then is also a multiple of 3. - Prove that if
is a multiple of 7, then is also a multiple of 7.
- Solution to (a)
-
If
is a multiple of 3, then is also a multiple of 3.
Proof: Let be any multiple of 3. By definition of multiple, there exists an integer such that
by substitution. Then by algebra,
Since the set of integers is closed under multiplication, .
So, by the definition of multiple, is a multiple of 3.
Therefore, if is a multiple of 3, then is also a multiple of 3.
Exercise
Prove that if
Exercise
Prove that if
Exercise
Recall that we can use a counterexample to disprove an implication. Show that the following claims are false:
- If
and are integers such that , then . - If
is a positive integer, then is prime.
Exercise
Explain why the following arguments are invalid:
- Let
be an integer. If is odd, then is odd. Therefore, must be odd. - Let
be an integer. If is even, then is also even. As an integer, could be odd. Hence, cannot be even. Therefore, must be odd.
- Solution
-
(a) There is no information about
, so the statement "if is odd, then is odd" is irrelevant to the parity of
(b) could be odd, but we also have could be even. So, we do not have enough information to determine the parity of
Exercise
Analyze the following reasoning:
- Let
be a set of real numbers. If is in , then is in . But is not in , hence is not in . - Let
be a set of real numbers. If is in , then is in . Therefore, if is in , then is in .
Exercise
Show that there exists an integer
- Solution
-
Consider
. The numbers are
Exercise
Prove: If