Skip to main content

Section 4.2 The Division Algorithm

In this section, we continue our discussion of integer division. We introduce vocabulary to describe the result of dividing one integer by another when the answer is not an integer. Next, we revisit polynomials and use polynomials to prove facts about even, odd, and divisors using cases.

Subsection 4.2.A The Division Algorithm, \(\fn{div}\text{,}\) and \(\fn{mod}\)

As we saw in Section 4.1, sometimes when we divide one integer by another integer we get an integer answer, such as
\begin{equation*} 40 \div 5 = \frac{40}{5} = 8\text{.} \end{equation*}
We said that 5 divides 40 and wrote \(5 \mid 40\text{.}\) Other times, we get a fraction that is not an integer, such as
\begin{equation*} 23 \div 4= \frac{23}{4} = 5.75\text{.} \end{equation*}
We said that 4 does not divide 23 and wrote \(4 \nmid 23\text{.}\) How can we think of \(23 \div 4\) in terms of integers?

Example 4.2.1 Cookies and Children.

Use the idea of giving 23 cookies to four children to describe \(23 \div 4\) in terms of (only) integers.
Solution.
Imagine that I have 23 cookies and four children. I want to give each child as many cookies as I can, but, to be fair, each child should have the same number of cookies as the other children. What should I do? I can give each child five cookies. That accounts for \(5 \times 4 = 20\) of the cookies, but I cannot evenly distribute the remaining \(23-20=3\) cookies without breaking them, which I do not want to do. I guess those 3 cookies are for me to eat. We might say \(23 \div 4\) is 5 cookies/child with 3 cookies remaining for me. We can write the equation
\begin{equation*} 23 = 5 \times 4 + 3\text{.} \end{equation*}
We formalize the idea from Example 4.2.1 with the following theorem.

Proof.
Let \(a\) and \(n\) be integers with \(n \ge 1\text{.}\) We prove existence in the case where \(a \ge 0\text{.}\)
Since \(a\) is nonnegative and \(n \ge 1\text{,}\) we can imagine giving \(a\) cookies to \(n\) children. First, I check to see if I have enough cookies for each child to get at least one, and if so, then I hand one cookie to each child. Next, I repeat that step with the remaining cookies as many times as possible. In the end, let’s say that each child gets \(q\) cookies. In total, I gave \(q \times n=qn\) cookies to the children, so there are
\begin{equation*} a-qn=r \end{equation*}
cookies leftover for me. Adding \(qn\) to each side of the equation we get
\begin{equation*} a = qn+r\text{.} \end{equation*}
Because I checked there were enough cookies for each child to get one, I never run out of cookies, and so \(r \ge 0\text{.}\) On the other hand, any time I still have enough cookies to give each child another cookie, I would do that. Therefore, the final number of remaining cookies must be strictly less than the number of children and so \(r \lt n\text{.}\)
The integers \(q\) and \(r\) in the Division Algorithm Theorem 4.2.2 have special names.

Definition 4.2.3 Quotient, Remainder, \(\fn,{div},\text{,}\) and \(\fn{mod}\).

Let \(a\) and \(n\) be integers with \(n \ge 1\) and let \(q\) and \(r\) be integers such that \(a = qn+r\) and \(0 \le r \lt n\text{.}\)
  1. The integer \(q\) is the quotient of \(a \div n\text{.}\) When \(a \ge 0\text{,}\) it is the number of cookies per child in the story. For example, the quotient when \(23 \div 4\) is five.
  2. We write \(a\,\fn{div}\,n =q\text{.}\) For example, \(23\) \(\fn{mod} \) \(4=5\text{.}\)
  3. The integer \(r\) is the remainder of \(a \div n\text{.}\) When \(a \ge 0\text{,}\) it is the number of cookies for me. For example, the remainder when \(23 \div 4\) is three.
  4. We write \(a\, \fn{mod}\, n=r\text{.}\) For example, \(23\,\fn{mod}\,4=3\text{.}\) In many computer programming languages, \(\fn{mod}\) is denoted using the percent symbol (%). For example, we would write \(23 \% 4 = 3\text{.}\)
  5. We say \(a \div n\) is \(q\) with remainder \(r\text{.}\) For example, \(23 \div 4\) is five with remainder three.
  6. In long division the quotient is typically written at the top of the bar and the remainder is the final number at the bottom, as in Figure 4.2.4.
    Figure 4.2.4. Long division calculation for \(23 \div 4\text{.}\)
