Skip to main content
Mathematics LibreTexts

3.5: The Division Algorithm and Congruence

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

    Preview Activity 1: Quotients and Remainders
    1. Let \(a = 27\) and \(b = 4\). We will now determine several pairs of integers \(q\) and \(r\) so that \(27 = 4q + r\). For example, if \(q = 2\) and \(r = 19\), we obtain \(4 \cdot 2 + 19 = 27\). The following table is set up for various values of \(q\). For each \(q\), determine the value of \(r\) so that \(4q + r = 27\).
      \(q\) 1 2 3 4 5 6 7 8 9 10
      \(r\)   19           -5    
      \(4q + r\) 27 27 27 27 27 27 27 27 27 27
    2. What is the smallest positive value for r that you obtained in your examples from Part (1)?

      Division is not considered an operation on the set of integers since the quotient of two integers need not be an integer. However, we have all divided one integer by another and obtained a quotient and a remainder. For example, if we divide 113 by 5, we obtain a quotient of 22 and a remainder of 3. We can write this as \(\dfrac{113}{5} = 22 + \dfrac{3}{5}\). If we multiply both sides of this equation by 5 and then use the distributive property to “clear the parentheses,” we obtain

      \(5 \cdot \dfrac{113}{5} = 5 (22 + \dfrac{3}{5})\)
      \(113 = 5 \cdot 22 + 3\)

      This is the equation that we use when working in the integers since it involves only multiplication and addition of integers.
    3. What are the quotient and the remainder when we divide 27 by 4? How is this related to your answer for Part (2)?
    4. Repeat part (1) using \(a = -17\) and \(b = 5\). So the object is to find integers \(q\) and \(r\) so that \(-17 = 5q + r\). Do this by completing the following table.
      \(q\) -7 -6 -5 -4 -3 -2 -1
      \(r\) 18         -7  
      \(5q + r\) -17 -17 -17 -17 -17 -17 -17
    5. The convention we will follow is that the remainder will be the smallest positive integer \(r\) for which \(-17 = 5q + r\) and the quotient will be the corresponding value of \(q\). Using this convention, what is the quotient and what is the remainder when -17 is divided by 5?
    Preview Activity 2: Some Work with Congruence Modulo \(n\)
    1. Let \(n\) be a natural number and let \(a\) and \(b\) be integers.

      (a) Write the definition of “\(a\) is congruent to \(b\) modulo \(n\),” which is written \(a \equiv b\) (mod \(n\)).

      (b) Use the definition of “divides” to complete the following:
      When we write \(a \equiv b\) (mod \(n\)), we may conclude that there exists an integer \(k\) such that ....

      We will now explore what happens when we multiply several pairs of integers where the first one is congruent to 3 modulo 6 and the second is congruent to 5 modulo 6. We can use set builder notation and the roster method to specify the set \(A\) of all integers that are congruent to 2 modulo 6 as follows:
      \[A = \{a \in \mathbb{Z} | a \equiv 3\ (mod\ 6)\} = \{... -15, -9, -3, 3, 9, 15, 21, ...\}\]

    2. Use the roster method to specify the set \(B\) of all integers that are congruent to 5 modulo 6.
      \[B = \{b \in \mathbb{Z} | b \equiv 5\ (mod\ 6)\} = ...\]
      Notice that \(15 \in A\) and \(11 \in B\) and that \(15 + 11 = 26\). Also notice that \(26 \equiv 2\) (mod 6) and that 2 is the smallest positive integer that is congruent to 26 (mod 6).
    3. Now choose at least four other pairs of integers \(a\) and \(b\) where \(a \in A\) and \(b \in B\). For each pair, calculate \((a + b)\) and then determine the smallest positive integer \(r\) for which \((a + b) \equiv r\) (mod 6). Note: The integer \(r\) will satisfy the inequalities \(0 \le r < 6\).
    4. Prove that for all integers \(a\) and \(b\), if \(a \equiv\) 3 (mod 6) and \(b \equiv\) 5 (mod 6), then \((a + b) \equiv\) 2 (mod 6).

    The Division Algorithm

    Preview Activity \(\PageIndex{1}\) was an introduction to a mathematical result known as the Division Algorithm. One of the purposes of this preview activity was to illustrate that we have already worked with this result, perhaps without knowing its name. For example, when we divide 337 by 6, we often write

    \[\dfrac{337}{6} = 56 + \dfrac{1}{6}. \nonumber\]

    When we multiply both sides of this equation by 6, we get

    \[337 = 6 \cdot 56 + 1 \nonumber\]

    When we are working within the system of integers, the second equation is preferred over the first since the second one uses only integers and the operations of addition and multiplication, and the integers are closed under addition and multiplication. Following is a complete statement of the Division Algorithm.

    The Division Algorithm

    For all integers \(a\) and \(b\) with \(b > 0\), there exist unique integers \(q\) and \(r\) such that

    \(a = bq + r\) and \(0 \le r < b\)

    Some Comments about the Division Algorithm

    1. The Division Algorithm can be proven, but we have not yet studied the methods that are usually used to do so. In this text, we will treat the Division Algorithm as an axiom of the integers. The work in Preview Activity \(\PageIndex{1}\) provides some rationale that this is a reasonable axiom.
    2. The statement of the Division Algorithm contains the new phrase, “there exist unique integers q and r such that ....” This means that there is only one pair of integers \(q\) and \(r\) that satisfy both the conditions \(a = bq + r\) and \(0 \le r < b\). As we saw in Preview Activity \(\PageIndex{1}\), there are several different ways to write the integer \(a\) in the form \(a = bq + r\). However, there is only one way to do this and satisfy the additional condition that \(0 \le r < b\).
    3. In light of the previous comment, when we speak of the quotient and the remainder when we “divide an integer \(a\) by the positive integer \(b\),” we will always mean the quotient \((q)\) and the remainder \((r)\) guaranteed by the Division Algorithm. So the remainder r is the least nonnegative integer such that there exists an integer (quotient) \(q\) with \(a = bq + r\).
    4. If \(a < 0\), then we must be careful when writing the result of the Division Algorithm. For example, in parts (4) and (5) of Preview Activity \(\PageIndex{1}\), with \(a = -17\) and \(b = 5\), we obtained \(-17 = 5 \cdot (-4) + 3\), and so the quotient is -4 and the remainder is 3. Notice that this is different than the result from a calculator, which would be \(\dfrac{-17}{5} = -3.4\). But this means \[\dfrac{-17}{5} = -(3 + \dfrac{4}{10}) = -3 - \dfrac{2}{5}.\] If we multiply both sides of this equation by 5, we obtain \[-17 = 5 (-3) + (-2).\] This is not the result guaranteed by the Division Algorithm since the value of 2 does not satisfy the result of being greater than or equal to 0 and less than 5.
    5. One way to look at the Division Algorithm is that the integer \(a\) is either going to be a multiple of \(b\), or it will lie between two multiples of \(b\). Suppose that \(a\) is not a multiple of \(b\) and that it lies between the multiples \(b \cdot q\) and \(b (q + 1)\), where \(q\) is some integer. This is shown on the number line in Figure 3.2.

    屏幕快照 2019-02-18 下午2.16.27.png

    Figure 3.2: Remainder for the Division Algorithm

    1. If \(r\) represents the distance from \(b \cdot q\) to \(a\), then
      \begin{eqnarray}
      r &=& a - b \cdot q, or\\
      a &=& b \cdot q +r.
      \end{eqnarray}
      From the diagram, also notice that \(r\) is less than the distance between \(b \cdot q\) and \(b (q + 1)\). Algebraically, this distance is
      \begin{eqnarray}
      b (q + 1) - b \cdot q &=& b \cdot q + b - b \cdot q\\
      &=& b.
      \end{eqnarray}
      Thus, in the case where \(a\) is not a multiple of \(b\), we get \(0 < r < b\).
    2. We have been implicitly using the fact that an integer cannot be both even and odd. There are several ways to understand this fact, but one way is through the Division Algorithm. When we classify an integer as even or odd, we are doing so on the basis of the remainder (according to the Division Algorithm) when the integer is “divided” by 2. If \(a \in \mathbb{Z}\), then by the Division Algorithm there exist unique integers \(q\) and \(r\) such that

      \(a = 2q + r\) and \(0 \le r < 2\).

      This means that the remainder, \(r\), can only be zero or one (and not both). When \(r = 0\), the integer is even, and when \(r = 1\), the integer is odd.

    Progress Check 3.26: Using the Division Algorithm
    1. What are the possible remainders (according to the Division Algorithm) when an integer is
      1. (a) Divided by 4?
      2. (b) Divided by 9?
    2. For each of the following, find the quotient and remainder (guaranteed by the Division Algorithm) and then summarize the results by writing an equation of the form \(a = bq + r\), where \(0 \le r < b\).
      1. When 17 is divided by 3.
      2. When -17 is divided by 3.
      3. When 73 is divided by 7.
      4. When -73 is divided by 7.
      5. When 436 is divided by 27.
      6. When 539 is divided by 110.
    Answer

    Add texts here. Do not delete this text first.

    Using Cases Determined by the Division Algorithm

    The Division Algorithm can sometimes be used to construct cases that can be used to prove a statement that is true for all integers. We have done this when we divided the integers into the even integers and the odd integers since even integers have a remainder of 0 when divided by 2 and odd integers have a remainder o 1 when divided by 2.

    Sometimes it is more useful to divide the integer \(a\) by an integer other than 2. For example, if \(a\) is divided by 3, there are three possible remainders: 0, 1, and 2. If \(a\) is divided by 4, there are four possible remainders: 0, 1, 2, and 3. The remainders form the basis for the cases.

    If the hypothesis of a proposition is that “\(n\) is an integer,” then we can use the Division Algorithm to claim that there are unique integers \(q\) and \(r\) such that

    \(n = 3q + r\) and \(0 \le r < 3\)

    We can then divide the proof into the following three cases: (1) \(r = 0\); (2) \(r = 1\); and (3) \(r = 2\). This is done in Proposition 3.27.

    Proposition 3.27

    If \(n\) is an integer, then 3 divides \(n^3 - n\).

    Proof

    Let \(n\) be an integer. We will show that 3 divides \(n^3 - n\) by examining the three cases for the remainder when \(n\) is divided by 3. By the Division Algorithm, there exist unique integers \(q\) and \(r\) such that

    \(n = 3q + r\), and \(0 \le r < 3\).

    This means that we can consider the following three cases:(1) \(r = 0\); (2) \(r = 1\); and (3) \(r = 2\).

    In the case where \(r = 0\), we have \(n = 3q\). By substituting this into the expression \(n^3 - n\), we get

    \begin{eqnarray}
    n^3 - n &=& (3q)^3 - (3q)\\
    &=& 27q^3 - 3q\\
    &=& 3 (9q^3-q).
    \end{eqnarray}

    Since \((9q^3 -q)\) is an integer, the last equation proves that \(3 | (n^3 - n)\).

    In the second case, \(r = 1\) and \(n = 3q + 1\). When we substitute this into \((n^3 -n)\), we obtain

    \begin{eqnarray}
    n^3 - n &=& (3q + 1)^3 - (3q + 1)\\
    &=& (27q^{3}27q^{2} + 27q + 1) - (3q + 1)\\
    &=& 27q^3 + 27q^2 + 6q\\
    &=& 3(9q^3 + 9q^2 + 2q).
    \end{eqnarray}

    Since \((9q^3 + 9q^2 + 2q)\) is an integer, the last equation proves that \(3 | (n^3 - n)\).

    The last case is when \(r = 2\). The details for this case are part of Exercise (1). Once this case is completed, we will have proved that 3 divides \(n^3 - n\) in all three cases. Hence, we may conclude that if n is an integer, then 3 divides \(n^3 - n\).

    Properties of Congruence

    Most of the work we have done so far has involved using definitions to help prove results. We will continue to prove some results but we will now prove some theorems about congruence (Theorem 3.28 and Theorem 3.30) that we will then use to help prove other results.

    Let \(n \in \mathbb{N}\). Recall that if \(a\) and \(b\) are integers, then we say that \(a\) is congruent to \(b\) modulo \(n\) provided that \(n\) divides \(a - b\), and we write \(a \equiv b\) (mod \(n\)). (See Section 3.1.) We are now going to prove some properties of congruence that are direct consequences of the definition. One of these properties was suggested by the work in Preview Activity \(\PageIndex{2}\) and is Part (1) of the next theorem.

    Theorem 3.28: Properties of Congruence Modulo \(n\)

    Let \(n\) be a natural number and let \(a\), \(b\), \(c\), and \(d\) be integers. If \(a \equiv b\) (mod \(n\)) and \(c \equiv d\) (mod \(n\)), then

    1. \(a + c) \equiv (b + d)\) (mod \(n\)).
    2. \(ac \equiv bd\) (mod \(n\)).
    3. For each \(m \in \mathbb{N}\), \(a^{m} \equiv b^{m}\) (mod \(n\)).
    Proof

    We will prove Parts (2) and (3). The proof of Part (1) is Progress Check 3.29. Let \(n\) be a natural number and let \(a\), \(b\), \(c\), and \(d\) be integers. Assume that \(a \equiv b\) (mod \(n\)) and \(c \equiv d\) (mod \(n\)). This means that \(n\) divides \(a - b\) and that \(n\) divides \(c - d\). Hence, there exist integers \(k\) and \(q\) such that \(a - b = nk\) and \(c - d = nq\). We can then write \(a = b + nk\) and \(c = d + nq\) and obtain

    \begin{eqnarray}
    ac &=& (b + nk)(d + nq)\\
    &=& bd + bnq + dnk + n^2kq\\
    &=& bd + n(bq + dk + nkq).
    \end{eqnarray}

    by subtracting \(bd\) from both sides of the last equation, we see that

    \[ac - bd = n (bq + dk + nkq).\]

    Since \(bq + dk + nkq\) is an integer, this proves that \(n | (ac - bd)\), and hence we can conclude that \(ac \equiv bd\) (mod \(n\)). This completes the proof of Part (2).

    Part (2) basically means that if we have two congruences, we can multiply the corresponding sides of these congruences to obtain another congruence. We have assumed that \(a \equiv�� b\) (mod \(n\)) and so we write this twice as follows:

    \begin{eqnarray}
    a &\equiv& b (mod\ n),\ and \\
    a &\equiv& b (mod\ n).
    \end{eqnarray}

    If we now use the result in Part (2) and multiply the corresponding sides of these two congruences, we obtain \(a^2 \equiv b^2\) (mod \(n\)). We can then use this congruence and the congruence \(a \equiv b\) (mod \(n\)) and the result in Part (2) to conclude that

    \[a^2 \cdot b \equiv b^2 \cdot b (mod\ n),\]

    or that \(a^3 \equiv b^3\) (mod \(n\)). We can say that we can continue with this process to prove Part (3), but this is not considered to be a formal proof of this result. To construct a formal proof for this, we could use a proof by mathematical induction. This will be studied in Chapter 4. See Exercise (13) in Section 4.1.

    Progress Check 3.29: Proving Part (1) of Theorem 3.28

    Prove part (1) of Theorem 3.28.

    Answer

    Add texts here. Do not delete this text first.

    Exercise (11) in Section 3.1 gave three important properties of congruence modulo \(n\). Because of their importance, these properties are stated and proved in Theorem 3.30. Please remember that textbook proofs are usually written in final form of “reporting the news.” Before reading these proofs, it might be instructive to first try to construct a know-show table for each proof.

    Theorem 3.30: Properties of Congruence Modulo \(n\)

    Let \(n \in \mathbb{N}\), and let \(a\), \(b\), and \(c\) be integers.

    1. For every integer \(a\), \(a \equiv a\) (mod \(n\)).
      This is called the reflexive property of congruence modulo \(n\).
    2. If \(a \equiv b\) (mod \(n\)), then \(b \equiv a\) (mod \(n\)).
      This is called symmetric property of congruence modulo \(n\).
    3. If \(a \equiv b\) (mod \(n\)) and \(b \equiv c\) (mod \(n\)), then \(a \equiv c\) (mod \(n\)).
      This is called transitive property of congruence modulo \(n\).
    Proof

    We will prove the reflexive property and the transitive property. The proof of the symmetric property is Exercise (3).

    Let \(n \in \mathbb{N}\), and let \(a \in \mathbb{Z}\). We will show that \(a \equiv a\) (mod \(n\)). Notice that

    \[a - a = 0 = n \cdot 0.\]

    This proves that \(n\) divides \(a - a\) and hence, by the definition of congruence modulo \(n\), we have proven that \(a \equiv a\) (mod \(n\)).

    To prove the transitive property, we let \(n \in \mathbb{N}\), and let \(a\), \(b\), and \(c\) be integers. We assume that \(a \equiv b\) (mod \(n\)) and \(b \equiv c\) (mod \(n\)). We will use the definition of congruence modulo \(n\) to prove that \(a \equiv c\) (mod \(n\)). Since \(a \equiv b\) (mod \(n\)) and \(b \equiv c\) (mod \(n\)), we know that \(n | (a - b)\) and \(n | (b - c)\). Hence, there exist integers \(k\) and \(q\) such that

    \begin{eqnarray}
    a - b &=& nk\\
    b - c &=& nq.\\
    \end{eqnarray}

    by adding the corresponding sides of these two equations, we obtain

    \[(a - b) + (b - c) = nk + nq.\]

    If we simplify the left side of the last equation and factor the right side, we get

    \[a - c = n (k + q).\]

    By the closure property of the integers, \((k + q) \in \mathbb{Z}\), and so this equation proves that \(n | (a - c)\) and hence that \(a \equiv c\) (mod \(n\)). This completes the proof of the transitive property of congruence modulo \(n\).

    Using Cases Based on Congruence Modulo \(n\)

    Notice that the set of all integers that are congruent to 2 modulo 7 is

    \[\{n \in \mathbb{Z} | n \equiv 2\ (mod\ 7)\} = \{..., -19, -12, -5, 2, 9, 16, 23,...\}\]

    If we divide any integer in this set by 7 and write the result according to the Division Algorithm, we will get a remainder of 2. For example,

    \begin{eqnarray}
    2 &=& 7 \cdot 0 + 2\\
    9 &=& 7 \cdot 1 + 2\\
    16 &=& 7 \cdot 2 + 2\\
    23 &=& 7 \cdot 3 + 2\\
    -5 &=& 7 (-1) + 2\\
    -12 &=& 7 (-2) + 2\\
    -19 &=& 7 (-3) + 2\\
    \end{eqnarray}

    Is this a coincidence or is this always true? Let’s look at the general case. For this, let \(n\) be a natural number and let \(a \in \mathbb{Z}\). By the Division Algorithm, there exist unique integers \(q\) and \(r\) such that

    \(a = nq + r\) and \(0 \le r < n\).

    By subtracting \(r\) from both sides of the equation \(a = nq + r\), we obtain

    \(a - r = nq\).

    But this implies that \(n | (a - r)\) and hence that \(a \equiv r\) (mod \(n\)). We have proven the following result.

    Theorem 3.31

    Let \(n \in \mathbb{N}\) and let \(a \in mathbb{Z}\). If \(a = nq + r\) and \(0 \le r < n\) for some integers \(q\) and \(r\), then \(a \equiv r\) (mod \(n\)).

    This theorem says that an integer is congruent (mod \(n\)) to its remainder when it is divided by \(n\). Since this remainder is unique and since the only possible remainders for division by \(n\) are 0, 1, 2,..., \(n 1\), we can state the following result.

    Corollary 3.32

    If \(n \in \mathbb{N}\), then each integer is congruent, modulo \(n\), to precisely one of the integers 0, 1, 2, ..., \(n - 1\). That is, for each integer \(a\), there exists a unique integer \(r\) such that

    \(a \equiv r\) (mod \(n\)) and \(0 \le r < n\).

    Corollary 3.32 can be used to set up cases for an integer in a proof. If \(n \in \mathbb{N}\) and \(a \in \mathbb{Z}\), then we can consider \(n\) cases for \(a\). The integer a could be congruent to 0,1, 2, ..., or \(n - 1\) modulo \(n\). For example, if we assume that 5 does not divide an integer \(a\), then we know \(a\) is not congruent to 0 modulo 5, and hence, that \(a\) must be congruent to 1, 2, 3, or 4 modulo 5. We can use these as 4 cases within a proof. For example, suppose we wish to determine the values of \(a^2\) modulo 5 for integers that are not congruent to 0 modulo 5. We begin by squaring some integers that are not congruent to 0 modulo 5. We see that

    \begin{eqnarray}
    1^2 &=& 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ and \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1&\equiv& 1\ (mod\ 5).\\
    3^2 &=& 9 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ and \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 9&\equiv& 4\ (mod\ 5).\\
    6^2 &=& 36 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ and \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 36&\equiv& 1\ (mod\ 5).\\
    8^2 &=& 64 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ and \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 64&\equiv& 4\ (mod\ 5).\\
    9^2 &=& 81 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ and \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 81&\equiv& 1\ (mod\ 5).
    \end{eqnarray}

    These explorations indicate that the following proposition is true and we will now outline a method to prove it.

    Proposition 3.33.

    For each integer \(a\), if \(a \not\equiv 0\) (mod 5), then \(a^2 \equiv 1\) (mod 5) or \(a^2 \equiv 4) (mod 5).

    Proof

    We will prove this proposition using cases for \(a\) based on congruence modulo 5. In doing so, we will use the results in Theorem 3.28 and Theorem 3.30. Because the hypothesis is \(a \not \equiv 0\) (mod 5), we can use four cases, which are: (1)\(a \equiv 1\) (mod 5), (2)\(a \equiv 2\) (mod 5), (3)\(a \equiv 3\) (mod 5), and (4)\(a \equiv 4) (mod 5). Following are proofs for the first and fourth cases.

    Case 1. (\(a \equiv 1\) (mod 5)). In this case, we use Theorem 3.28 to conclude that

    \(a^2 \equiv 1^2\) (mod 5) or \(a^2 \equiv 1\) (mod 5).

    This proves that if \(a \equiv 1\) (mod 5), then \(a^ \equiv 1\) (mod 5).

    Case 4. (\(a \equiv 4\) (mod 5)). In this case, we use Theorem 3.28 to conclude that

    \(a^2 \equiv 4^2\) (mod 5) or \(a^2 \equiv 16\) (mod 5).

    We also know that \(16 \equiv 1\) (mod 5). So we have \(a^2 \equiv 16\) (mod 5) and \(16 \equiv 1\) (mod 5), and we can now use the transitive property of congruence (Theorem 3.30) to conclude that \(a^2 \equiv 1\) (mod 5). This proves that if \(a \equiv 4\) (mod 5), then \(a^2 \equiv 1\) (mod 5).

    Progress Check 3.34 (Using Properties of Congruence)

    Complete a proof of Proposition 3.33 by completing proofs for the other two cases.

    Note: It is possible to prove Proposition 3.33 using only the definition of congruence instead of using the properties that we have proved about congruence. However, such a proof would involve a good deal of algebra. One of the advantages of using the properties is that it avoids the use of complicated algebra in which it is easy to make mistakes.

    Answer

    Add texts here. Do not delete this text first.

    In the proof of Proposition 3.33, we used four cases. Sometimes it may seem a bit overwhelming when confronted with a proof that requires several cases. For example, if we want to prove something about some integers modulo 6, we may have to use six cases. However, there are sometimes additional assumptions (or conclusions) that can help reduce the number of cases that must be considered. This will be illustrated in the next progress check.

    Progress Check 3.35: Using Cases Modulo 6

    Suppose we want to determine the possible values for \(a^2\) modulo 6 for odd integers that are not multiples of 3. Before beginning to use congruence arithmetic (as in the proof of Proposition 3.33) in each of the possible six cases, we can show that some of the cases are not possible under these assumptions. (In some sense, we use a short proof by contradiction for these cases.) So assume that \(a\) is an odd integer. Then:

    • If \(a \equiv 0\) (mod 6), then there exists an integer \(k\) such that \(a = 6k\). But then \(a = 2(3k)\) and hence, \(a\) is even. Since we assumed that \(a\) is odd, this case is not possible.
    • If \(a \equiv 2\) (mod 6), then there exists an integer \(k\) such that \(a = 6k + 2\). But then \(a = 2(3k + 1)\) and hence, \(a\) is even. Since we assumed that \(a\) is odd, this case is not possible.
    1. Prove that if \(a\) is an odd integer, then \(a\) cannot be congruent to 4 modulo 6.
    2. Prove that if \(a\) is an integer and 3 does not divide \(a\), then \(a\) cannot be congruent to 3 modulo 6.
    3. So if \(a\) is an odd integer that is not a multiple of 3, then \(a\) must be congruent to 1 or 5 modulo 6. Use these two cases to prove the following proposition:
    Answer

    Add texts here. Do not delete this text first.

    Proposition 3.36.

    For each integer \(a\), if \(a\) is an odd integer that is not multiple of 3, then \(a^2 \equiv 1\) (mod 6).

    Exercises for Section 3.5
    1. Complete the details for the proof of Case 3 of Proposition 3.27.
    2. Extending the idea in Exercise (1) of Section 3.4, we can represent three consecutive integers as \(m\), \(m + 1\), and \(m + 2\), where \(m\) is an integer.

      (a) Explain why we can also represent three consecutive integers as \(k - 1\), \(k\), and \(k + 1\), where \(k\) is an integer.
      (b) Explain why Proposition 3.27 proves that the product of any three consecutive integers is divisible by 3.
      (c) Prove that the product of three consecutive integers is divisible by 6.
    3. Prove the symmetric property of congruence stated in Theorem 3.30.
    4. (a) Let \(n \in \mathbb{N}\) and let \(a \in \mathbb{Z}\). Explain why \(n\) divides \(a\) if and only if \(a \equiv 0\) (mod \(n\)).
      (b) Let \(a \in \mathbb{Z}\). Explain why if \(a \not\equiv 0\) (mod 3), then \(a \equiv 1\) (mod 3) or \(a \equiv 2\) (mod 3).
      (c) Is the following proposition true or false? Justify your conclusion.
      For each \(a \in \mathbb{Z}\), \(a \not\equiv 0\) (mod 3) if and only if \(a^2 \equiv 1\) (mod 3).
    5. (a) Use cases based on congruence modulo 3 and properties of congruence to prove that for each integer \(n\), \(n^3 \equiv n\) (mod 3).
      (b) Explain why the result in Part (a) proves that for each integer \(n\), 3 divides \(n^3 - n\). Compare this to the proof of the same result in Proposition 3.27.
    6. Prove that for each natural number \(n\), \(\sqrt{3n + 2}\) is not a natural number.
    7. Prove the following proposition by proving its contrapositive. (Hint: Use case analysis. There are several cases.

      For all integers \(a\) and \(b\), if \(ab \equiv 0\) (mod 3), then \(a \equiv 0\) (mod 3) or \(b \equiv 0\) (mod 3).
    8. (a) Explain why the following proposition is equivalent to the proposition in Exercise (7).
      For all integers \(a\) and \(b\), if \(3 | ab\), then \(3 | a\) or \(3 | b\).
      (b) Prove that for each integer \(a\), if 3 divides \(a^2\), then 3 divides \(a\).
    9. (a) Prove that the real number \(\sqrt 3\) is an irrational number. That is, prove that
      If \(r\) is a positive real number such that \(r^2 = 3\), then \(r\) is irrational.
      (b) Prove that the real number \(\sqrt{12}\) is an irrational number.
    10. (a) Use the result in Proposition 3.33 to help prove that the integer \(m\) = 5, 344, 580, 232, 468, 953, 153 is not a perfect square. Recall that an integer \(n\) is a perfect square provided that there exists an integer \(k\) such that \(n = k^2\). Hint: Use a proof by contradiction.
      (b) Is the integer \(n\) = 782, 456, 231, 189, 002, 288, 438 a perfect square? Justify your conclusion.
    11. (a) Use the result in Proposition 3.33 to help prove that for each integer \(a\), if 5 divides \(a^2\), then 5 divides \(a\).
      (b) Prove that the real number \(\sqrt 5\) is an irrational number.
    12. (a) Prove that for each integer \(a\), if \(a \not\equiv 0\) (mod 7), then \(a^2 \not\equiv 0\) (mod 7).
      (b) Prove that for each integer \(a\), if 7 divides \(a^2\), then 7 divides \(a\).
      (c) Prove that the real number \(\sqrt 7\) is an irrational number.
    13. (a) If an integer has a remainder of 6 when it is divided by 7, is it possible to determine the remainder of the square of that integer when it is divided by 7? If so, determine the remainder and prove that your answer is correct.
      (b) If an integer has a remainder of 11 when it is divided by 12, is it possible to determine the remainder of the square of that integer when it is divided by 12? If so, determine the remainder and prove that your answer is correct.
      (c) Let \(n\) be a natural number greater than 2. If an integer has a remainder of \(n - 1\) when it is divided by \(n\), is it possible to determine the remainder of the square of that integer when it is divided by \(n\)? If so, determine the remainder and prove that your answer is correct.
    14. Let \(n\) be a natural number greater than 4 and let a be an integer that has a remainder of \(n - 2\) when it is divided by \(n\). Make whatever conclusions you can about the remainder of \(a^2\) when it is divided by \(n\). Justify all conclusions.
    15. Is the following proposition true or false? Justify your conclusion with a proof or a counterexample.
      For each natural number \(n\), if 3 does not divide \((n^2 + 2)\), then \(n\) is not a prime number or \(n = 3\).
    16. (a) Is the following proposition true or false? Justify your conclusion with a counterexample or a proof.
      For each integer \(n\), if \(n\) is odd then \(n^2 \equiv 1\) (mod 8).
      (b) Compare this proposition to the proposition in Exercise (7) from Section 3.4. Are these two propositions equivalent? Explain.
      (c) Is the following proposition true or false? Justify your conclusion with a counterexample or a proof.
      For each integer \(n\), if \(n\) is odd and \(n\) is not a multiple of 3, then \(n^2 \equiv 1\) (mod 24).
    17. Prove the following proposition:
      For all integers \(a\) and \(b\), if 3 divides \((a^2 + b^2)\), then 3 divides \(a\) and 3 divides \(b\).
    18. Is the following proposition true or false? Justify your conclusion with a counterexample or a proof.
      For each integer \(a\), 3 divides \(a^3 + 23a\).
    19. Are the following statements true or false? Either prove the statement is true or provide a counterexample to show it is false.

      (a) For all integer \(a\) and \(b\), if \(a \cdot b \equiv 0\) (mod 6), then \(a \equiv 0\) (mod 6) or \(b \equiv 0\) (mod 6).
      (b) For all integer \(a\) and \(b\), if \(a \cdot b \equiv 0\) (mod 8), then \(a \equiv 0\) (mod 8) or \(b \equiv 0\) (mod 8).
      (c) For all integer \(a\) and \(b\), if \(a \cdot b \equiv 1\) (mod 6), then \(a \equiv 1\) (mod 6) or \(b \equiv 1\) (mod 6).
      (d) For all integer \(a\) and \(b\), if \(ab \equiv 7\) (mod 6), then either \(a \equiv 1\) (mod 12) or \(b \equiv 7\) (mod 12).
    20. (a) Determine several pairs of integers \(a\) and \(b\) such that \(a \equiv b\) (mod 5). For each such pair, calculate \(4a + b\), \(3a + 2b\), and \(7a + 3b\). Are each of the resulting integers congruent to 0 modulo 5?
      (b) Prove or disprove the following proposition:
      Let \(m\) and \(n\) be integers such that \((m + n) \equiv 0\) (mod 5) and let \(a,b \in \mathbb{Z}\). If \(a \equiv b\) (mod 5), then \((ma + nb) \equiv 0\) (mod 5).
    21. Evaluation of proofs
      See the instructions for Exercise (19) on page 100 from Section 3.1.
      (a)
      Proposition

      For all integers \(a\) and \(b\), if \((a + 2b) \equiv 0\) (mod 3), then \((2a + b) \equiv 0\) (mod 3).

      Proof

      We assume \(a,b \in \mathbb{Z}\) and \((a + 2b) \equiv 0\) (mod 3). This means that 3 divides \(a + 2b\) and, hence, there exists an integer \(m\) such that \(a + 2b = 3m\). Hence, \(a = 3m - 2b\). For \((2a + b) \equiv 0\) (mod 3), there exists an integer \(x\) such that \(2a + b = 3x\). Hence,

      \begin{eqnarray}
      2(3m - 2b) + b &=& 3x\\
      6m - 3b &=& 3x\\
      3(2m - b) &=& 3x\\
      2m - b &=& x
      \end{eqnarray}

      Since \((2m - b)\) is an integer, this proves that 3 divides \((2a + b)\) and hence, \((2a + b) \equiv 0\) (mod 3)

      (b)

      Proposition.

      For each integer \(m\), 5 divides \((m^5 - m)\).

      Proof

      Let \(m \in \mathbb{Z}\). We will prove that 5 divides \((m^5 - m)\) by proving that divides \((m^5 - m) \equiv 0\) (mod 5). We will use cases.

      For the first case, if \(m \equiv 0\) (mod 5), then \(m^5 \equiv 0\) (mod 5) and, hence, ((m^5 - m) \equiv 0\) (mod 5).

      For the second case, if \(m \equiv 1\) (mod 5), then \(m^5 \equiv 1\) (mod 5) and, hence, ((m^5 - m) \equiv (1 - 1)\) (mod 5), which means that ((m^5 - m) \equiv 0\) (mod 5).

      For the third case, if \(m \equiv 2\) (mod 5), then \(m^5 \equiv 32\) (mod 5) and, hence, ((m^5 - m) \equiv (32 - 2)\) (mod 5), which means that ((m^5 - m) \equiv 0\) (mod 5).

      Explorations and Activities

    22. Using a Contradiction to Prove a Case Is Not Possible. Explore the statements in Parts (a) and (b) by considering several examples where the hypothesis is true.

      (a) If an integer \(a\) is divisible by both 4 and 6, then it divisible by 24.
      (b) If an integer \(a\) is divisible by both 2 and 3, then it divisible by 6.
      (c) What can you conclude from the examples in Part (a)?
      (d) What can you conclude from the examples in Part (b)?

      The proof of the following proposition based on Part (b) uses cases. In this proof, however, we use cases and a proof by contradiction to prove that a certain integer cannot be odd. Hence, it must be even. Complete the proof of the proposition.

      Proposition. Let \(a \in \mathbb{Z}\). If 2 divides a and 3 divides \(a\), then 6 divides \(a\).

      Proof : Let \(a \in \mathbb{Z}\) and assume that 2 divides \(a\) and 3 divides \(a\). We will prove that 6 divides \(a\). Since 3 divides \(a\), there exists an integer \(n\) such that
      \[a = 3n.\]
      The integer \(n\) is either even or it is odd. We will show that it must be even by obtaining a contradiction if it assumed to be odd. So, assume that \(n\) is odd. (Now complete the proof.)
    23. The Last Two Digits of a Large Integer.
      Notice that 7, 381, 272 \(\equiv\) 72 (mod 100) since 7, 381, 272 - 72 = 7, 381, 200, which is divisible by 100. In general, if we start with an integer whose decimal representation has more than two digits and subtract the integer formed by the last two digits, the result will be an integer whose last two digits are 00. This result will be divisible by 100. Hence, any integer with more than 2 digits is congruent modulo 100 to the integer formed by its last two digits.

      (a) Start by squaring both sides of the congruence \(3^4 \equiv 81\) (mod 100) to prove that \(3^8 \equiv 61\) (mod 100) and then prove that \(3^{16} \equiv 21\) (mod 100). What does this tell you about the last two digits in the decimal representation of \(3^{16}\)?
      (b) Use the two congruences in Part (23a) and laws of exponents to determine \(r\) where \(3^{20} \equiv r\) (mod 100) and \(r \in \mathbb{Z}\) with \(0 \le r < 100\). What does this tell you about the last two digits in the decimal representation of \(3^{20}\)?
      (c) Determine the last two digits in the decimal representation of \(3^{400}\).
      (d) Determine the last two digits in the decimal representation of \(4^{804}\).
      Hint: One way is to determine the "mod 100 values", for \(4^2\), \(4^4\), \(4^8\), \(4^{16}\), \(4^{32}\), \(4^{64}\), and so on. Then use these values and laws of exponents to determine \(r\), where \(4^{804} \equiv r\) (mod 100) and \(r \in \mathbb{Z}\) with \(0 \le r < 100\).
      (e) Determine the last two digits in the decimal representation of \(3^{3356}\).
      (f) Determine the last two digits in the decimal representation of \(7^{403}\).
    Answer

    Add texts here. Do not delete this text first.


    This page titled 3.5: The Division Algorithm and Congruence is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Ted Sundstrom (ScholarWorks @Grand Valley State University) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.