\(\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\,}$}}}
\)
Section4.1Integer Division
In this section, we begin our exploration of integer division by discussing even and odd integers, divisors, and fractions.
At Perpetual High School, a never-ending line of students marches down a never-ending hallway of lockers. The first student opens each locker. The second student closes every other locker (002, 004, 006, etc.) The third student changes the state of every third locker, which means closing 003, opening 006, etc. And so on, with the \(d^{th}\) student changing the state of every \(d^{\text{ th } }\) locker.
There are two very reasonable answers to (d). One conjecture, Conjecture A, depends on the number of students who touch the locker. The other conjecture, Conjecture B, depends only on the locker number. Which conjecture did you make in (d): A or B? What is the other conjecture?
What is the final state of locker 99? Explain.
Solution.
First note that the last student to touch locker 99 is the \(99^{\text{ th } }\) student. So to determine the final state of locker 99 we only need to know which students from 1-99 touched it. We can factor 99 in several ways: \(1 \times 99\text{,}\)\(3 \times 33\text{,}\) and \(9 \times 11\text{.}\) That is, the only students from 1-99 to touch locker 99 are students one, three, nine, 11, 33, and 99. Student one opens locker 99, student three closes it, student nine opens it, student 11 closes it, student 33 opens it, and student 99 closes it. The final state of locker 99 is that it is closed.
Conjecture how the final state of a locker depends on the number of students who touch the locker.
Solution.
When the number of students who touch the locker is even, as was the case for locker 99, the final state of the locker is closed. When the number of students who touch the locker is odd, as was the case for locker 100, the final state of the locker is open. This conjecture is Conjecture A.
Conjecture which lockers have an odd number of students that touch that locker.
Solution.
Notice that students who touch the locker tend to come in pairs. For example, locker 99 is touched by students one and 99, students three and 33, and students nine and 11. As another example, locker 100 is touched by students one and 100, students two and 50, students four and 25, and students five and 20. But there is one additional student who touches locker 100, student 10, which makes the total number of students touching locker 100 odd. Why is student 10 not in a pair? Because \(10 \times 10 = 100\) or, in other words, \(100 = 10^2\text{.}\) We conjecture that lockers touched by an odd number of students have locker numbers equal to the square of an integer, known as a perfect square. This conjecture is Conjecture B.
We have seen several situations in which it mattered whether an integer is even or odd. An odd number of bridges was problematic in solving the Bridges Puzzle in Activity 3.1.A. The chromatic number of the cycle \(C_s\) and the wheels \(W_s\) depended on whether \(s\) was even or odd. In each of those examples, we recognize that an even integer is the sum of twos: on-off, on-off, …, on-off in the Bridges Puzzle or black-white, black-white, …, black-white in coloring a cycle. That is, \(n\) is even if we can write
\begin{equation*}
n = \underbrace{2 + 2 + 2 + \ldots + 2}_{k \text{ times } } = 2k\text{.}
\end{equation*}
Equivalently, we can think of even integers as those that divide exactly in half. That is, \(n=k+k = 2k\text{.}\) We state the formal definition.
The integer \(n\) is even if \(n=2k\) for some integer \(k\text{.}\) For example, 18 is even because \(18=2(9)\text{.}\) If we wanted to be formal, we would say \(18=2k\) where \(k=9\text{.}\)
The integer \(n\) is odd if \(n=2k+1\) for some integer \(k\text{.}\) For example, 19 is odd because \(19 = 2(9)+1\text{.}\) If we wanted to be formal, we would say \(19=2k+1\) where \(k=9\text{.}\)
You probably know many facts about even and odd integers. In this example, we use only the definitions.
Use the definition of even to show that \(6t\) is even for any integer \(t\text{.}\)Solution.
We want to write \(6t=2k\) for some integer \(k\text{.}\) We can solve to find \(k\text{.}\) We divide by two to get \(k=3t\text{,}\) which is an integer. Officially, we need to use that value of \(k\) to write
Use the definition of odd to show that \(2m-1\) is odd for any integer \(m\text{.}\)Solution.
We want to write \(2m-1 = 2k+1\) for some integer \(k\text{.}\) We can solve to find \(k\text{.}\) First, we subtract and factor to get \(2k=(2m-1)-1=2m-2=2(m-1)\text{.}\) Next, we divide by two to get \(k=m-1\text{,}\) which is an integer. Officially, we need to use that value of \(k\) to write
Use the definition of odd to show that, for any integer \(m\text{,}\) the integer \(4m+1\) is always odd. Hint: Once you find a useful value of \(k\text{,}\) write \(4m+1\) in the form \(2k+1\text{.}\)
In Activity 4.1.B(c) we asked if zero is even, odd, both, or neither. A common incorrect answer is neither, perhaps because neither is the correct answer to a different question, namely is zero positive, negative, both, or neither? Let’s show that zero is even and not odd.
Use the definition to show that zero is not odd.
Solution.
Suppose that we could write \(0 = 2k+1\text{.}\) We can subtract one to get \(2k=-1\) and then divide by two to get \(k = ^-\frac{1}{2}\text{.}\) Since \(^-\frac{1}{2}\) is the only possible value of \(k\text{,}\) and \(^-\frac{1}{2}\) is not an integer, it follows that zero is not odd.
In the Lockers Puzzle Activity 4.1.A, the \(d^{\text{ th } }\) student touches locker \(d\text{,}\) locker \(d+d=2d\text{,}\) locker \(d+d+d=3d\text{,}\) etc. In general, the \(d^{\text{ th } }\) student touches locker \(n\) when we can write
\begin{equation*}
n=\underbrace{d+d+ \ldots+d}_{k \text{ times } } =dk
\end{equation*}
for some integer \(k\text{.}\) We make this concept formal with another definition.
The nonzero integer \(d\) divides integer \(n\text{,}\) denoted \(d \mid n\text{,}\) if \(n = dk\) for some integer \(k\text{.}\) For example, 3 divides 15, denoted \(3 \mid 15\) because \(15 = 3(5)\text{.}\) Note also that \(3 \mid -15\) because \(-15 = 3(-5)\) and \(-3 \mid 15\) because \(15 = -3(-5)\text{.}\)
If \(d \mid n\text{,}\) then \(d\) is a divisor (or factor) of \(n\text{.}\) For example, the (positive) divisors of 15 are: 1, 3, 5, and 15 because \(1 \times 15 = 15\) and \(3 \times 5=15\text{.}\) (It is harder to know that we found all the positive divisors.) The complete list of 15 divisors is \(\pm\) 1, \(\pm\) 3, \(\pm\) 5 and \(\pm\) 15.
Use the definition of divides to show that \(5 \mid (5n-20)\text{.}\)Solution.
Factor to write \(5n-20 = 5(n-4)\text{,}\) so \(5 \mid (5n-20)\text{.}\) If we wanted to be formal, we could write \(5n-20 = 5k\) where \(k=n-4\text{.}\)
Can we divide by zero? That is, is zero a divisor of any integer? Explain.
Solution.
We are asking if \(0 \mid n\) for any integer \(n\text{.}\) In Definition 4.1.8 we did not allow the divisor \(d\) to be zero, so the answer is no. The reason we excluded zero is because if \(n = 0(k) =0\) for some integer \(k\text{,}\) then the only possibility is \(n=0\text{.}\) Therefore, it is impossible for zero to divide any nonzero integer. We also do not allow zero to divide itself either. The answer is no.
We are asking if \(n \mid 0\) for any integer \(n\text{.}\) That means we are looking for an integer \(k\) such that \(0 = (n)k\text{.}\) Since \(0 = (n)0\) and \(k=0\) is an integer, it follows that \(n \mid 0\) for all nonzero integers \(n\text{.}\) The answer is yes.
When we divide one integer by another (nonzero) integer, sometimes we get an integer, but sometimes we get a fraction (rational number) that is not an integer. Here is the formal definition.
For integer \(n\) and nonzero integer \(d\text{,}\) the fraction (or rational number) is the number we get by dividing \(n\) by \(d\text{,}\) meaning
\begin{equation*}
\displaystyle \frac{n}{d} = n \div d\text{.}
\end{equation*}
We can think of the fraction \(\frac{n}{d}\) as representing an equal share of \(n\) objects among \(d\) places. For example, if we have 40 cucumber slices and five pickling jars, then we can put \(40 \div 5 = 8\) slices in each jar. Similarly, if we have four party-sized bags of candy to share equally among ten people, then each person gets \(\frac{4}{10} = 4 \div 10 = .4 = 40\%\) of a bag.
In the fraction \(\frac{n}{d}\text{,}\) the integer on the top of the fraction \(n\) is the numerator and the integer on the bottom of the fraction \(d\) is the denominator. For example, in the fraction \(\frac{4}{10}\) the numerator is four and the denominator is ten.
For integers \(n\text{,}\)\(m\text{,}\)\(a \neq 0\text{,}\) and \(b \neq 0\text{,}\) the fractions \(\frac{n}{a}\) and \(\frac{m}{b}\) are equal (or equivalent), which we write as
if \(nb=ma\text{.}\) For example, \(\frac{6}{15} = .4\) and so \(\frac{4}{10}=\frac{6}{15}\text{.}\) We can cross-multiply to confirm that \((4)(15) = 60 = (6)(10)\text{.}\)
Let \(d\) and \(n\) be integers with \(d\neq 0\text{.}\) Then \(d \mid n\) exactly when \(\frac{n}{d}\) is an integer. Although we have this connection between fractions and divisibility, it is customary to avoid referencing fractions when working with divides.
Every fraction has (infinitely) many different names. We often want to write a fraction in its simplest form. Other times, it is useful to write a fraction with a denominator such that the fraction is not in its simplest form– for example, to add, subtract, or compare fractions. The next theorem verifies both operations.
Which fraction is larger: \(\frac{2}{5}\) or \(\frac{1}{3}\text{?}\)Solution.
We can write each fraction with common denominator \(3 \times 5 = 15\text{.}\) In part (a), we found \(\frac{2}{5} =\frac{6}{15}\text{.}\) Similarly, we can use Theorem 4.1.14 to multiply top and bottom of the fraction \(\frac{1}{3}\) by five to get:
We can imagine \(\frac{6}{15}\) as the amount of pizza each person gets if we have six pizzas shared by 15 people. In that vein, we can imagine \(\frac{5}{15}\) as the amount of pizza each person gets if we have five pizzas shared by 15 people. Each person will get more pizza if we have six pizzas to share versus five pizzas to share, and so \(\frac{6}{15}> \frac{5}{15}\text{.}\) It follows that \(\frac{2}{5}>\frac{1}{3}\text{.}\)
Notice that 6 and 25 do not have any common divisors (other than the integers \(\pm\)1) and so we cannot further reduce the fraction \(\frac{6}{25}\text{.}\)
The integers \(s\) and \(t\) are coprime (or relatively prime) if the only common positive divisor of \(s\) and \(t\) is the integer 1. For example, 6 has positive divisors 1, 2, 3, and 6 whereas 25 has positive divisors 1, 5, and 25 so their only common positive divisor is 1. Therefore, 6 and 25 are coprime.
The fraction \(\frac{s}{t}\) is written in lowest terms if \(s\) and \(t\) are coprime. For example, since 6 and 25 are coprime, it follows that the fraction \(\frac{6}{25}\) is written in lowest tersm.
Reduce \(\displaystyle\frac{2^3}{2^5}\) to lowest terms. Hint: Use the definition of exponential notation Definition 2.4.15 and cancel before multiplying.
How many strings of three uppercase letters are there if we cannot repeat letters?
Solution.
Think of filling in three spaces with uppercase letters. The first space can be any of the 26 uppercase letters. Because repeats are not allowed, the second space can be any of the 25 remaining uppercase letters, and the third space can be any of the 24 remaining uppercase letters. Since steps multiply Theorem 2.2.3, the answer is \((26)(25)(24)\text{.}\)
In the Lockers puzzle Activity 4.1.A, Locker 001 is only touched once. Of all the lockers, which are only touched twice? Make a conjecture that depends on only the locker number.
Of the first 50 lockers, which are touched by the most students in the Lockers Puzzle Activity 4.1.A? Do not use technology or other resources to find the answer. Show work.
Of the first 1,000 lockers, which are touched by the most students in the Lockers puzzle Activity 4.1.A? Use technology or other resources to find the answer. Explain what you looked up and cite your source(s).
SubsubsectionExercises for 4.1.B Even and Odd Integers
When an exercise asks you to use the definition of even or odd, you should use only that definition and algebra. Do not use other facts you might know about even or odd integers.
Hint: Write \(4m+7=2(\hspace{0.5in})+1\) and fill in the parentheses.If you need help figuring out what goes into the parentheses, solve \(4m+7=2k+1\) for \(k\text{.}\)
When an exercise asks you to use the definition of divides, you should use only that definition and algebra. Do not use other facts you might know about divisibility.
For this exercise, all exponents should be nonnegative. (If you have seen negative exponents, the answers should still make sense, just use nonnegative exponents.)
Reduce \(\displaystyle \frac{2^{11}}{2^5}\) to lowest terms. Hint: Use the definition of exponential notation Definition 2.4.15 and cancel before multiplying.
