Congruence
As we discussed in the previous few topics, we defined “modulo” to be an operation that returns the remainder of division.
It is certainly possible for different numbers to have the same remainder when divided by a specific number. For example, \(3\ mod\ 2=5\ mod\ 2=7\ mod\ 2=1\); i.e. \(3,5,7\) all have remainder \(1\) when you divide each by \(2\).
Numbers that all have the same remainder when divided by a specific divisor are given a special classification.
Note that the above definition is equivalent to saying “\(a\) and \(b\) are congruent modulo \(m\) provided that \(a\) and \(b\) have the same remainder when divided by \(m\).”
To sketch why this is true, assume that \(a\equiv b\ (mod\ m)\) and note that by the Quotient Remainder Theorem, we can write \(a=mq+r\) and \(b=mk+r\), noting that \(a\) and \(b\) have the same remainder \(r\). Then
$$\begin{align} a-b&=(mq+r)-(mk+r)\\&=mq+r-mk-r\\&=mq-mk\\&=m(q-k)\end{align}$$
Therefore, since \(a-b\) can be written as the product of the divisor \(m\) and some other integer (in this case \((q-k)\)), it follows that \(m|(a-b)\) by definition of “divides.”
The problems below will help you get accustomed to the definition above.
False
Note \(42\ mod\ 3=0\) and \(4\ mod\ 3=1\). So, \(42\) and \(4\) have different remainders when divided by \(3\), implying that they are not congruent mod \(3\).
Alternatively, using the original definition of congruence, notice \(42-4=38\) and \(3\) does not divide \(38\). So \(42\) and \(4\) are not congruent mod \(3\).
True!
Using the original definition of congruence, note that \(721-521=200\) and \(200\) is divisible by \(2\). Thus, the congruence stated in the problem holds.
Alternatively, notice that \(721\ mod\ 2=1\) and \(521\ mod\ 2=1\). Since \(721\) and \(521\) have the same remainder, they are congruent mod \(2\).
That is, find three integers that all have the same remainder as \(3\) when divided by \(5\).
Note that your numbers may differ from mine.
\(8, 13, 18\).
Any three numbers you choose from the set \(\{…,-12,-7,-2,3, 8,13, 18, 23,…\}\) will work.
First, notice that \(3\ mod\ 5=3\) so \(3\) is its own remainder when divided by \(5\). So we are looking for numbers that have remainder \(3\) when divided by \(5\). Such numbers are multiples of \(5\) plus \(3\). Hence how I got \(8,13,18\) as well as the bigger set at the bottom of the “Possible Solution” box.
\(15, 22, 29\)
Any three numbers in the set \(\{…, -20,-13,-6,1, 8, 15, 22, 29,…\}\), i.e. any multiple of \(7\), plus \(1\).
Note first that \(8\ mod\ 7=1\), so we are looking for integers that have positive remainder \(1\) when divided by \(7\). Such numbers are specifically all multiples of \(7\) plus \(1\). Pick your favorite three.
1.) Find \(3\mathbb{Z}\): the set of all integers congruent to \(0\) (mod \(3\)).
2.) Find \(3\mathbb{Z}+1\): the set of all integers congruent to \(1\) (mod \(3\)).
3.) Find \(3\mathbb{Z}+2\): The set of all integers congruent to \(2\) (mod \(3\)).
4.) Do any pair of the three sets above have anything in common?
5.) What is the result of \((3\mathbb{Z})\cup( 3\mathbb{Z}+1)\cup (3\mathbb{Z}+2)\)?
1.) \(3\mathbb{Z}=\{…,-9,-6,-3,0,3,6,9,…\}\), the set of all integers with remainder \(0\) when divided by \(3\).
2.) \(3\mathbb{Z}+1=\{…,-8, -5, -2, 1, 4, 7, 10,…\}\), the set of all integers with remainder \(1\) when divided by \(3\).
3.) \(3\mathbb{Z}+2=\{…,-7, -4, -1, 2, 5, 8, 11, …\}\), the set of all integers with remainder \(2\) when divided by \(3\).
4.) Nope! They are all, what is called, pairwise disjoint.
5.) \(\mathbb{Z}\), i.e. all integers.
The three sets separate (or partition) the integers. Each set corresponds to a specific remainder obtained from division by \(3\). Since there are only three possible remainders when dividing any number by \(3\), there are therefore only three possible sets that a number could land in. If you were dividing by \(5\), you’d have five different sets that partition the integers; division by \(21\) would result in a \(21\)-set partition of the integers.