\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section5.3Conditional Statements
Most statements in mathematics and computer science involve conditionals: if one thing happens, then another thing happens. Consider, for example, a database that tracks patients who have scheduled follow-up visits (or not). We might want to send a reminder to patients who have not yet scheduled their follow-up visits. That is, if the patient has not scheduled their follow-up visit, then we want to send them a reminder.
For statements \(P\) and \(Q\text{,}\) the statement “if \(P\text{,}\) then \(Q\)”, denoted \(P \to Q\text{,}\) is a conditional statement. We also say \(P\) implies \(Q\text{.}\) The statement \(P \to Q\) promises that if \(P\) is true, then \(Q\) must also be true. For example, consider the following statement: For any integer \(k\text{,}\) if \(k=3\text{,}\) then \(k^2=9\text{.}\) This statement is true because when \(k=3\) we have \(k^2 = 3^2 = 9\text{.}\)
In the statement \(P \to Q\text{,}\) the statement \(P\) is the hypothesis and \(Q\) is the conclusion. For example, consider the following statement: If a graph is a tree, then it has a leaf. The hypothesis is that a graph is a tree. The conclusion is that it has a leaf.
For \(P \to Q\) to be true, it must be the case that if \(P\) is true, then \(Q\) is 100% guaranteed to also be true. It might be the case that \(P\) causes \(Q\text{,}\) for example, if \(P\) is the statement “Tova dropped her glove in a puddle” a nd \(Q\) is the statement “Tova’s glove got wet”, then \(P \to Q\) is the statement “If Tova dropped her glove in a puddle, then Tova’s glove got wet”, which is true. In this example, \(P\) caused \(Q\text{.}\)
Alternatively, it might be the case that \(Q\) had to happen in order for \(P\) to happen. For example, if \(P\) is the statement “Derek got an A in Algorithms class” and \(Q\) is the statement “Derek took the Algorithms class” then \(P \to Q\) is the statement “if Derek got an A in Algorithms class, then Derek took the Algorithms class” which is true. In this example, \(Q\) would have to happen before \(P\text{.}\)
Example5.3.2Understanding when a conditional is true.
Consider the following conditional statement \(S\) which is “If you show up to class every day and do all of the homework on time, then you will get an A in this class.”
Is \(S\) true or false if you show up to class every day and do all of the homework on time and you get an A in this class?
Solution.
It is true. When both the hypothesis and the conclusion are true, we have kept the promise.
In many parts of this activity, you are asked to construct a truth table. You may start a new truth table for each part, but consider adding columns to your existing truth table instead.
Use your truth table to show that \((P \land Q) \to P\) is a tautology by adding a column for \(P \land Q\) and another column for \((P \land Q) \to P\text{.}\)
Example5.3.7Truth tables for statements involving conditionals.
Construct a truth table for \(Q \to P\text{.}\)Solution.
Table 5.3.8 shows the truth table. Note that the hypothesis is now \(Q\) and the conclusion is now \(P\text{.}\) The only time \(Q \to P\) is false is when the hypothesis \(Q\) is true but the conclusion \(P\) is false.
Construct a truth table for \(\neg P \lor Q\text{.}\) What do you notice?
Solution.
Table 5.3.10 shows the truth table. Because the last column is the same as the truth table for \(P \to Q\) in Table 5.3.4, we can conclude that they are logically equivalent. That is, \(\neg P \lor Q \equiv P \to Q\text{.}\)
A common command in computer programming is a statement of the form “If \(P\text{,}\) then \(Q\text{,}\) else \(R\text{.}\)” This statement tells the computer that if \(P\) is true, then do what \(Q\) says and if \(P\) is false, then do what \(R\) says.
Write the statement if \(P\text{,}\) then \(Q\text{,}\) else \(R\) in logical notation.
Solution.
The statement says if \(P\text{,}\) then \(Q\) and also if \(\neg P\text{,}\) then \(R\) so we have
\begin{equation*}
(P \to Q) \land (\neg P \to R)
\end{equation*}
Consider the following statement: for any integer \(n\text{,}\) if \(n\) is even, then the answer is \(\frac{n}{2}\text{,}\) else the answer is \(3n+1\text{.}\) What is the answer when \(n=30\text{?}\) What is the answer when \(n = 7\text{?}\)Solution.
When \(n=30\) the statement \(n\) is even is true and so the answer is \(\frac{n}{2}=\frac{30}{2} = 15\text{.}\) On the other hand, when \(n=7\) the statement \(n\) is even is false and so the answer is \(3n+1 = 3(7)+1 = 22\text{.}\)
Subsection5.3.BProof Format: Direct Proof of a Conditional
Since \(P \to Q\) promises that if \(P\) is true, then \(Q\) is true, our proof format begins by assuming that \(P\) is true and concludes once we have shown that \(Q\) is true. The proof does not mention the case where \(P\) is false since \(P \to Q\) is automatically true if that happens, as stated in Remark 5.3.5.
Activity5.3.BDirect proof of a conditional statement.
Copy the following proof of a direct proof of a conditional statement. Note that we are using Theorem 5.2.18 because the statement is universally quantified as well as Theorem 5.3.13. Prove for any integer \(m\text{,}\) if \(m\) is odd then \(3m\) is odd.
Proof.
Let \(m\) be an integer. Assume that \(m\) is odd. By the definition of odd Definition 4.1.4 we can write \(m=2k+1\) for some integer \(k\text{.}\) Then
We have just seen how to prove that a conditional statement is true. How do we construct a counterexample involving a conditional statement to prove that it is false?
For each statement from Activity 5.3.C (a)-(c), find a counterexample to show the statement is false.
If a graph has chromatic number four, then it must be the complete graph \(K_4\text{.}\)Solution.
One possible counterexample is the wheel \(W_5\text{,}\) drawn in Figure 3.2.26. (By the way, we could not use \(W_3\) as a counterexample because \(W_3 \cong K_4\text{.}\)) Notice that our counterexample has the hypothesis true and the conclusion false.
Given real numbers \(x\) and \(y\text{,}\) if \(x + y = 2\text{,}\) then \(x \le 1\) and \(y \le 1\text{.}\)Solution.
One possible counterexample is \(x = 0.8\) and \(y=1.2\text{.}\) While it is true that \(x=0.8 \le 1\text{,}\) because \(y = 1.2 > 1\) it follows that the conclusion that \(x \le 1\) and \(y \le 1\) is false. Notice that our counterexample has the hypothesis true and the conclusion false. To insure that the conclusion was false, we used DeMorgan’s Laws Theorem 5.1.23\(\neg(P \land Q) \equiv \neg P \lor \neg Q\text{.}\)
For any integers \(a\) and \(b\text{,}\) if \(6 \mid ab\text{,}\) then \(6 \mid a\) or \(6 \mid b\text{.}\)Solution.
One possible counterexample would be \(a = 3\) and \(b = 4\) because then \(6 \mid 12 = ab\) but \(6 \nmid 3\) and \(6 \nmid 4\text{.}\) Notice that our counterexample has the hypothesis true and the conclusion false. To insure that the conclusion was false, we used DeMorgan’s Laws Theorem 5.1.23\(\neg(P \lor Q) \equiv \neg P \land \neg Q\text{.}\)
As we saw in Activity 5.3.C and Example 5.3.16, a counterexample to \(P \to Q\) must have \(P\) true and \(Q\) false. After all, that is the only way to break the promise.
Write the negation of each statement in a sentence. Hint: The negation should be true for your counterexample.
If a graph has chromatic number four, then it must be the complete graph \(K_4\text{.}\)Solution.
Note that this statement does not state a specific quantifier, so following Remark 5.2.11, we interpret this statement as universally quantified. Using Theorem 5.2.24 and Theorem 5.3.17 we get the following negation: There exists a graph that has chromatic number four but is not the complete graph \(K_4\text{.}\) Our counterexample from Example 5.3.16 found a graph, namely \(W_5\text{,}\) that has chromatic number four but is not the complete graph \(K_4\text{.}\)
Given real numbers \(x\) and \(y\text{,}\) if \(x + y = 2\text{,}\) then \(x \le 1\) and \(y \le 1\text{.}\)Solution.
We use Theorem 5.2.24 and Theorem 5.3.17 to find the following awkwardly-stated draft of the negation: There are real numbers \(x\) and \(y\) such that \(x+y=2\) but it is not the case that \(x \le 1\) and \(y \le 1\text{.}\) We can eliminate the awkward “it is not the case” by using DeMorgan’s law Theorem 5.1.23. Our negation is the following statement: There are real numbers \(x\) and \(y\) such that \(x+y=2\) but either \(x > 1\) or \(y > 1\text{.}\) Our counterexample from Example 5.3.16 found real numbers \(x = 0.8\) and \(y = 1.2\) where \(x+y=2\) but \(y > 1\text{.}\)
For any integers \(a\) and \(b\text{,}\) if \(6 \mid ab\text{,}\) then \(6 \mid a\) or \(6 \mid b\text{.}\)Solution.
We use Theorem 5.2.24 and Theorem 5.3.17 to find the following awkwardly-stated draft of the negation: There are integers \(a\) and \(b\) such that \(6 \mid ab\) but it is not the case that \(6 \mid a\) or \(6 \mid b\text{.}\) We can eliminate the awkward “it is not the case” by using DeMorgan’s law Theorem 5.1.23. Our negation is the following statement: There are integers \(a\) and \(b\) such that \(6 \mid ab\) but \(6 \nmid a\) and \(6 \nmid b\text{.}\) Our counterexample from Example 5.3.16 found integers \(a = 3\) and \(b = 4\) where \(6 \mid 12\) but \(6 \nmid 3\) and \(6 \nmid 4\text{.}\)
The implication equivalence Theorem 5.3.11 gives us a new way to prove an “or” statement, which we saw earlier using cases in Theorem 5.1.12. That is, to prove \(R \lor Q\) we can prove \(\neg R \to Q\text{.}\)
Activity5.3.DDirect proof of an “or” statement using an equivalent conditional.
Copy the following proof of proof of an “or” statement using the implication equivalence. Note that we are using Theorem 5.2.18 because the statement is universally quantified as well as Theorem 5.3.19. Prove that for any positive real numbers \(a\) and \(b\) such that \(ab=100\text{,}\) either \(a \le 10\) or \(b \lt 10\text{.}\)
Proof.
Let \(a\) and \(b\) be positive real numbers such that \(ab = 100\text{.}\) Assume \(a > 10\text{.}\) Multiplying each side of this equation by the positive number \(b\) we get \(100=ab > 10b\text{.}\) Dividing each side of this equation by 10 we get \(b \lt 10\text{.}\) Thus either \(a \le 10\) or \(b \lt 10\text{.}\)
Edit the proof in (a) to prove that for any positive real numbers \(a\) and \(b\) such that \(ab=5\text{,}\) either \(a \le \sqrt{5}\) or \(b \lt \sqrt{5}\text{.}\)
A common concern about proving an “or” statement using the implication equivalence is that we have proved that if \(P\) is false, then \(Q\) is true, but it feels like we are missing a proof that if \(Q\) is false, then \(P\) is true. It is not missing. Let’s look at how to better understand Theorem 5.3.19 by comparing it to proof by cases.
Hint: The truth table should have four columns: \(P\text{,}\)\(Q\text{,}\)\(P \lor Q\text{,}\)\(P \to (P \lor Q)\text{.}\) The truth table should also have four rows, as in Example 5.3.3. To show that the statement is a tautology, the last column of your truth table should be all \(\str{T}\) s.
Construct a truth table to show that \((P \land (P \to Q)) \to Q\) is a tautology. This logical equivalence justifies modus ponens, a key logical inference we discuss in Section 5.5.
Hint: Your truth table should have eight columns: \(P\text{,}\)\(Q\text{,}\)\(R\text{,}\)\(P \to R\text{,}\)\(Q \to R\text{,}\)\((P \to R) \land (Q \to R)\text{,}\)\(P \lor Q\text{,}\) and \((P \lor Q) \to R\text{.}\) Your truth table should also have eight rows, as in Example 5.1.9. The sixth and eighth columns should be the same.
Use the implication equivalence Theorem 5.3.11 to rewrite the following statement as a conditional: Either you take a break from playing that video game or I will take away your controller for a week.
Is \(P \lor (Q \to R)\) logically equivalent to \((P \lor Q) \to R\text{?}\) Use a truth table to justify your answer. Include appropriate intermediate columns.
Use Theorem 5.2.18, Theorem 5.3.13, and Definition 4.1.4 to prove that for any integer \(n\text{,}\) if \(n\) is odd, then \(n^2\) is odd. Hint: Write \(n=2k+1\text{.}\) Next, simplify \(n^2\) and write it as \(2(~)+1\text{.}\)
Use Theorem 5.2.18, Theorem 5.3.13, and Definition 4.1.8 to prove that for any integer \(n\text{,}\) if \(6 \mid n\text{,}\) then \(3 \mid n\text{.}\) Hint: Write \(n = 6k\) for some integer \(k\text{.}\) How can you write \(n = 3(~)\text{?}\)
Use Theorem 5.2.18, Theorem 5.3.13, and Definition 4.1.8 to prove if \(a \mid b\text{,}\) then \(a \mid b^2\) for any integers \(a\) and \(b\text{.}\) Hint: Write \(b = ak\) for some integer \(k\text{.}\) Next, simplify \(b^2\) and write it as \(a(~)\text{.}\)
Use Theorem 5.2.18, Theorem 5.1.11, and Theorem 5.3.13 to prove for any integers \(a\) and \(b\) if \(a\) is even and \(b\) is odd, then \(a+b\) is odd and \(ab\) is even. Hint: Write \(a = 2k_1\) and \(b = 2k_2+1\) for some integers \(k_1\) and \(k_2\text{.}\) (You cannot use the same integer \(k\) for both.)
Proof. Let \(a\) and \(b\) be integers. Assume \(\ldots\text{.}\) By the definitions of even and odd, we can write \(\ldots\) (use hint) Then, first, \(a+b= \ldots\text{.}\) Thus, \(\ldots.\) Next, \(ab =\ldots\text{.}\) Thus, \(\ldots.\)
Use Theorem 5.2.18, Theorem 5.3.13, and Definition 4.1.8 to prove that if \(a \mid b\) and \(b \mid c\text{,}\) then \(a \mid c\) for any integers \(a\text{,}\)\(b\text{,}\) and \(c\text{.}\) Hint: Write \(b=ak_1\) and \(c=bk_2\) for some integers \(k_1\) and \(k_2\text{.}\) You cannot use the same integer \(k\) for both.
Proof. Let \(a\text{,}\)\(b\text{,}\) and \(c\) be integers. Assume \(a \mid b\) and \(b \mid c\text{.}\) By the definitions of divides, we can write \(b=ak_1\) and \(c=bk_2\) for some integers \(k_1\) and \(k_2\text{.}\) Then,
\begin{equation*}
c = bk_2 = (ak_1)k_2 = a(k_1k_2) = ak
\end{equation*}
where \(k = k_1k_2\) is an integer. Thus, by definition of divides, \(a \mid c\text{.}\)\(\Box\)
It follows from this exercise that if the last digit of an integer is even, then that integer is even and if the last digit of an integer is odd, then that integer is odd.
In this exercise, we prove Theorem 4.5.6(a). Let \(a\text{,}\)\(n\text{,}\)\(q\text{,}\) and \(r\) be integers such that \(a = nq + r\text{.}\) (We are most interested in the case where \(r = a\)\(\fn{mod}\)\(n\text{,}\) but the result holds in general.)
Use Theorem 5.2.18, Theorem 5.3.13, and Definition 4.1.8 to prove that for any integer \(d\text{,}\) if \(d \mid a\) and \(d \mid n\text{,}\) then \(d \mid r\text{.}\) Hint: Solve for \(r\text{.}\)
Explain why it follows from 18.(a) and 18.(c) that the list of common divisors of \(a\) and \(n\) is the same as the list of common divisors of \(n\) and \(r\text{.}\)
Each of the following statements is false. First, find a counterexample and then use Theorem 5.3.17 to write the negation of each statement in a sentence. Hint: Use DeMorgan’s laws Theorem 5.1.23.
For any integers \(a\) and \(b\text{,}\) if \(a+b\) is even, then \(a\) is even or \(b\) is even.
Consider the following conditional statement \(S\text{:}\) For any integers \(a\) and \(b\text{,}\) if \(ab=0\text{,}\) then \(a=0\) or \(b=0\text{.}\) Use 26.(a) to rewrite \(S\) without “or”.
Consider the following conditional statement \(S\) from Exercise 26: For any integers \(a\) and \(b\text{,}\) if \(ab=0\text{,}\) then \(a=0\) or \(b=0\text{.}\) Use Theorem 5.2.18, Theorem 5.3.13, and Theorem 5.3.19 to prove \(S\text{.}\) Hint: if \(a \neq 0\text{,}\) then you may divide each side of the equation \(ab=0\) by \(a\text{.}\)