Let’s see these definitions in action.

Example 4.2.5 Quotient, Remainder, \(\fn{div}\text{,}\) and \(\fn{mod}\).

On this problem we do not use computational technology (except to check).
  1. Find the quotient and the remainder when \(100 \div 9\text{.}\) Use your answer to calculate \(100\) \(\fn{div}\) \(9\) and \(100\) \(\fn{mod}\) \(9\text{.}\)
    Solution.
    Starting with 100 cookies, we recognize that \(9 \times 11 = 99\) and so we can hand each child 11 cookies, leaving us with \(100 - (11\times 9) = 100-99 = 1\) cookie.
    If we were using computational technology, we could calculate \(100 \div 9 = 11.1111.\text{..}\) and again see that 11 is the largest number of cookies we can give each child, as there are not enough cookies to give each child 12 cookies.
    If we did a long division instead, we would get the same answer, as shown in Figure 4.2.4.
    Figure 4.2.6. Long division calculation for \(100 \div 9\text{.}\)
    Notice that in the long division we calculate the remainder in two steps. First, we give each child 10 cookies for a total of \(10 \times 9 = 90\) cookies (although 0 is not written), so the remainder is \(100-90 = 10\text{.}\) Next, we give each child 1 cookie for a total of \(1 \times 9 = 9\) cookies, so the final remainder is \(10-9=1\text{.}\)
    Using any way of thinking of this division, we get
    \begin{equation*} 100 = 11(9) +1\text{,} \end{equation*}
    so the quotient is 11 and the remainder is 1. Thus, \(100\) \(\fn{div}\) \(9=11\) and \(100\) \(\fn{mod}\) \(9=1\text{.}\)
  2. Find the quotient and the remainder when \(35 \div 5\text{.}\) Use your answer to calculate \(35\) \(\fn{mod}\) \(5\) and \(35\) \(\fn{mod}\) \(5\text{.}\)
    Solution.
    Write \(35 = 7(5)\) so the quotient is seven. To find the remainder, think of the equation as \(35 = 7(5)+0\text{,}\) so the remainder is zero. Thus, \(35\) \(\fn{mod}\) \(5=7\) and \(35\) \(\fn{mod}\) \(5=0\)
  3. Use the \(\fn{mod}\) notation (or %) to describe whether an integer is even or odd.
    Solution.
    An integer \(n\) is even if \(n=2k\) for some integer \(k\text{.}\) When we divide, we get \(n \div 2 = k\) and the remainder is zero. Thus, \(n\) is even exactly when \(n\) \(\fn{mod}\) \(2=0\) or, equivalently, when \(n\%2=0\text{.}\)
    An integer \(n\) is odd if \(n=2k+1\) for some integer \(k\text{.}\) When we divide, we get \(n \div 2 = k\text{,}\) and the remainder is one. Thus, \(n\) is even exactly when \(n\) \(\fn{mod}\) \(2=1\) or, equivalently, when \(n\%2=1\text{.}\)
It is your turn to practice.

Activity 4.2.A Practice with Div and Mod.

In this activity, do all calculations by hand.
  1. Find the quotient and the remainder when \(73 \div 7\text{.}\) State your answer using \(\fn{mod}\) and \(\fn{mod}\text{.}\)
  2. Find the quotient and the remainder when \(66 \div 6\text{.}\) State your answer using \(\fn{mod}\) and \(\fn{mod}\text{.}\)
  3. Find the quotient and the remainder when \(3 \div 10\text{.}\) State your answer using \(\fn{mod}\) and \(\fn{mod}\text{.}\)
  4. Calculate \(27\) \(\fn{mod}\) 10, 115 \(\fn{mod}\) 10, and 123,456,789 \(\fn{mod}\) 10. Hint: Subtract multiples of 10.
  5. What do you notice in (d)? State your answer as a conjecture.
  6. For a nonnegative integer \(a\text{,}\) what are the possible values of \(a\) \(\fn{mod}\) \(10\text{?}\) State your answer as a conjecture.
  7. For a nonnegative integer \(a\) and an integer \(n \ge 1\text{,}\) what are the possible values of \(a\) \(\fn{mod}\) \(n\text{?}\) State your answer as a conjecture.

