Direct Proofs

Section 3.1 Direct Proofs

Beginning Activity Beginning Activity 1: Definition of Divides, Divisor, Multiple
A4 US

In Section 1.2, 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 that 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.

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,$ 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 \neq 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

\frac{a}{b} .

The notation

a ∣ b

represents a relationship between the integers

a

and

b

and is simply a shorthand for “

a

divides

b .

”

🔗

A Note about Definitions.

🔗

Technically, a definition in mathematics should almost always be written using “if and only if.” It is not clear why, but the convention in mathematics is to replace the phrase “if and only if” with “if” or an equivalent. Perhaps this is a bit of laziness or the “if and only if” phrase can be a bit cumbersome. In this text, we will often use the phrase “provided that” instead.

🔗

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 Z) (n = m \cdot q) .

🔗

1.

Use the definition of divides to explain why 4 divides 32 and to explain why 8 divides $- 96 .$

🔗

2.

Give several examples of two integers where the first integer does not divide the second integer.

🔗

3.

According to the definition of “divides,” does the integer 10 divide the integer 0? That is, is 10 a divisor of 0? Explain.

🔗

4.

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 … .”

🔗

5.

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 \dots .$ ”

🔗

6.

Give three different examples of three integers where the first integer divides the second integer and the second integer divides the third integer.

🔗

As we have seen in Section 1.2, a definition is frequently used when constructing and writing mathematical proofs. Consider the following conjecture:

Let $a,$ $b,$ and $c$ be integers with $a \neq 0$ and $b \neq 0 .$ If $a$ divides $b$ and $b$ divides $c,$ then $a$ divides $c .$

🔗

7.

Explain why the examples you generated in Exercise 6 provide evidence that this conjecture is true.

🔗

In Section 1.2, we also learned how to use a know-show table to help organize our thoughts when trying to construct a proof of a statement. If necessary, review the appropriate material in Section 1.2.

🔗

8.

State precisely what we would assume if we were trying to write a proof of the preceding conjecture.

🔗

9.

Use the definition of “divides” to make some conclusions based on your assumptions in Exercise 8.

🔗

10.

State precisely what we would be trying to prove if we were trying to write a proof of the conjecture.

🔗

11.

Use the definition of divides to write an answer to the question, “How can we prove what we stated inExercise 10?”

🔗

Beginning Activity Beginning Activity 2: Calendars and Clocks
A4 US

🔗

This activity is intended to help with understanding the concept of congruence, which will be studied at the end of this section.

🔗

1.

Suppose that it is currently Tuesday.

🔗

(a)

What day will it be 3 days from now?

🔗

(b)

What day will it be 10 days from now?

🔗

(c)

What day will it be 17 days from now? What day will it be 24 days from now?

🔗

(d)

Find several other natural numbers $x$ such that it will be Friday $x$ days from now.

🔗

(e)

Create a list (increasing order) of the numbers 3, 10, 17, 24, and the numbers you generated in Task 1.d. Pick any two numbers from this list and subtract one from the other. Repeat this several times.

🔗

(f)

What do the numbers you obtained in Task 1.e have in common?

🔗

2.

Suppose that we are using a twelve-hour clock with no distinction between A.M. and P.M. Also, suppose that the current time is 5:00.

🔗

(a)

What time will it be 4 hours from now?

🔗

(b)

What time will it be 16 hours from now? What time will it be 28 hours from now?

🔗

(c)

Find several other natural numbers $x$ such that it will be 9:00 $x$ hours from now.

🔗

(d)

Create a list (in increasing order) of the numbers $4, 16, 28,$ and the numbers you generated in Task 2.c. Pick any two numbers from this list and subtract one from the other. Repeat this several times.

🔗

(e)

What do the numbers you obtained in Task 2.d have in common?

🔗

3.

This is a continuation of Exercise 1. Suppose that it is currently Tuesday.

🔗

(a)

What day was it 4 days ago?

🔗

(b)

What day was it 11 days ago? What day was it 18 days ago?

🔗

(c)

Find several other natural numbers $x$ such that it was Friday $x$ days ago.

🔗

(d)

Create a list (in increasing order) consisting of the numbers $- 18, - 11, - 4,$ the opposites of the numbers you generated in Task 3.c and the positive numbers in the list from Task 1.e. Pick any two numbers from this list and subtract one from the other. Repeat this several times.

🔗

(e)

What do the numbers you obtained in Task 3.d have in common?

🔗

Subsection 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.

🔗

A Note About Axioms in This Text.

🔗

The closure properties of the number systems discussed in Section 1.1 and the properties of the number systems in Table 1.9 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.

🔗

Subsection Constructing Mathematical Proofs

🔗

To create a proof of a theorem, we must use correct logical reasoning and mathematical statements that we already accept as true. These statements include axioms, definitions, theorems, lemmas, and corollaries.

🔗

In Section 1.2, we introduced the use of a know-show table to help us organize our work when we are attempting to prove a statement. We also introduced some guidelines for writing mathematical proofs once we have created the proof. These guidelines should be reviewed before proceeding.

🔗

Please remember that when we start the process of writing a proof, we are essentially “reporting the news.” That is, we have already discovered the proof, and now we need to report it. This reporting often does not describe the process of discovering the news (the investigative portion of the process).

🔗

Quite often, the first step is to develop a conjecture. This is often done after working within certain objects for some time. This is what we did in Beginning Activity 1 when we used examples to provide evidence that the following conjecture is true:

Conjecture: Let $a,$ $b,$ and $c$ by integers with $a \neq 0$ and $b \neq 0 .$ If $a$ divides $b$ and $b$ divides $c,$ then $a$ divides $c .$

🔗

Before we try to prove a conjecture, we should make sure we have explored some examples. This simply means to construct some specific examples where the integers

a,

b,

and

c

satisfy the hypothesis of the conjecture in order to see if they also satisfy the conclusion. We did this for this conjecture in Beginning Activity 1.

