Skip to main content

Section 2.1 Using the Definitions of Congruence and Divides

We will consider the following proposition and try to determine if it is true or false.

Proposition.

For all integers \(a\) and \(b\text{,}\) if \(\modulo{a}{5}{8}\) and \(\modulo{b}{6}{8}\text{,}\) then \(\modulo{(a + b)}{3}{8}\text{.}\)

Before we try to prove a proposition, it is a good idea to try some examples for which the hypothesis is true and then determine whether or not the conclusion is true for these examples. The idea is to convince ourselves that this proposition at least appears to be true. On the other hand, if we find an example where the hypothesis is true and the conclusion is false, then we have found a counterexample for the proposition and we would have prove the proposition to be false. The following table summarizes four examples that suggest this proposition is true.

\(a\) \(b\) \(a + b\) Is \(\modulo{a + b}{2}{8}\text{?}\)
5 6 11 Yes, since \(\modulo{11}{3}{8}\)
13 22 35 Yes, since \(\modulo{35}{3}{8}\)
\(-3\) 14 11 Yes, since \(\modulo{11}{3}{8}\)
\(-11\) \(-2\) \(-13\) Yes, since \(\modulo{-13}{3}{8}\)

We will not attempt to construct a proof of this proposition. We will start with the backwards process. Please keep in mind that it is a good idea to write all of this down on paper. We should not try to construct a proof in our heads. Writing h

So we first know that the goal is to prove that \(\modulo{(a + b)}{3}{8}\text{.}\) So a “backwards question” is, “How do we prove \(\modulo{(a + b)}{3}{8}\text{?}\)” We may be able to answer this question in different ways depending on whether or not we have some previously proven results, but we can always use the definition. So an answer to this question is, “We can prove that 8 divides \((a + b) - 3\text{.}\)” We now ask, “How can we prove that 8 divides \((a + b) - 3\text{?}\)” Again, we can use the definition and answer that we can prove that there exists an integer \(k\) such that \((a + b) - 3 = 8k\text{.}\) So here is what we should have written down.

  • \(Q\text{:}\) \(\modulo{(a + b)}{3}{8}\)

  • \(Q1\text{:}\) 8 divides \((a + b) - 3\)

  • \(Q2\text{:}\) There exists and integer \(k\) such that \((a + b) - 3 = 8k\)

The idea is that if we can prove that \(Q2\) is true, then we can conclude that \(Q1\) is true, and then we can conclude that \(Q\) is true. \(Q2\) is a good place to stop the backwards process since it involves proving that something exists and we have an equation with which to work. So we start the forwards process. We start by writing down the assumptions stated in the hypothesis of the proposition and then make conclusions based on these assumptions. While doing this, we look at the items in the backward process and try to find ways to connect the conclusions in the forward process to the backward process. The forward process can be summarized as

  • \(P\text{:}\) \(a\) and \(b\) are integers and \(\modulo{a}{5}{8}\) and \(\modulo{b}{6}{8}\text{.}\)

  • \(P1\text{:}\) 8 divides \(a - 5\) and 8 divides \(b - 6\text{.}\)

  • \(P2\text{:}\) There exists and integer \(m\) such that \(a - 5 = 8m\) and there exists and integer \(n\) such that \(b - 6 = 8n\)

It now seems that there is a way to connect the forward part (\(P2\)) to the backward part \((Q2)\) using the existence of \(m\) and \(n\) (which have been proven to exist) and the equations in \(P2\) and \(Q2\text{.}\)

Solving the two equations in \(P2\) for \(a\) and \(b\text{,}\) we obtain \(a = 8m + 5\) and \(b = 8n + 6\text{.}\) We can now use these in \(Q2\text{.}\)

Important Notes.

  • We used the letter \(k\) in step \(Q2\) and so we could not use that again in the forward process since there is no way of guaranteeing that the same integer produces the equations for the equations in \(Q2\) and \(P2\text{.}\)

  • In the proof, we cannot use the integer represent by \(k\) in \(Q2\) since we have not proven that such an integer exists. The goal is to prove that such an integer exists.

So now we can proceed as followings:

\begin{align*} (a + b) - 3 \amp = (8m + 5) + (8n + 6) - 3\\ \amp = 8m + 8n + 8\\ \amp = 8 (m + n + 3) \end{align*}

Since the integers are closed under addition, we conclude that \(m + n + 3\) is an integer and so the last equation implies that 8 divides \((a + b) - 3\text{.}\) We can now write a proof. The following proof is written according to the writing guidelines in Appendix A.

Proof.