Subsection 4.2.B Algebra: Polynomials

The Division Algorithm Theorem 4.2.2 gives us expressions such as \(2k+1\) for an odd integer or \(3q+2\) for an integer where that integer \(\fn{mod}~ 3 = 2\text{.}\) We might square an even integer to get an expression of the form \(4n^2\text{.}\) These expressions are polynomials. In this section, we take a look at polynomials, including how to simplify products and powers. We start with the definition.

Definition 4.2.8 Polynomials.

 
  1. For an integer \(n\text{,}\) a polynomial in \(n\) is a sum of constant multiples of powers of \(n\text{.}\) For example, \(2m^4+5m^2-m+7\) is a polynomial in \(m\text{.}\) To see why, we can rewrite this polynomial to show the powers of \(n\text{.}\)
    \begin{equation*} 2m^4+5m^2-m+7=2(m^4)+5(m^2)+(-1)(m^1)+7(m^0)\text{.} \end{equation*}
  2. In a polynomial, the integer in front of a power of \(n\) is the coefficient of that power of \(n\text{.}\) For example, in the polynomial \(2m^3+5m^2-m+7\text{,}\) the coefficient of \(m^4\) is 2, the coefficient of \(m^2\) is 5, the coefficient of \(m\) is \(-1\text{,}\) and the coefficient of \(m^3\) is 0.
  3. In a polynomial, the coefficient of \(m^0\) is the constant term. For example, the constant term of \(2m^3+5m^2-m+7\) is 7.
  4. We add polynomials by collecting like terms. For example
    \begin{equation*} \begin{aligned} (k^3 + 2k -7) + (4k^3 + k^2 + 2) &= (k^3+4k^3) + (k^2) + (2k) + (-7 +2)\\ & = 5k^3+k^2+2k-5 \end{aligned} \end{equation*}
  5. To multiply or expand a product of polynomials, we use the distributive rule. See, for example, Example 4.2.9.
We use the distributive rule Definition 2.1.20 to expand polynomials.

Example 4.2.9 Multiplying polynomials.

 
  1. Expand \(n^2(2n+1)\text{.}\)
    Solution.
    By the distributive rule,
    \begin{equation*} n^2(2n+1) = n^2(2n) + n^2(1) = 2n^3+n^2\text{.} \end{equation*}
  2. Expand \((n+2)(n+3)\text{.}\)
    Solution.
    By the distributive rule (repeatedly),
    \((n+3)(n+2)\) = \(n(n+2) + 3(n+2)\)
    = \(\underbrace{(n)(n)}_{\text{ First } } +\underbrace{(n)(2)}_{\text{ Outside } } + \underbrace{(3)(n)}_{\text{ Inside } } + \underbrace{(3)(2)}_{\text{ Last } }\)
    = \(n^2 + 2n + 3n + 6\)
    = \(n^2+5n + 6\)
    The words under each product indicate the original location of the two integers that are multiplied. This method is First, Outside, Inside, Last or FOIL.
There is a nice set of visualizations of multiplying polynomials in \(x\) as areas.
 1 
This lesson is from the College Algebra Foundations course by Lumen Learning.
Try your hand at multiplying polynomials with discrete variables.

Activity 4.2.B Multiplying polynomials.

Expand and simplify each expression.
  1. \(\displaystyle 2n(3n^2+2n-1)\)
  2. \(\displaystyle (k-2)(k+1)\)
  3. \(\displaystyle (m+1)^2\)
  4. \(\displaystyle (2q+1)^2\)
  5. \(\displaystyle (n+3)(n-3)\)
  6. \((n+b)(n-b)\) for any integer \(b\)

Subsection 4.2.C Proof Format: Proof by Cases

We can use the Division Algorithm Theorem 4.2.2 to prove that every integer is even or odd, but never both.

Example 4.2.11 Every integer is even or odd.