🔗

We will now start a know-show table for this conjecture.

Step	Know	Reason
$P$	$a, b, c \in Z,$ $a \neq 0,$ $b \neq 0,$ $a ∣ b$ and $b ∣ c$	Hypothesis
$P 1$
$⋮$	$⋮$	$⋮$
$Q 1$
$Q$	$a ∣ c$
Step	Show	Reason

🔗

The backward question we ask is, “How can we prove that

a

divides

c ?

” One answer is to use the definition and show that there exists an integer

q

such that

c = a \cdot q .

This could be step

Q 1

in the know-show table.

🔗

We now have to prove that a certain integer

q

exists, so we ask the question, “How do we prove that this integer exists?” When we are at such a stage in the backward process of a proof, we usually turn to what is known in order to prove that the object exists or to find or construct the object we are trying to prove exists. We often say that we try to “construct” the object or at least prove it exists from the known information. So at this point, we go to the forward part of the proof to try to prove that there exists an integer

q

such that

c = a \cdot q .

🔗

The forward question we ask is, “What can we conclude from the facts that

a ∣ b

and

b ∣ c ?

” Again, using the definition, we know that there exist integers

s

and

t

such that

b = a \cdot s

and

c = b \cdot t .

This could be step

P 1

in the know-show table.

🔗

The key now is to determine how to get from

P 1

Q 1 .

That is, can we use the conclusions that the integers

s

and

t

exist in order to prove that the integer

q

(from the backward process) exists. Using the equation

b = a \cdot s,

we can substitute

a \cdot s

for

b

in the second equation,

c = b \cdot t .

This gives

\begin{aligned} c & = b \cdot t \\ = (a \cdot s) \cdot t \\ = a (s \cdot t) . \end{aligned}

🔗

The last step used the associative property of multiplication. (See Table 1.9.) This shows that

c

is equal to

a

times some integer. (This is because

s \cdot t

is an integer by the closure property for integers.) So although we did not use the letter

q,

we have arrived at step

Q 1 .

The completed know-show table follows.

Step	Know	Reason
$P$	$a, b, c \in Z,$ $a \neq 0,$ $b \neq 0,$ $a ∣ b$ and $b ∣ c$	Hypothesis
$P 1$	$(\exists s \in Z) (b = a \cdot s)$ $(\exists t \in Z) (c = b \cdot t)$	Definition of “divides”
$P 2$	$c = (a \cdot s) \cdot t$	Substitution for $b$
$P 3$	$c = a \cdot (s \cdot t)$	Associative property of multiplication
$Q 1$	$(\exists q \in Z) (c = a \cdot q)$	Step $P 3$ and the closure properties of the integers
$Q$	$a ∣ c$	Definition of “divides”

🔗

Notice the similarities between what we did for this proof and many of the proofs about even and odd integers we constructed in Section 1.2. When we try to prove that a certain object exists, we often use what is called the construction method for a proof. The appearance of an existential quantifier in the show (or backward) portion of the proof is usually the indicator to go to what is known in order to prove the object exists.

🔗

We can now report the news by writing a formal proof.

🔗

Theorem 3.1.

Let $a,$ $b,$ and $c$ be integers with $a \neq 0$ and $b \neq 0 .$ If $a$ divides $b$ and $b$ divides $c,$ then $a$ divides $c .$

🔗

Proof.

We assume that $a,$ $b,$ and $c$ are integers with $a \neq 0$ and $b \neq 0 .$ We further assume that $a$ divides $b$ and that $b$ divides $c .$ We will prove that $a$ divides $c .$

Since $a$ divides $b$ and $b$ divides $c,$ there exist integers $s$ and $t$ such that

\begin{aligned} (1) & b & = a \cdot s, and \\ (2) & c & = b \cdot t \end{aligned}

We can now substitute the expression for $b$ from equation (1) into equation (2). This gives

c = (a \cdot s) \cdot t .

Using the associate property for multiplication, we can rearrange the right side of the last equation to obtain

c = a \cdot (s \cdot t) .

Because both $s$ and $t$ are integers, and since the integers are closed under multiplication, we know that $s \cdot t \in Z .$ Therefore, the previous equation proves that $a$ divides $c .$ Consequently, we have proven that whenever $a,$ $b,$ and $c$ are integers with $a \neq 0$ and $b \neq 0$ such that $a$ divides $b$ and $b$ divides $c,$ then $a$ divides $c .$

🔗

Subsection Writing Guidelines for Equation Numbers

🔗

We wrote the proof for Theorem 3.1 according to the guidelines introduced in Section 1.2, but a new element that appeared in this proof was the use of equation numbers. Following are some guidelines that can be used for equation numbers.

🔗

If it is necessary to refer to an equation later in a proof, that equation should be centered and displayed. It should then be given a number. The number for the equation should be written in parentheses on the same line as the equation at the right-hand margin as in shown in the following example.

Since $x$ is an odd integer, there exists an integer $n$ such that

🔗

\begin{matrix} (3) & x = 2 n + 1 . \end{matrix}

🔗

Later in the proof, there may be a line such as

Then, using the result in equation (3), we obtain ….

Notice that we did not number every equation in Theorem 3.1. We should only number those equations we will be referring to later in the proof, and we should only number equations when it is necessary. For example, instead of numbering an equation, it is often better to use a phrase such as, “the previous equation proves that …” or “we can rearrange the terms on the right side of the previous equation.” Also, note that the word “equation” is not capitalized when we are referring to an equation by number. Although it may be appropriate to use a capital “E,” the usual convention in mathematics is not to capitalize.

🔗

Progress Check 3.2. A Property of Divisors.

🔗

(a)

Give at least four different examples of integers $a,$ $b,$ and $c$ with $a \neq 0$ such that $a$ divides $b$ and $a$ divides $c .$

🔗

(b)

For each example in Task 3.2.a, calculate the sum $b + c .$ Does the integer $a$ divide the sum $b + c ?$

Solution.

