3.2: Direct Proofs

Last updated
Save as PDF

Page ID: 24456

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

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 $m$ divides an integer $n$.

Definition of Divides

A nonzero integer $m$ divides an integer $n$ provided that there is an integer $q$ such that $n = m \cdot q$. We also say that $m$ is a divisor of $n$, $m$ is a factor of $n$, $n$ is divisible by $m$, and $n$ is a multiple of $m$. The integer 0 is not a divisor of any integer. If $a$ and $b$ are integers and $a \ne 0$, we frequently use the notation $a | b$ as a shorthand for “$a$ divides $b$.”

A Note about Notation: Be careful with the notation $a | b$. This does not represent the rational number $\dfrac{a}{b}$. The notation $a | b$ represents a relationship between the integers $a$ and $b$ and is simply a shorthand for “$a$ divides $b$.” "Divides" as in $a | b$ is a relation (true or false), while "divided by" as in $\dfrac{a}{b}$ or $a/b$ is an operation (results in a number) .

The definition for “divides” can be written in symbolic form using appropriate quantifiers as follows: A nonzero integer $m$ divides an integer $n$ provided that $(\exists q \in \mathbb{Z})(n = m \cdot q)$.

Restated, let $a$ and $b$ be two integers such that $a \neq 0$, then the following statements are equivalent:

$a$ divides $b$,
$a$ is a divisor of $b$,
$a$ is a factor of $b$,
$b$ is a multiple of $a$, and
$b$ is divisible by $a$.

They all mean

Given the initial conditions, there exists an integer $q$ such that $b=aq.$