We assume that \(a\) and \(b\) are integers and that \(\modulo{a}{5}{8}\) and \(\modulo{b}{6}{8}\text{.}\) We will prove that \(\modulo{(a + b)}{3}{8}\text{.}\) From the assumptions, we conclude that

\begin{equation*} 8 \text{ divides } (a - 5) \text{ and } 8 \text{ divides } (b - 6) \end{equation*}

So there exist integers \(m\) and \(n\) such that

\begin{equation*} a - 5 = 8m \text{ and } b - 6 = 8n \end{equation*}

Solving these equations for \(a\) and \(b\text{,}\) we obtain \(a = 8m + 5\) and \(b = 8n + 6\text{.}\) We can now substitute for \(a\) and \(b\) in the expression \((a + b) - 3\text{.}\) This gives

\begin{align*} (a + b) - 3 \amp = (8m + 5) + (8n + 6) - 3\\ \amp = 8m + 8n + 8\\ \amp = 8 (m + n + 3) \end{align*}

Since the integers are closed under addition, we conclude that \((m + n + 3)\) is an integer and so the last equation implies that 8 divides \((a + b) - 3\text{.}\) So by the definition of congruece, we can conclude that \(\modulo{(a + b)}{3}{8}\text{.}\) This proves that for all integers \(a\) and \(b\text{,}\) if \(\modulo{(a)}{5}{8}\) and \(\modulo{(b)}{6}{8}\text{,}\) then \(\modulo{(a + b)}{3}{8}\)

Note.

This shows a typical way to construct and write a direct proof of a proposition or theorem. We will not be going into this much detail on the construction process in all of the results proved in this book. In fact, most textbooks do not do this. What they most often show is only the final product as shown in the preceding proof. Do not be fooled that this is the way that proofs are constructed. Constructing a proof often requires trial and error and because of this, it is always a good idea to write down what is being assumed and what it is we are trying to prove. Then be willing to work backwards for what it is to be proved and works forwards from the assumptions. The hard part is often connecting the forward process to the backward process. This becomes extremely difficult if we do not write things down and try to work only in our heads.

We will now consider the following proposition.

If we think about starting a a proof, we would let \(n\) be an integer, assume that 7 divides \(( n^2 - 4 )\) and from this assumption, try to prove that 7 divides \(( n - 2 )\text{.}\) That is, we would assume that there exists an integer \(k\) such that \(n^2 - 4 = 7k\) and try to prove that there exists an integer \(m\) such that \(n - 2 = 7m\text{.}\) From the assumption, we can using factoring and conclude that

\begin{equation*} ( n - 2 )(n + 2 ) = 7k \end{equation*}

There does not seem to be a direct way to prove that there is an integer \(m\) such that \(n - 2 = 7m\text{.}\) So we start looking for examples of integers \(n\) such that 7 divides \(( n^2 - 4 )\) and see if 7 divides \(( n - 2 )\) for these examples. After trying a few examples, we find that for \(n = 0\) and \(n = 5\text{,}\) 7 divides \(( n^2 - 4 )\) . (There are many other such values for \(n\text{.}\)) For \(n = 5\text{,}\) we see that

\begin{equation*} n^2 - 4 = 21 = 7 \cdot 3 \text{ and } n - 2 = 3 \end{equation*}

However, 7 does not divides 3. This shows that for \(n = 5\text{,}\) the hypothesis of Proposition 2.2 is true and the conclusion is false. This is a counterexample for the proposition and proves that Proposition 2.2 is false.

Note.

This is the standard way to prove a conditional statement is false. Find an example (called a counterexample) in which the hypothesis is true and the conclusion is false. Sometimes, even though a proposition is false, we can modify the statement of the proposition and create a new true proposition. We can do this for Proposition 2.2 once we have studied more number theory. There is a theorem from number theory that states:

For each prime number \(p\) and all integers \(a\) and \(b\text{,}\) if \(p\) divides \(ab\text{,}\) then \(p\) divides \(a\) or \(p\) divides \(b\text{.}\)
This result is known as Euclid's Lemma. Using this result, when we get to the part where we conclude that \(( n - 2)( n + 2) = 7k\text{,}\) we can conclude that 7 divides \((n - 2)(n + 2)\) and hence, 7 divides \(n - 2/\) or 7 divides \((n + 2)/\text{.}\) So we would have the following true proposition.

Proposition.

For each integer \(n\text{,}\) if 7 divides \((n^2 - 4 )\) , then 7 divides \((n - 2)\) or 7 divides \(( n + 2 )\text{.}\)