Use the Division Algorithm Theorem 4.2.2 to prove that every integer is even or odd.
Solution.
Proof Let \(a\) be an integer. By the Division Algorithm Theorem 4.2.2 with \(n=2\text{,}\) there exist unique integers \(q\) and \(r\) such that \(a=qn+r\) and \(0 \le r \lt 2\text{.}\) Note that \(r=0\) or \(r=1\text{.}\) Since \(r\) is unique, we are in exactly one of these two cases. Case 1: Assume \(r=0\text{.}\) Then \(a = 2q+0 = 2q\) is even, by the definition of even. Case 2: Assume \(r=1\text{.}\) Then \(a=2q+1\) is odd, by the definition of odd. In either case \(a\) is even or \(a\) is odd.
As in Example 4.2.11, the Division Algorithm Theorem 4.2.2 can be used to break a proof into cases, similar to how we break counting arguments into cases in Section 2.2. Here is the proof format.
In a proof by cases, it is important that the cases cover all of the possibilities. Sometimes we need to explain that up front. The phrase “We consider \(n\) cases” that alerts the reader that we are using a proof by cases. The assumption for each case “Assume that …”. is stated as a complete sentence (with a period at the end) before any additional argument is presented. After we finish the cases, we summarize using the phrase “in either case”. If there are more than two cases, we use “in all cases”.

Activity 4.2.C Proof by Cases: \(n^2 + n\) is even.

 
  1. Copy the following example of a proof by cases. Prove that \(n^2+n\) is even for any integer \(n\text{.}\)

    Proof.
    Let \(n\) be an integer. By Example 4.2.11, \(n\) is even or \(n\) is odd. We consider two cases.
    Case 1: Assume \(n\) is even. By the definition of even, \(n = 2k\) for some integer \(k\text{.}\) Thus
    \begin{equation*} n^2+n=(2k)^2+(2k) = 4k^2+2k = 2(2k^2+k)\text{,} \end{equation*}
    so \(n^2+n\) is even.
    Case 2: Assume \(n\) is odd. By the definition of odd, \(n=2k+1\) for some integer \(k\text{.}\) Thus
    \begin{equation*} n^2+n= (2k+1)^2 +(2k+1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1)\text{,} \end{equation*}
    so \(n^2+n\) is even.
    In either case, \(n^2+n\) is even.
  2. Edit the proof in (a) to prove that \(n^2 - n\) is even for any integer \(n\text{.}\)
We give another example of proof by cases.

Example 4.2.14 Using proof by cases to prove multiple of three.

Use a proof by cases to prove
\begin{equation*} 3 \mid n(n+1)(n+2) \end{equation*}
for any integer \(n\text{.}\)
Solution.
Let \(n\) be an integer. By the Division Algorithm Theorem 4.2.2, we can write
\begin{equation*} n=3q+r \end{equation*}
for some integers \(q\) and \(r\) with \(0 \le r \lt 3\text{.}\) The only possible values of \(r\) are \(r=0\text{,}\) \(r=1\text{,}\) and \(r=2\text{.}\) We consider three cases.
Case 1: Assume \(r=0\text{.}\) In this case, \(n=3q\) and so
\begin{equation*} \begin{aligned} n(n+1)(n+2)&= (3q)(3q+1)(3q+2)\\ & = 3[q(3q+1)(3q+2)] \\ &= 3k \end{aligned} \end{equation*}
where \(k = q(3q+1)(3q+2)\text{.}\) Thus, \(3\mid n(n+1)(n+2)\text{.}\)
Case 2: Assume \(r=1\text{.}\) In this case, \(n=3q+1\) and so
\begin{equation*} \begin{aligned} n(n+1)(n+2)&= (3q+1)(3q+2)(3q+3)\\ & = (3q+1)(3q+2)3(q+1) \\ &=3[(3q+1)(3q+2)(q+1)] \\ &= 3k \end{aligned} \end{equation*}
where \(k = (3q+1)(3q+2)(q+1)\text{.}\) Thus, \(3\mid n(n+1)(n+2)\text{.}\)
Case 3: Assume \(r=2\text{.}\) In this case, \(n=3q+2\) and so
\begin{equation*} \begin{aligned} n(n+1)(n+2)&= (3q+2)(3q+3)(3q+4)\\ & = (3q+2)3(q+1)(3q+4)\\ &= 3[(3q+2)(q+1)(3q+4)]\\ & = 3k \end{aligned} \end{equation*}
where \(k = (3q+2)(q+1)(3q+4)\text{.}\) Thus, \(3\mid n(n+1)(n+2)\text{.}\)
In all cases, \(3\mid n(n+1)(n+2)\text{.}\)