In terms of division, we say that $a$ divides $b$ if and only if the remainder is zero when $b$ is divided by $a$. We adopt the notation \[a \mid b \qquad \mbox{[spoken as "$a$ divides $b$'']}\] Do not use a forward slash $/$ or a backward slash $\backslash$ in the notation. To say that $a$ does not divide $b$, we add a slash across the vertical bar, as in

\[a \nmid b \qquad \mbox{[spoken as "$a$ does not divide $b$'']}\]

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:

$a\mid b\;\Leftrightarrow\;b=aq$ for some integer $q$.

Both integers $a$ and $b$ can be positive or negative, and $b$ could even be 0. The only restriction is $a\neq0$. In addition, $q$ must be an integer. For instance, $3 = 2\cdot\frac{3}{2}$, but it is certainly absurd to say that 2 divides 3.

Example $\PageIndex{1}\label{eg:divides-01}$

Since $14=(-2)\cdot(-7)$, it is clear that $-2\mid 14$.

hands-on exercise $\PageIndex{1}\label{he:divides-01}$

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 $m$ does not divide the integer $n$ means that ....”
Use the definition of “divides” to complete the following sentence without using the symbols for quantifiers: “The nonzero integer $m$ does not divide the integer $n$. ....”
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 $\PageIndex{2}\label{he:divides-02}$

Verify that \[5 \mid 35, \quad 8\nmid 35, \quad 25\nmid 35, \quad 7 \mid 14, \quad 2 \mid -14, \quad\mbox{and}\quad 14\mid 14,\] by finding the quotient $q$ and the remainder $r$ such that $b=aq+r$, and $r=0$ if $a\mid b$.

Definition of Prime & Composite

An integer $p>1$ is a prime if $\forall a,b \in \mathbb{Z},$ if $ab=p$ then either $a=p\wedge b=1$ or $a=1 \wedge b=p$

An integer $n>1$ is a composite if $\exists a,b \in \mathbb{Z}\, (ab=n) $ with $1<a<n \wedge 1<b<n $.

Notes:

The integer 1 is neither prime nor composite.
A positive integer $n$ is composite if it has a divisor $d$ that satisfies $1<d<n$.

With our definition of "divisor" we can use a simpler definition for prime, as follows.

Definition

An integer $p>1$ is a prime if its positive divisors are 1 and $p$ itself. Any integer greater than 1 that is not a prime is called composite.

Example $\PageIndex{2}\label{eg:divides-02}$

The integers $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots\,$ are primes.

hands-on exercise $\PageIndex{3}\label{he:divides-03}$

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 $\PageIndex{3}\label{eg:pfintro-03}$

Given any positive integer $n$, show that there exist $n$ consecutive composite positive integers.

Solution: For each positive integer $n$, we claim that the $n$ integers \[(n+1)!+2, \quad (n+1)!+3, \quad \ldots \quad (n+1)!+n, \quad (n+1)!+(n+1)\] are composite. Here is the reason. For each $i$, where $2\leq i\leq n+1$, the integer \[\begin{aligned} (n+1)!+i &=& 1\cdot2\cdot3\,\cdots(i-1)i(i+1)\cdots\,(n+1)+i \\ &=& i\,[\,1\cdot2\cdot3\,\cdots(i-1)(i+1)\cdots\,(n+1)+1\,] \end{aligned}\] is divisible by $i$ and greater than $i$, and hence is composite.

hands-on Exercise $\PageIndex{4}\label{he:pfintro-04}$

Construct five consecutive positive integers that are composite. Verify their compositeness by means of factorization.

Theorem $\PageIndex{1}$ 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 $n$ be any integer. $n+1$ is the next consecutive integer, by the meaning of consecutive.

We will consider two cases.

Case 1: $n$ is even.

Since $n$ is even, there exists an integer k such that $n=2k$ by the definition of even.

$n+1=2k+1$ by substitution. Thus $n+1$ is odd by definition of odd. We have $n$ is even and $n+1$ is odd, so in this case, these consecutive integers have opposite parity.

Case 2: $n$ is odd.

Since $n$ is odd, there exists an integer j such that $n=2j+1$ by the definition of odd.

$n+1=2j+1+1$ by substitution. By algebra, $n+1=2j+2=2(j+1)$. Since $\mathbb{Z}$ is closed under addition, $j+1$ is an integer. Thus $n+1$ is even by definition of even. We have $n$ is odd and $n+1$ is even, so in this case, these consecutive integers have opposite parity.

We know by the Parity Property that $n$ is either even or odd, so we have covered all cases.

$\therefore$ 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 $\PageIndex{5}\label{he:directpf-05}$

Show that $n^3+n$ is even for all $n\in\mathbb{N}$.

Theorem $\PageIndex{2}$ 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 $n \in \mathbb{N}$ with $n > 1$. Assume that
\[n = p_{1}p_{2}\cdot\cdot\cdot p_{r} \text{ and that } n = q_{1}q_{2}\cdot\cdot\cdot q_{s},\]
where $p_{1}p_{2}\cdot\cdot\cdot p_{r}$ and $q_{1}q_{2}\cdot\cdot\cdot q_{s}$ are prime with $p_{1} \le p_{2} \le \cdot\cdot\cdot \le p_{r}$ and $q_{1} \le q_{2} \le \cdot\cdot\cdot \le q_{s}$. Then $r = s$, and for each $j$ from 1 to $r$, $p_{j} = q{j}$.

Proof: The proof uses mathematical induction. This is a proof technique we will be covering soon.

Definition

Let $a$ and $b$ be integers, not both 0. A common divisor of $a$ and $b$ is any nonzero integer that divides both $a$ and $b$. The largest natural number that divides both $a$ and $b$ is called the greatest common divisor of $a$ and $b$. The greatest common divisor of $a$ and $b$ is denoted by gcd($a$, $b$).

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 $\PageIndex{4}$

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 $x$ be any even integer. Since $x^2$ means $(x)(x)$ we know $x^2$ is the product of two even integers, thus by the Even Product Theorem, $x^2$ is even. Therefore, the square of any even integer is even. $W^5$

Summary and Review

To prove an implication $p\Rightarrow q$, start by assuming that $p$ is true. Use the information from this assumption, together with any other known results, to show that $q$ must also be true.
If necessary, you may break $p$ into several cases $p_1, p_2, \ldots\,$, and prove each implication $p_i\Rightarrow q$ (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 $\PageIndex{1}\label{ex:directpf-01}$

Prove or disprove: $2^n+1$ is prime for all nonnegative integer $n$.

Solution: Consider $n=3;$ $n$ is a nonnegative integer. \[2^n+1=2^3+1=9.\]
$9$ is not prime, since ($3)(3)=9$, thus the statement: $2^n+1$ is prime for all nonnegative integer $n$ is false.

Exercise $\PageIndex{2}\label{ex:directpf-02}$

Prove if $n$ is an integer, then $n^2$ has the same parity as $n$.

Hint: Use proof by cases.

Exercise $\PageIndex{3}\label{ex:directpf-03}$

Let $n$ be an integer.

Show that if $n$ is odd, then $n^2$ is also odd.
Show that if $n$ is odd, then $n^4$ 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 $m$ and $n$ are odd, then so is $mn$.
Show that if $m$ is even, and $n$ is odd, then $mn$ is even.

Solution to (a)

If $n$ is odd, then $n^2$ is also odd.
Proof: Let $n$ be any odd integer. By definition of odd, $\exists k \in \mathbb{Z}(n=2k+1).$
$n^2=(2k+1)^2,$ by substitution. Then by algebra, $n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1.$
Since the set of integers is closed under multiplication and addition, $(2k^2+2k)\in \mathbb{Z}$.
So, by the definition of odd, $n^2$ is odd.
Therefore, if $n$ is odd, then $n^2$ is also odd.

$W^5$

Exercise $\PageIndex{4}\label{ex:directpf-04}$

Prove that, for any odd integer $n$, the number $2n^2+5n+4$ must be odd.

Exercise $\PageIndex{5}\label{ex:directpf-05}$

Let $n$ be an integer.

Prove that if $n$ is a multiple of 3, then $n^2$ is also a multiple of 3.
Prove that if $n$ is a multiple of 7, then $n^3$ is also a multiple of 7.

Solution to (a)

If $n$ is a multiple of 3, then $n^2$ is also a multiple of 3.
Proof: Let $n$ be any multiple of 3. By definition of multiple, there exists an integer $k$ such that $n=3k.$
$n^2=(3k)^2,$ by substitution. Then by algebra, $n^2=(3k)^2=9k^2=3(3k^2).$
Since the set of integers is closed under multiplication, $(3k^2)\in \mathbb{Z}$.
So, by the definition of multiple, $n^2$ is a multiple of 3.
Therefore, if $n$ is a multiple of 3, then $n^2$ is also a multiple of 3.

$W^5$

Exercise $\PageIndex{6}\label{ex:directpf-06}$

Prove that if $a \mid b$ and $c \mid (-a)$ then $(-c) \mid b$

Exercise $\PageIndex{7}\label{ex:directpf-07}$

Prove that if $ac \mid bc$ then $a \mid b$

Exercise $\PageIndex{8}\label{ex:directpf-08}$

Recall that we can use a counterexample to disprove an implication. Show that the following claims are false:

If $x$ and $y$ are integers such that $x^2>y^2$, then $x>y$.
If $n$ is a positive integer, then $n^2+n+41$ is prime.

Exercise $\PageIndex{9}\label{ex:directpf-09}$

Explain why the following arguments are invalid:

Let $n$ be an integer. If $n^2$ is odd, then $n$ is odd. Therefore, $n$ must be odd.
Let $n$ be an integer. If $n$ is even, then $n^2$ is also even. As an integer, $n^2$ could be odd. Hence, $n$ cannot be even. Therefore, $n$ must be odd.

Solution: (a) There is no information about $n^2$, so the statement "if $n^2$ is odd, then $n$ is odd" is irrelevant to the parity of $n.$
(b) $n^2$ could be odd, but we also have $n^2$ could be even. So, we do not have enough information to determine the parity of $n.$

Exercise $\PageIndex{10}\label{ex:directpf-10}$

Analyze the following reasoning:

Let $S$ be a set of real numbers. If $x$ is in $S$, then $x^2$ is in $S$. But $x$ is not in $S$, hence $x^2$ is not in $S$.
Let $S$ be a set of real numbers. If $x$ is in $S$, then $x^2$ is in $S$. Therefore, if $x^2$ is in $S$, then $x$ is in $S$.

Exercise $\PageIndex{11}$

Show that there exists an integer $n$ such that $n$, $n+2$ and $n+4$ are all primes.

Solution: Consider $n=3$. The numbers are $3, 5, 7.$

Exercise $\PageIndex{12}$

Prove: If $n$ is odd, then $n^2-1$ is divisible by $4.$

Search

Theorem \(\PageIndex{2}\) The Fundamental Theorem of Arithmetic or Prime Factorization Theorem