For each example in Part (1), the integer $a$ divides the sum $b + c .$

🔗

(c)

Construct a know-show table for the following proposition: For all integers $a,$ $b,$ and $c$ with $a \neq 0,$ if $a$ divides $b$ and $a$ divides $c,$ then $a$ divides $(b + c) .$

Solution.

Conjecture: For all integers $a,$ $b,$ and $c$ with $a \neq 0,$ if $a$ divides $b$ and $a$ divides $c,$ then $a$ divides $b + c .$

A Know-show table for a proof of the conjecture in Part (3).

Step	Know	Reason
$P$	$a ∣ b$ and $a ∣ c$	Hypothesis
$P 1$	$(\exists s \in Z) (b = a \cdot s)$ $(\exists t \in Z) (c = a \cdot t)$	Definition of “divides”
$P 2$	$b + c = a s + a t$	Substituting for $b$ and $c$
$P 3$	$b + c = a (s + t)$	Distributive property
$Q 1$	$s + t$ is an integer	$Z$ is closed under addition
$Q$	$a \| (b + c)$	Definition of “divides”
Step	Show	Reason

🔗

Subsection Using Counterexamples

🔗

In Section 1.2 and so far in this section, our focus has been on proving statements that involve universal quantifiers. However, another important skill for mathematicians is to be able to recognize when a statement is false and then to be able to prove that it is false. For example, suppose we want to know if the following proposition is true or false.

For each integer $n,$ if 5 divides $(n^{2} - 1),$ then 5 divides $(n - 1) .$

🔗

Suppose we start trying to prove this proposition. In the backward process, we would say that in order to prove that 5 divides

(n - 1),

we can show that there exists an integer

k

such that

Q_{1} : n - 1 = 5 k or n = 5 k + 1 .

🔗

For the forward process, we could say that since 5 divides

(n^{2} - 1),

we know that there exists an integer

m

such that

P_{1} : n^{2} - 1 = 5 m or n^{2} = 5 m + 1 .

🔗

The problem is that there is no straightforward way to use

P_{1}

to prove

Q_{1} .

At this point, it would be a good idea to try some examples for

n

and try to find situations in which the hypothesis of the proposition is true. (In fact, this should have been done before we started trying to prove the proposition.) The following table summarizes the results of some of these explorations with values for

n .

$n$	$n^{2} - 1$	Does 5 divide $(n^{2} - 1)$	$n - 1$	Does 5 divide $(n - 1)$
1	0	yes	0	yes
2	3	no	1	no
3	8	no	2	no
4	15	yes	3	no

🔗

We can stop exploring examples now since the last row in the table provides an example where the hypothesis is true and the conclusion is false. Recall from Section 2.4 (see Counterexamples and Negations of Conditional Statements) that a counterexample for a statement of the form

(\forall x \in U) (P (x))

is an element

a

in the universal set for which

P (a)

is false. So we have actually proved that the negation of the proposition is true.

🔗

When using a counterexample to prove a statement is false, we do not use the term “proof” since we reserve a proof for proving a proposition is true. We could summarize our work as follows:

🔗

Conjecture.

For each integer $n,$ if 5 divides $(n^{2} - 1),$ then 5 divides $(n - 1) .$

The integer $n = 4$ is a counterexample that proves this conjecture is false. Notice that when $n = 4,$ $n^{2} - 1 = 15$ and 5 divides 15. Hence, the hypothesis of the conjecture is true in this case. In addition, $n - 1 = 3$ and 5 does not divide 3 and so the conclusion of the conjecture is false in this case. Since this is an example where the hypothesis is true and the conclusion is false, the conjecture is false.

As a general rule of thumb, anytime we are trying to decide if a proposition is true or false, it is a good idea to try some examples first. The examples that are chosen should be ones in which the hypothesis of the proposition is true. If one of these examples makes the conclusion false, then we have found a counterexample and we know the proposition is false. If all of the examples produce a true conclusion, then we have evidence that the proposition is true and can try to write a proof.

🔗

Progress Check 3.3. Using a Counterexample.

Use a counterexample to prove the following statement is false.

For all integers $a$ and $b,$ if 5 divides $a$ or 5 divides $b,$ then 5 divides $(5 a + b) .$

Solution.

A counterexample for this statement will be values of $a$ and $b$ for which 5 divides $a$ or 5 divides $b,$ and 5 does not divide $5 a + b .$ One counterexample for the statement is $a = 5$ and $b = 1 .$ For these values, the hyothesis is true since 5 divides $a$ and the conclusion is false since $5 a + b = 26$ and 5 does not divide 26.

🔗

Subsection Congruence

🔗

What mathematicians call congruence is a concept used to describe cycles in the world of the integers. For example, the day of the week is a cyclic phenomenon in that the day of the week repeats every seven days. The time of the day is a cyclic phenomenon because it repeats every 12 hours if we use a 12-hour clock or every 24 hours if we use a 24-hour clock. We explored these two cyclic phenomena in Beginning Activity 2.

🔗

Similar to what we saw in Beginning Activity 2, if it is currently Monday, then it will be Wednesday 2 days from now, 9 days from now, 16 days from now, 23 days from now, and so on. In addition, it was Wednesday 5 days ago, 12 days ago, 19 days ago, and so on. Using negative numbers for time in the past, we generate the following list of numbers:

\dots, - 19, - 12, - 5, 2, 9, 16, 23, \dots .

🔗

Notice that if we subtract any number in the list above from any other number in that list, we will obtain a multiple of 7. For example,

\begin{aligned} 16 - 2 & = 14 = 7 \cdot 2 \\ (- 5) - (9) & = - 14 = 7 \cdot (- 2) \\ 16 - (- 12) & = 28 = 7 \cdot 4 . \end{aligned}

🔗

Using the concept of congruence, we would say that all the numbers in this list are congruent modulo 7, but we first have to define when two numbers are congruent modulo some natural number

n .

🔗

Definition.