Subsection 4.2.D Exercises

Subsubsection Exercises for 4.2.A The Division Algorithm, \(\fn{div}\text{,}\) and \(\fn{mod}\)

1. Practice.

Do not use technology or other resources.
  1. Find the quotient and the remainder when \(100 \div 3\text{.}\) State your answer using \(\fn{mod}\) and \(\fn{mod}\text{.}\)
  2. Calculate 20 \(\fn{mod}\) 7 and 20 \(\fn{mod}\) 7.
  3. Explain your answers to (b) using the context of children and cookies as in Example 4.2.1.
Check.
  1. \(100 \fn{ div } 3 = 33\) and \(100 \fn{ mod }3 = 1\)
  2. 2, 6
  3. Hint: Imagine 7 children.

2. Practice.

 
  1. Evaluate each of the following integers: 3 \(\fn{mod}\) 2, 4 \(\fn{mod}\) 2, 5 \(\fn{mod}\) 2, 6 \(\fn{mod}\) 2, 28 \(\fn{mod}\) 2, 125 \(\fn{mod}\) 2.
  2. Which integers have \(n\) \(\fn{mod}\) \(2 = 0\text{?}\)
  3. Which integers have \(n\) \(\fn{mod}\) \(2 = 1\text{?}\)

3. Understand.

On this problem, no justification is required.
  1. Give an example of an integer \(n\) with \(100 \le n \le 200\) and \(n\) \(\fn{mod}\) 2 = 1.
  2. Give an example of an integer \(n\) with \(100 \le n \le 200\) and \(n\) \(\fn{mod}\) 3 = 1.
  3. Give an example of an integer \(n\) with \(100 \le n \le 200\) and \(n\) \(\fn{mod}\) 7 = 1.
  4. Give an example of an integer \(n\) with \(100 \le n \le 200\) and \(n\) \(\fn{mod}\) 10 = 1.
Check.
  1. Hint: Check that your answer is between 100 and 200 and odd.
  2. Hint: Check that your answer is one more than a multiple of three.
  3. Hint: for example, \(7 \times 20 = 140\text{,}\) and so 141 is a possible example.
  4. Hint: Any example is of the form \(1d1\) where \(d\) is a digit.

4. Understand.

 
  1. Evaluate each of the following: 21 \(\fn{mod}\) 10, 37 \(\fn{mod}\) 10, 43 \(\fn{mod}\) 10, 59 \(\fn{mod}\) 10, and 60 \(\fn{mod}\) 10.
  2. Give an example of positive integers \(a\) and \(b\) where \(2a \fn{ mod } 10 = 2b \fn{ mod } 10\) but \(a \fn{ mod } 10 \neq b \fn{ mod } 10\text{.}\)
  3. Give an example of integers \(m\) and \(n\) where \(n \fn{ mod } 10 \neq 0\) and \(m \fn{ mod } 10 \neq 0\text{,}\) but \(nm \fn{ mod } 10 = 0\text{.}\)
Check.
  1. Hint: The answers in some order are \(0,1,3,7,9\text{.}\)
  2. Hint: One way to build an example is to pick \(a\) and use \(b=a+5\text{.}\)
  3. Hint: Neither \(n\) nor \(m\) should be a multiple of 10. Try picking an even integer for \(n\) and an odd multiple of five for \(m\text{.}\)

5. Understand.

Consider an integer \(n \ge 1\text{.}\)
  1. What are the values of \(0\) \(\fn{mod}\) \(n\) and \(0\) \(\fn{mod}\) \(n\text{?}\) Explain.
  2. What are the values of \(n\) \(\fn{mod}\) \(n\) and \(n\) \(\fn{mod}\) \(n\text{?}\) Explain.
  3. If \(a\) is an integer with \(0 \le a \lt n\text{,}\) what can you say about \(a\) \(\fn{mod}\) \(n\) and \(a\) \(\fn{mod}\) \(n\text{?}\) Explain.
Check.
  1. Hint: The answers in some order are 0 and \(n\text{.}\)
  2. Hint: The answers in some order are 0 and 1.
  3. Hint: The answers in some order are 0 and \(a\text{.}\)

