In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
Let's use the hours of a clock as an example, except we will start with 0 instead of 12 on top. Starting at noon, the hour hand goes in the order:
\[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, \ldots \]
You can see the numbers continue to "wrap around" every 12 count. We called this count in modulo 12. In modulo 3, we "wrap around" every 3 count
\[ 1, 2, 0, 1, 2, 0 \ldots \]
All integers can be expressed as \( 0, 1\), or \(2 \) in modulo 3, we give these set of integers that can be represented with \( 0, 1\), or \(2 \) in modulo 3 the name residue classes. In general, for any natural number n, the module n residues are the integers that are whole numbers less than n: meaning you can represented from 0 to \(n-1\)
| We say that \(a\) is the modulo-\(m\) residue of \(n\) when \(n \equiv a \pmod{m},\) and \(0 \leq a <m\). |
We saw above that all of the integers can be represented by one of the modulo 3 residues. However, multiple integers can be represented as the same residue.
For example, if we found 4 in modulo 3, we count four residues in order \(0, 1, 2, 0\). So 4 is represented by the residue 0 in modulo 3.
Now 7 in modulo 3, we count seven residues in order \(0, 1, 2, 0, 1, 2, 0\). So 7 is also represented by the residue 0 in modulo 3.
So we say that 0, 4, and 7 are congruent in modulo 3.
\[1 \equiv 4 \equiv 7 \pmod{3} \]
The \( \pmod{3} \) tells us that we are working with the integers in modulo 3. Notice that the difference between congruent numbers in modulo 3 is also 3.
|
Two integers \(a\) and \(b\) are congruent in modulo \(n\) when \(a-b\) is a multiple of \(n\). In other words, \(a \equiv b \pmod{n} \) when \(\frac{a-b}{n}\) is an integer. Otherwise, \(a \not \equiv b \pmod{n}\), which means that \(a\) and \(b\) are not congruent in modulo \(n\). |
Find the following residues in the stated modulo.
1. 1\(5 \pmod{4}\)
One method is to count 15 residues in modulo 4.
\[1,2,3,0,1,2,3,0,1,2,3,0,1,2,3\]
Thus, \(15\equiv 3 \pmod{4}\) or 3 is the residue of 15 in modulo 4. However, this can become tedious as the numbers increase in size.
A shorter method is to find the remainder using long division. For example, \(15 \div 4 = 3 R3\). Which means 15 wraps around 3 times and has a remainder of 3. Thus, we only have to count 3 residues in modulo 3.
2. \(82 \pmod{11} \)
\(82 \div 11 = 7 R5\). Thus, the remainder 5 means you only have to count 5 residues in modulo 11, so \(82 \equiv 5\pmod{11} \). This also means that \(11 \times 7 +5 = 82\).
3. \(-17 \pmod{10} \)
For negative integers, when you perform the division \(-17 \div 10 = -1 R-7\), the remainder is -7. However, we know that the reside for 10 must be one of the numbers \(1,2,3,4,5,6,7,8,9,0\). Thus, we must work out the division such that the remainder is positive.
\[-17 \div 10 = -2 R3\]
Above when we increase the quotient by 1 to 2, it results in a positive remainder. This also means that \(-2 \times 10 + 3 = 17\).
\(\therefore -17 \equiv 3 \pmod{10} \)
4. \(-73 \pmod{7} \)
\(-73 \div 7 = -10 R-3\) or \(= -11 R4\). Since we want the positive remainder.
\[-73 \equiv 4 \pmod{7}\]
5. \(907,342 \pmod{23} \)
How do we find the remainder of a really big number?
You can first use your calculator to find \(907,342 \div 23 = 39,449.65217\)
What is important is the value before the decimal 39,449
Now to find the remainder \(907,342 - 39,449 \times 23 = 15 \)
\( \therefore 907,342 \pmod{23} \equiv 15 \pmod{23} \)