Let $n \in N .$ If $a$ and $b$ are integers, then we say that $a$ is congruent to $b$ modulo $n$ provided that $n$ divides $a - b .$ A standard notation for this is $a \equiv b (\mod n) .$ This is read as “ $a$ is congruent to $b$ modulo $n$ ” or “ $a$ is congruent to $b$ mod $n .$ ”

Notice that we can use the definition of divides to say that

n

divides

(a - b)

if and only if there exists an integer

k

such that

a - b = n k .

So we can write

🔗

\begin{aligned} a & \equiv b (\mod n) means (\exists k \in Z) (a - b = n k), or \\ a & \equiv b (\mod n) means (\exists k \in Z) (a = b + n k) . \end{aligned}

🔗

This means that in order to find integers that are congruent to

b

modulo

n,

we only need to add multiples of

n

b .

For example, to find integers that are congruent to 2 modulo 5, we add multiples of 5 to 2. This gives the following list:

\dots, - 13, - 8, - 3, 2, 7, 12, 17, \dots .

🔗

We can also write this using set notation and say that

{a \in Z | a \equiv 2 (\mod 5)} = {\dots, - 13, - 8, - 3, 2, 7, 12, 17, \dots} .

🔗

Progress Check 3.4. Congruence Modulo 8.

🔗

(a)

Determine at least eight different integers that are congruent to 5 modulo 8.

Solution.

Some integers that are congruent to 5 modulo 8 are $- 11, - 3, 5, 13,$ and 21.

🔗

(b)

Use set builder notation and the roster method to specify the set of all integers that are congruent to 5 modulo 8.

Solution.

${x \in Z | x \equiv 5 (\mod 8)} = {\dots, - 19, - 11, - 3, 5, 13, 21, 29, \dots} .$

🔗

(c)

Choose two integers that are congruent to 5 modulo 8 and add them. Then repeat this for at least five other pairs of integers that are congruent to 5 modulo 8.

Solution.

For example, $- 3 + 5 = 2,$ $- 11 + 29 = 18,$ $13 + 21 = 34 .$

🔗

(d)

Explain why all of the sums that were obtained in Task 3.4.c are congruent to 2 modulo 8.

Solution.

If we subtract 2 from any of the sums obtained in Solution 3.4.c.1, the result will be a multiple of 8. This means that the sum is congruent to 2 modulo 8. For example, $2 - 2 = 0,$ $18 - 2 = 16,$ $34 - 2 = 32 .$

🔗

We will study the concept of congruence modulo

n

in much more detail later in the text. For now, we will work with the definition of congruence modulo

n

in the context of proofs. For example, all of the examples used in Progress Check 3.4 should provide evidence that the following proposition is true.

🔗

Proposition 3.5.

For all integers $a$ and $b,$ if $a \equiv 5 (\mod 8)$ and $b \equiv 5 (\mod 8),$ then $(a + b) \equiv 2 (\mod 8) .$

🔗

Progress Check 3.6. Proving Proposition 3.5.

We will use “backward questions” and “forward questions” to help construct a proof for Proposition 3.5. So, we might ask, “How do we prove that $(a + b) \equiv 2 (\mod 8) ?$ ” One way to answer this is to use the definition of congruence and state that $(a + b) \equiv 2 (\mod 8)$ provided that 8 divides $(a + b - 2) .$

🔗

(a)

Use Definition to determine a way to prove that 8 divides $(a + b - 2) .$

Solution.

To prove that 8 divides $(a + b - 2),$ we can prove that there exists an integer $q$ such that $(a + b - 2) = 8 q .$

🔗

(b)

We now turn to what we know and ask, “What can we conclude from the assumptions that $a \equiv 5 (\mod 8)$ and $b \equiv 5 (\mod 8) ?$ ” We can again use the definition of congruence and conclude that 8 divides $(a - 5)$ and 8 divides $(b - 5) .$

Use Definition to make conclusions based on the facts that 8 divides $(a - 5)$ and 8 divides $(b - 5) .$

Solution.

Since 8 divides $(a - 5)$ and $(b - 5),$ there exist integers $k$ and $m$ such that $a - 5 = 8 k$ and $b - 5 = 8 m .$

🔗

(c)

Solve an equation from Task 3.6.b for $a$ and for $b .$

Solution.

$a = 5 + 8 k$ and $b = 5 + 8 m .$

🔗

(d)

Use the results from Task 3.6.c) to prove that 8 divides $(a + b - 2) .$

Solution.

$a + b - 2 = (5 + 8 k) + (5 + 8 m) - 2 = 8 + 8 k + 8 m = 8 (1 + k + m) .$

🔗

(e)

Write a proof for Proposition 3.5.

Solution.

🔗

Proof.

Let $a$ and $b$ be integers and assume that $a \equiv 5 (\mod 8)$ and $b \equiv 5 (\mod 8) .$ We will prove that $(a + b) \equiv 2 (\mod 8) .$ Since 8 divides $(a - 5)$ and $(b - 5),$ there exist integers $k$ and $m$ such that $a - 5 = 8 k$ and $b - 5 = 8 m .$ We then see that

\begin{aligned} a + b - 2 & = (5 + 8 k) + (5 + 8 m) - 2 \\ = 8 + 8 k + 8 m \\ = 8 (1 + k + m) \end{aligned}

By the closure properties of the integers, $(1 + k + m)$ is an integer and so the last equation proves that 8 divides $(a + b - 2)$ and hence, $(a + b) \equiv 2 (\mod 8) .$ This proves that if $a \equiv 5 (\mod 8)$ and $b \equiv 5 (\mod 8),$ then $(a + b) \equiv 2 (\mod 8)$

🔗

Subsection Additional Writing Guidelines

🔗

We will now be writing many proofs, and it is important to make sure we write according to accepted guidelines so that our proofs may be understood by others. Some writing guidelines were introduced in Chapter 1. The first four writing guidelines given below can be considered general guidelines, and the last three can be considered as technical guidelines specific to writing in mathematics.