6. Understand.

 
  1. Use the Division Algorithm Theorem 4.2.2 to explain how any integer can be written in the form \(3q\text{,}\) \(3q+1\text{,}\) or \(3q+2\text{.}\) Hint: We used this fact in Example 4.2.14.
  2. Use the Division Algorithm Theorem 4.2.2 to explain how any integer \(n\) can be written in the form \(n=10q+s\) where \(s\) is a digit, namely the last digit of \(n\text{.}\)
Check.
  1. Hint: By the Division Algorithm, \(a=3q+r\) where \(0 \le r \lt 3\text{.}\) What are the possible values of the integer \(r\text{?}\)
  2. Hint: Explain why \(0 \le s \lt 10\) and so \(s\) is the last digit of \(n\text{.}\)

7. Recap.

Do you know …
  1. What the Division Algorithm says?
  2. What restrictions are on the remainder \(r\) when we calculate \(n \div a\text{?}\)
  3. How to calculate \(\fn{mod}\) and \(\fn{mod}\) using long division?
Check.
  1. Hint: \(a^2=\underline{\hspace{0.5in}}q^2 + \underline{\hspace{0.5in}}qs + \underline{\hspace{0.5in}}s^2\)
  2. Hint: Expand and simplify \(a^2-s^2\) and factor out 10.
  3. Hint: Copy and complete Table 4.2.22.
    Table 4.2.22. The last digit of squares
    \(s\) 0 1 2 3 4 5 6 7 8 9
    \(s^2\) 16
    Last digit of \(s^2\) 6
  4. Hint: Use the hint.

8. Explore.

 
  1. Calculate 247 \(\fn{mod}\) 18 and 247 \(\fn{mod}\) 18.
  2. Note that \(247 \div 18= 13.7222\ldots\text{.}\) Explain how we could calculate 247 \(\fn{mod}\) 18 using this equation.
  3. In general, if we know the decimal number \(n \div a\text{,}\) how can we find \(a\) \(\fn{mod}\) \(n\text{?}\) You may describe your answer in words.
  4. Again, note that \(247 \div 18= 13.7222\ldots\text{.}\) Explain how we could calculate 247 \(\fn{mod}\) 18 using this equation.
  5. In general, if we know the decimal number \(n \div a\) and we know \(a\) \(\fn{mod}\) \(n\text{,}\) how can we find \(a\) \(\fn{mod}\) \(n\text{.}\) You may describe your answer in words.

9. Explore.

The International Standard Book Number (ISBN) is a 13-digit integer used to identify a book. The last digit is calculated from the first 12 digits and is used to check whether a 13-digit number is a legitimate ISBN. This check digit is useful to avoid copying errors. Here is how. For
\begin{equation*} \text{ ISBN } = abcdefghijkmx \end{equation*}
the 13th check digit \(x\) is chosen so that
\begin{equation*} (a + 3b + c + 3d + e + 3f + g + 3h + i + 3j + k + 3m + x) \fn{ mod } 10 = 0 \end{equation*}
  1. Confirm that 9780691151649 is a valid ISBN. Note that \(a=9\text{,}\) \(b=7\text{,}\) …, \(x=9\text{.}\)
  2. Calculate the check digit for the ISBN beginning 123450123450.
Check.
  1. Hint: Calculate \((9 + 3 \cdot 7 +8 + 3 \cdot 0 + \ldots ) \fn{ mod } 10\text{.}\) You should get zero.
  2. \(\displaystyle x=4\)

Subsubsection Exercises for 4.2.B Algebra: Polynomials

10. Practice.

 
  1. What is the coefficient of \(n^2\) in the polynomial \(5n^3-n^2+3n+8\text{?}\)
  2. What is the constant term of the polynomial \(5n^3-n^2+3n+8\text{?}\)
  3. What is the coefficient of \(k\) in the polynomial \(5k^2+k\text{?}\)
  4. What is the constant term of the polynomial \(5k^2+k\text{?}\)

11. Practice.

Expand and simplify.
  1. \(\displaystyle n(2n^2+1)\)
  2. \(\displaystyle (k+1)(k+3)\)
  3. \(\displaystyle (m-1)(m+1)\)
Check.
  1. \(\displaystyle 2n^3+n\)
  2. Hint: The coefficient of \(k\) in the answer is 4.
  3. Hint: The constant term of the answer is \(-1\text{.}\)

12. Understand.