Know Your Audience.
Every writer should have a clear idea of the intended audience for a piece of writing. In that way, the writer can give the right amount of information at the proper level of sophistication to communicate effectively. This is especially true for mathematical writing. For example, if a mathematician is writing a solution to a textbook problem for a solutions manual for instructors, the writing would be brief with many details omitted. However, if the writing was for a students' solution manual, more details would be included.
Use complete sentences and proper paragraph structure.
Good grammar is an important part of any writing. Therefore, conform to the accepted rules of grammar. Pay careful attention to the structure of sentences. Write proofs using complete sentences but avoid run-on sentences. Also, do not forget punctuation, and always use a spell checker when using a word processor.
Keep it simple.
It is often difficult to understand a mathematical argument no matter how well it is written. Do not let your writing help make it more difficult for the reader. Use simple, declarative sentences and short paragraphs, each with a simple point.
Write a first draft of your proof and then revise it.
Remember that a proof is written so that readers are able to read and understand the reasoning in the proof. Be clear and concise. Include details but do not ramble. Do not be satisfied with the first draft of a proof. Read it over and refine it. Just like any worthwhile activity, learning to write mathematics well takes practice and hard work. This can be frustrating. Everyone can be sure that there will be some proofs that are difficult to construct, but remember that proofs are a very important part of mathematics. So work hard and have fun.
Do not use $*$ for multiplication or ^ for exponents.
Leave this type of notation for writing computer code. The use of this notation makes it difficult for humans to read. In addition, avoid using $/$ for division when using a complex fraction.

For example, it is very difficult to read $(x^{3} - 3 x^{2} + 1 / 2) / (2 x / 3 - 7);$ the fraction

$\frac{x^{3} - 3 x^{2} + \frac{1}{2}}{\frac{2 x}{3} - 7}$

is much easier to read.
Do not use a mathematical symbol at the beginning of a sentence..
For example, we should not write, “Let $n$ be an integer. $n$ is an odd integer provided that … .” Many people find this hard to read and often have to re-read it to understand it. It would be better to write, “An integer $n$ is an odd integer provided that … .”
Use English and minimize the use of cumbersome notation.
Do not use the special symbols for quantifiers $\forall$ (for all), $\exists$ (there exists), $∍$ (such that), or $∴$ (therefore) in formal mathematical writing. It is often easier to write, and usually easier to read, if the English words are used instead of the symbols. For example, why make the reader interpret

$(\forall x \in R) (\exists y \in R) (x + y = 0)$

when it is possbile to write
For each real number $x,$ there exists a real number $y$ such that $x + y = 0,$
or, more succinctly (if appropriate),
Every real number has an additive inverse.

🔗

Exercises Exercises

🔗

1.

Prove each of the following statements:

🔗

(a)

For all integers $a,$ $b,$ and $c$ with $a \neq 0,$ if $a ∣ b$ and $a ∣ c,$ then $a ∣ (b - c) .$

Answer.

Since $a ∣ b$ and $a ∣ c,$ there exist integers $m$ and $n$ such that $b = a m$ and $c = a n .$ Hence,

\begin{aligned} b - c & = a m - a n \\ = a (m - n) \end{aligned}

Since $m - n$ is an integer (by the closure properties of the integers), the last equation implies that $a$ divides $b - c .$

🔗

(b)

For each $n \in Z,$ if $n$ is an odd integer, then $n^{3}$ is an odd integer.

Hint.

What do you need to do in order to prove that $n^{3}$ is odd? Notice that if $n$ is an odd integer, then there exists an integer $k$ such that $n = 2 k + 1 .$ Remember that to prove that $n^{3}$ is an odd integer, you need to prove that there exists an integer $q$ such that $n^{3} = 2 q + 1 .$ This can also be approached as follows: If $n$ is odd, then by Theorem 1.10, $n^{2}$ is odd. Now use the fact that $n^{3} = n \cdot n^{2} .$

🔗

(c)

For each integer $a,$ if 4 divides $(a - 1),$ then 4 divides $(a^{2} - 1) .$

Hint.

If 4 divides $(a - 1),$ then there exists an integer $k$ such that $a - 1 = 4 k$ and so $a = 4 k + 1 .$ Use algebra to rewrite $(a^{2} - 1) = (4 k + 1)^{2} - 1 .$

🔗

2.

For each of the following, use a counterexample to prove the statement is false.

🔗

(a)

For each odd natural number $n,$ if $n > 3,$ then 3 divides $(n^{2} - 1) .$

Answer.

The natural number $n = 9$ is a counterexample since $n$ is odd, $n > 3,$ $n^{2} - 1 = 80$ and 3 does not divide 80.

🔗

(b)

For each natural number $n,$ $(3 \cdot 2^{n} + 2 \cdot 3^{n} + 1)$ is a prime number.

🔗

(c)

For all real numbers $x$ and $y,$ $\sqrt{x^{2} + y^{2}} > 2 x y .$

🔗

(d)

For each integer $a,$ if 4 divides $(a^{2} - 1),$ then 4 divides $(a - 1) .$

Answer.

The integer $a = 3$ is a counterexample since $a^{2} - 1 = 8$ and $a - 1 = 2 .$ Since 4 divides 8 and 4 does not divide 2, this is an example where the hypothesis of the conditional statement is true and the conclusion is false.

🔗

3.

Determine if each of the following statements is true or false. If a statement is true, then write a formal proof of that statement, and if it is false, then provide a counterexample that shows it is false.

🔗

(a)

For all integers $a,$ $b,$ and $c$ with $a \neq 0,$ if $a ∣ b,$ then $a ∣ (b c) .$

🔗

(b)

For all integers $a$ and $b$ with $a \neq 0,$ if $6 ∣ (a b),$ then $6 ∣ a$ or $6 ∣ b .$

Answer.

This statement is false. One counterexample is $a = 3$ and $b = 2$ since this is an example where the hypothesis is true and the conclusion is false.

🔗

(c)

For all integers $a,$ $b,$ and $c$ with $a \neq 0,$ if $a$ divides $(b - 1)$ and $a$ divides $(c - 1),$ then $a$ divides $(b c - 1) .$

🔗

(d)

For each integer $n,$ if 7 divides $(n^{2} - 4),$ then 7 divides $(n - 2) .$

Answer.

This statement is false. One counterexample is $n = 5 .$ Since $n^{2} - 4 = 21$ and $n - 2 = 3,$ this is an example where the hypothesis of the conditional statement is true and the conclusion is false.

🔗

(e)

For every integer $n,$ $4 n^{2} + 7 n + 6$ is an odd integer.

Hint.

Make sure you first try some examples. How do you prove that an integer is an odd integer?

🔗

(f)

For every odd integer $n,$ $4 n^{2} + 7 n + 6$ is an odd integer.

Hint.

The following algebra may be useful.

4 {(2 m + 1)}^{2} + 7 (2 m + 1) + 6 = 16 m^{2} + 30 m + 17 .

🔗

(g)

For all integers $a,$ $b,$ and $d$ with $d \neq 0,$ if $d$ divides both $a - b$ and $a + b,$ then $d$ divides $a .$

Answer.

This statement is false. One counterexample is $a = 7,$ $b = 1,$ and $d = 2 .$ Why is this a counterexample?

🔗

(h)

For all integers $a,$ $b,$ and $c$ with $a \neq 0,$ if $a ∣ (b c),$ then $a ∣ b$ or $a ∣ c .$

🔗

4.

Complete the following.

🔗

(a)

If $x$ and $y$ are integers and $x y = 1,$ explain why $x = 1$ or $x = - 1 .$

Answer.

If $x y = 1,$ then $x$ and $y$ are both divisors of $1,$ and the only divisors of $1$ are $- 1$ and $1 .$

🔗

(b)

Is the following proposition true or false?

For all nonzero integers $a$ and $b,$ if $a ∣ b$ and $b ∣ a,$ then $a = \pm b .$

Hint.

Task 4.a is useful in proving this.

🔗

5.

Prove the following proposition:

Let $a$ be an integer. If there exists an integer $n$ such that $a ∣ (4 n + 3)$ and $a ∣ (2 n + 1),$ then $a = 1$ or $a = - 1 .$

Hint 1.

Use the fact that the only divisors of 1 are 1 and $- 1 .$

Hint 2.

$(4 n + 3) - 2 (2 n + 1) = 1 .$

🔗

6.

🔗

(a)

For each integer $a,$ if there exists an integer $n$ such that $a$ divides $(8 n + 7)$ and $a$ divides $(4 n + 1),$ then $a$ divides 5.

🔗

(b)

For each integer $a,$ if there exists an integer $n$ such that $a$ divides $(9 n + 5)$ and $a$ divides $(6 n + 1),$ then $a$ divides 7.

🔗

(c)

For each integer $n,$ if $n$ is odd, then 8 divides $(n^{4} + 4 n^{2} + 11) .$

🔗

(d)

For each integer $n,$ if $n$ is odd, then 8 divides $(n^{4} + n^{2} + 2 n) .$

🔗

7.

Let $a$ be an integer and let $n \in N .$

🔗

(a)

Prove that if $a \equiv 0 (\mod n),$ then $n ∣ a .$

🔗

(b)

Prove that if $n ∣ a,$ then $a \equiv 0 (\mod n) .$

🔗

8.

Let $a$ and $b$ be integers. Prove that if $a \equiv 2 (\mod 3)$ and $b \equiv 2 (\mod 3),$ then

🔗

(a)

$a + b \equiv 1 (\mod 3) .$

Answer.

Assuming $a$ and $b$ are both congruent to 2 modulo 3, there exist integers $m$ and $n$ such that $a = 3 m + 2$ and $b = 3 n + 2 .$ Show that

a + b - 1 = 3 (m + n + 1) .

We can then conclude that 3 divides $(a + b) - 1$ and this proves that $(a + b) \equiv 1 (\mod 3) .$

🔗

(b)

$a \cdot b \equiv 1 (\mod 3) .$

Answer.

Assuming $a$ and $b$ are both congruent to 2 modulo 3, there exist integers $m$ and $n$ such that $a = 3 m + 2$ and $b = 3 n + 2 .$ Show that

a \cdot b - 1 = 3 (3 m n + 2 m + 2 n + 1) .

We can then conclude that 3 divides $a \cdot b - 1$ and this proves that $a \cdot b \equiv 1 (\mod 3) .$

🔗

9.

Let $a$ and $b$ be integers. Prove that if $a \equiv 7 (\mod 8)$ and $b \equiv 3 (\mod 8),$ then:

🔗

(a)

$a + b \equiv 2 (\mod 8) .$

🔗

(b)

$a \cdot b \equiv 5 (\mod 8) .$

🔗

10.

Determine if each of the following propositions is true or false. Justify each conclusion.

🔗

(a)

For all integers $a$ and $b,$ if $a b \equiv 0 (\mod 6),$ then $a \equiv 0 (\mod 6)$ or $b \equiv 0 (\mod 6) .$

🔗

(b)

For each integer $a,$ if $a \equiv 2 (\mod 8),$ then $a^{2} \equiv 4 (\mod 8) .$

🔗

(c)

For each integer $a,$ if $a^{2} \equiv 4 (\mod 8),$ then $a \equiv 2 (\mod 8) .$

🔗

11.

Let $n$ be a natural number. Prove each of the following:

🔗

(a)

For every integer $a,$ $a \equiv a (\mod n) .$

This is called the reflexive property of congruence modulo $n .$

Answer.

Let $n \in N .$ If $a$ is an integer, then $a - a = 0$ and $n$ divides 0. Therefore, $a \equiv a (\mod n) .$

🔗

(b)