Expand and simplify.
  1. \((n+1)^2\text{.}\)
  2. \((2k+1)^2\text{.}\)
  3. \(\displaystyle (m+2)^2-(m-1)^2\)
Check.
  1. Hint: The coefficient of \(n\) in the answer is 2.
  2. Hint: In the answer \(k^2\) and \(k\) have the same coefficient.
  3. \(\displaystyle 6m+3\)

13. Recap.

Do you know …
  1. What a polynomial is?
  2. How to multiply polynomials or square a polynomial?
  3. What the abbreviation FOIL stands for?

14. Explore.

By Exercise 66.(b), we can write a positive integer \(a\) as \(a=10q+s\) for some integers \(q\) and \(s\) where \(s\) is the last digit of \(a\text{.}\) Note that \(s=0,1,2,\ldots,9\text{.}\)
  1. Expand and simplify \(a^2\) in terms of \(q\) and \(s\text{.}\)
  2. Show that \(a^2-s^2\) is a multiple of 10. It follows that \(a^2\) \(\fn{mod}\) 10 \(=s^2\) \(\fn{mod}\) 10 and therefore the last digit of \(a^2\) is equal to the last digit of \(s^2\text{.}\)
  3. What are the possible last digits of \(s^2\text{?}\) Hint: Recall that \(s\) is a digit, so you can check each value of \(s=0,1,2,\ldots,9\text{.}\)
  4. What are the possible last digits of any integer \(a^2\text{?}\) Hint: Use the results of 14.(b) and 14.(c).

Subsubsection Exercises for 4.2.C Proof Format: Proof by Cases

15. Practice.

For any integer \(n\text{,}\) copy and edit the proof in Activity 4.2.C to prove that
\begin{equation*} n^2+3n+1 \end{equation*}
is odd for any integer \(n\text{.}\)
Check.
Hint: In the case where \(n=2k+1\text{,}\) expand and simplify \((2k+1)^2+3(2k+1)+1=4k^2+10k+5 = 2(\underline{\hspace{0.5in}})+1\text{.}\) Then, fill in the parentheses. If you need to, set it equal to \(2m+1\) and solve for \(m\text{.}\)

16. Understand.

Copy and edit the proof in Example 4.2.14 to prove
\begin{equation*} 3 \mid n(n+1)(n-1) \end{equation*}
for any integer \(n\text{.}\)
Check.
Hint: As in the proof in Example 4.2.14, keep the product in factored form and find a way to factor out a three from one of the factors.

17. Recap.

Do you know …
  1. How to write a proof by cases?
  2. What needs to be true about the list of cases in a proof-by-cases?
  3. How we can use the Division Algorithm to create cases for a proof by cases?

18. Explore.

  Use proof by cases Subsection 4.2.C to prove
\begin{equation*} 3 \nmid 2n^2 +n+1 \end{equation*}
for any integer \(n\text{.}\) Hint: Use Exercise 6 6.(a) to create three cases. Notice that we are proving something is not a multiple of three.

19. Explore.

Use cases Subsection 4.2.C to prove that \(n^2\) \(\fn{mod}\) \(4 = 0\) or \(n^2\) \(\fn{mod}\) \(4 = 1\) for any integer \(n\text{.}\) Hint: Use cases based on whether \(n\) is even or \(n\) is odd. Note that in one case we get \(n^2\) \(\fn{mod}\) \(4 = 0\) and in the other case we get \(n^2\) \(\fn{mod}\) \(4 = 1\text{.}\) Officially, we are using a modified version of proof by cases that we revisit in Section 5.1.
Check.
Hint: Copy and edit the proof in Activity 4.2.C (a) and follow the hint.

20. Explore.

Use cases Subsection 4.2.C to prove that \(n^2\) \(\fn{mod}\) \(3 = 0\) or \(n^2\) \(\fn{mod}\) \(3 = 1\) for any integer \(n\text{.}\) Hint: Use Exercise 6 6.(a) and consider three cases. Note that in one case we get \(n^2\) \(\fn{mod}\) \(3 = 0\) and in the other two cases we get \(n^2\) \(\fn{mod}\) \(3 = 1\text{.}\) Officially, we are using a modified version of proof by cases that we revisit in Section 5.1.
Check.
Hint: Copy and edit the proof in Example 4.2.14 and follow the hint.
PrevTopNext