For all integers $a$ and $b,$ if $a \equiv b (\mod n),$ then $b \equiv a (\mod n) .$

This is called the symmetric property of congruence modulo $n .$

Answer.

Let $n \in N,$ let $a, b \in Z$ and assume that $a \equiv b (\mod n) .$ We will prove that $b \equiv a (\mod n) .$ Since $a \equiv b (\mod n),$ $n$ divides $(a - b)$ and so there exists an integer $k$ such that $a - b = n k .$ From this, we can show that $b - a = n (- k)$ and so $n$ divides $(b - a) .$ Hence, if $a \equiv b (\mod n),$ then $b \equiv a (\mod n) .$

🔗

(c)

For all integers $a,$ $b,$ and $c,$ if $a \equiv b (\mod n)$ and $b \equiv c (\mod n),$ then $a \equiv c (\mod n) .$

This is called the transitive property of congruence modulo $n .$

🔗

12.

Let $n$ be a natural number and let $a,$ $b,$ $c,$ and $d$ be integers. Prove each of the following.

🔗

(a)

If $a \equiv b (\mod n)$ and $c \equiv d (\mod n),$ then $(a + c) \equiv (b + d) (\mod n) .$

🔗

(b)

If $a \equiv b (\mod n)$ and $c \equiv d (\mod n),$ then $a c \equiv b d (\mod n) .$

Answer.

The assumptions mean that $n ∣ (a - b)$ and that $n ∣ (c - d) .$ Use these divisibility relations to obtain an expression that is equal to $a$ and to obtain an expression that is equal to $c .$ Then use algebra to rewrite the resulting expressions for $a + c$ and $a \cdot c .$

🔗

13.

Complete the following.

🔗

(a)

Let $a,$ $b,$ and $c$ be real numbers with $a \neq 0 .$ Explain how to use a part of the quadratic formula (called the discriminant) to determine if the quadratic equation $a x^{2} + b x + c = 0$ has two real number solutions, one real number solution, or no real number solutions. (See Exercise 11 from Section 1.2 for a statement of the quadratic formula.)

🔗

(b)

Prove that if $a,$ $b,$ and $c$ are real numbers for which $a > 0$ and $c < 0,$ then one solution of the quadratic equation $a x^{2} + b x + c = 0$ is a positive real number.

🔗

(c)

Prove that if $a,$ $b,$ and $c$ are real numbers, if $a \neq 0,$ $b > 0$ and $\frac{b}{2} < \sqrt{a c},$ then the quadratic equation $a x^{2} + b x + c = 0$ has no real number solution.

🔗

14.

Let $h$ and $k$ be real numbers and let $r$ be a positive number. The equation for a circle whose center is at the point $(h, k)$ and whose radius is $r$ is

{(x - h)}^{2} + {(y - k)}^{2} = r^{2} .

We also know that if $a$ and $b$ are real numbers, then

The point $(a, b)$ is inside the circle if ${(a - h)}^{2} + {(b - k)}^{2} < r^{2} .$
The point $(a, b)$ is on the circle if ${(a - h)}^{2} + {(b - k)}^{2} = r^{2} .$
The point $(a, b)$ is outside the circle if ${(a - h)}^{2} + {(b - k)}^{2} > r^{2} .$

Prove that all points on or inside the circle whose equation is ${(x - 1)}^{2} + {(y - 2)}^{2} = 4$ are inside the circle whose equation is $x^{2} + y^{2} = 26 .$

🔗

15.

Let $r$ be a positive real number. The equation for a circle of radius $r$ whose center is the origin is $x^{2} + y^{2} = r^{2} .$

🔗

(a)

Use implicit differentiation to determine $\frac{d y}{d x} .$

🔗

(b)

Let $(a, b)$ be a point on the circle with $a \neq 0$ and $b \neq 0 .$ Determine the slope of the line tangent to the circle at the point $(a, b) .$

🔗

(c)

Prove that the radius of the circle to the point $(a, b)$ is perpendicular to the line tangent to the circle at the point $(a, b) .$

Hint.

Two lines (neither of which is horizontal) are perpendicular if and only if the products of their slopes is equal to

- 1 .

🔗

16.

Determine if each of the following statements is true or false. Provide a counterexample for statements that are false and provide a complete proof for those that are true.

🔗

(a)

For all real numbers $x$ and $y,$ $\sqrt{x y} \leq \frac{x + y}{2} .$

🔗

(b)

For all real numbers $x$ and $y,$ $x y \leq {(\frac{x + y}{2})}^{2} .$

🔗

(c)

For all nonnegative real numbers $x$ and $y,$ $\sqrt{x y} \leq \frac{x + y}{2} .$

🔗

17.

Use one of the true inequalities in Exercise 16 to prove the following proposition.

For each real number $a,$ the value of $x$ that gives the maximum value of $y = x (a - x)$ is $x = \frac{a}{2} .$

🔗

18.

On the left side, an equilateral triangle has sides x and altitude h. On the righthand side, a right triangle with vertices ABC. Three equilateral triangles are constructed from the sides of the right triangle, with vertices ABD, BCF, EAC. — Figure 3.7. Diagrams for Exercise 18

🔗

(a)

State the Pythagorean Theorem for right triangles.

The diagrams in Figure 3.7 will be used for the problems in this exercise.

🔗

(b)

In the diagram on the left of Figure 3.7, $x$ is the length of a side of the equilateral triangle and $h$ is the length of an altitude of the equilateral triangle. The labeling in the diagram shows the fact that the altitude intersects the base of the equilateral triangle at the midpoint of the base. Use the Pythagorean Theorem to prove that the area of this equilateral triangle is $\frac{\sqrt{3}}{4} x^{2} .$

🔗

(c)

In the diagram on the right of Figure 3.7, $△ A B C$ is a right triangle. In addition, there has been an equilateral triangle constructed on each side of this right triangle. Prove that the area of the equilateral triangle on the hypotenuse is equal to the sum of the areas of the equilateral triangles constructed on the other two sides of the right triangle.

🔗

19. Evaluation of Proofs.

This type of exercise will appear frequently in the book. In each case, there is a proposed proof of a proposition. However, the proposition may be true or may be false.

If a proposition is false, the proposed proof is, of course, incorrect. In this situation, you are to find the error in the proof and then provide a counterexample showing that the proposition is false.
If a proposition is true, the proposed proof may still be incorrect. In this case, you are to determine why the proof is incorrect and then write a correct proof using the writing guidelines that have been presented in this book.
If a proposition is true and the proof is correct, you are to decide if the proof is well written or not. If it is well written, then you simply must indicate that this is an excellent proof and needs no revision. On the other hand, if the proof is not well written, then you must then revise the proof by writing it according to the guidelines presented in this text.

🔗

(a)

Proposition: If $m$ is an even integer, then $(5 m + 4)$ is an even integer.
Proof: We see that $5 m + 4 = 10 n + 4 = 2 (5 n + 2) .$ Therefore, $(5 m + 4)$ is an even integer.

🔗

(b)

Proposition

For all real numbers $x$ and $y,$ if $x \neq y,$ $x > 0,$ and $y > 0,$ then $\frac{x}{y} + \frac{y}{x} > 2 .$

Proof

Since $x$ and $y$ are positive real numbers, $x y$ is positive and we can multiply both sides of the inequality by $x y$ to obtain

\begin{aligned} (\frac{x}{y} + \frac{y}{x}) \cdot x y & > 2 \cdot x y \\ x^{2} + y^{2} & > 2 x y . \end{aligned}

By combining all terms on the left side of the inequality, we see that $x^{2} - 2 x y + y^{2} > 0$ and then by factoring the left side, we obtain ${(x - y)}^{2} > 0 .$ Since $x \neq y,$ $(x - y) \neq 0$ and so ${(x - y)}^{2} > 0 .$ This proves that if $x \neq y,$ $x > 0,$ and $y > 0,$ then $\frac{x}{y} + \frac{y}{x} > 2 .$

🔗

(c)

Proposition

For all integers $a,$ $b,$ and $c,$ if $a ∣ (b c),$ then $a ∣ b$ or $a ∣ c .$

Proof

We assume that $a,$ $b,$ and $c$ are integers and that $a$ divides $b c .$ So, there exists an integer $k$ such that $b c = k a .$

We now factor $k$ as $k = m n,$ where $m$ and $n$ are integers. We then see that

b c = m n a .

This means that $b = m a$ or $c = n a$ and hence, $a ∣ b$ or $a ∣ c .$

🔗

(d)

Proposition: For all positive integers $a,$ $b,$ and $c,$ ${(a^{b})}^{c} = a^{(b^{c})} .$
Proof: This proposition is false as is shown by the following counterexample: If we let $a = 2,$ $b = 3,$ and $c = 2,$ then

$\begin{aligned} {(a^{b})}^{c} & = a^{(b^{c})} \\ {(2^{3})}^{2} & = 2^{(3^{2})} \\ 8^{2} & = 2^{9} \\ 64 & \neq 512 . \end{aligned}$

🔗

Activity 11. Congruence Modulo 6.

🔗

(a)

Find several integers that are congruent to 5 modulo 6 and then square each of these integers.

🔗

(b)

For each integer $m$ from Task 11.a, determine an integer $k$ so that $0 \leq k < 6$ and $m^{2} \equiv k (\mod 6) .$ What do you observe?

🔗

(c)

Based on the work in Task 11.b, complete the following conjecture:

For each integer $m,$ if $m \equiv 5 (\mod 6),$ then … .

🔗

(d)

Complete a know-show table for the conjecture in Task 11.c or write a proof of the conjecture.

🔗

Activity 12. Pythagorean Triples.

Three natural numbers $a,$ $b,$ and $c$ with $a < b < c$ are called a Pythagorean triple provided that $a^{2} + b^{2} = c^{2} .$ See Activity 2 in Section 1.2. Three natural numbers are called consecutive natural numbers if they can be written in the form $m,$ $m + 1,$ and $m + 2,$ where $m$ is a natural number.

🔗

(a)

Determine all Pythagorean triples consisting of three consecutive natural numbers. (State a theorem and prove it.)

🔗

(b)

Determine all Pythagorean triples that can be written in the form $m,$ $m + 7,$ and $m + 8,$ where $m$ is a natural number. State a theorem and prove it.

Section 3.1 Direct Proofs

Beginning Activity Beginning Activity 1: Definition of Divides, Divisor, Multiple A4US

Definition.

A Note about Notation.

A Note about Definitions.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

Beginning Activity Beginning Activity 2: Calendars and Clocks A4US

1.

(a)

(b)

(c)

(d)

(e)

(f)

2.

(a)

(b)

(c)

(d)

(e)

3.

(a)

(b)

(c)

(d)

(e)

Subsection Some Mathematical Terminology

A Note About Axioms in This Text.

Subsection Constructing Mathematical Proofs

Theorem 3.1.

Proof.

Subsection Writing Guidelines for Equation Numbers

Progress Check 3.2. A Property of Divisors.

(a)

(b)

(c)

Subsection Using Counterexamples

Conjecture.

Progress Check 3.3. Using a Counterexample.

Subsection Congruence

Definition.

Progress Check 3.4. Congruence Modulo 8.

(a)

(b)

(c)

(d)

Proposition 3.5.

Progress Check 3.6. Proving Proposition 3.5.

(a)

(b)

(c)

(d)

(e)

Proof.

Subsection Additional Writing Guidelines

Exercises Exercises

1.

(a)

(b)

(c)

2.

(a)

(b)

(c)

(d)

3.

(a)

(b)

(c)

(d)

Beginning Activity Beginning Activity 1: Definition of Divides, Divisor, Multiple
A4 US

Beginning Activity Beginning Activity 2: Calendars and Clocks
A4 US