8.7: Remainder Arithmetic

The Congruence Lemma 8.6.1 says that two numbers are congruent iff their remainders are equal, so we can understand congruences by working out arithmetic with remainders. And if all we want is the remainder modulo \(n\) of a series of additions, multiplications, subtractions applied to some numbers, we can take remainders at every step so that the entire computation only involves number in the range \([0..n)\).

General Principle of Remainder Arithmetic

To find the remainder on division by \(n\) of the result of a series of additions and multiplications, applied to some integers

• replace each integer operand by its remainder on division by \(n\),
• keep each result of an addition or multiplication in the range \([0..n)\) by immediately replacing any result outside that range by its remainder on division by \(n\).

For example, suppose we want to find

\[\label{8.7.1} \text{rem}((44427^{3456789} + 15555858^{5555})403^{6666666}, 36).\]

This looks really daunting if you think about computing these large powers and then taking remainders. For example, the decimal representation of \(44427^{3456789}\) has about 20 million digits, so we certainly don’t want to go that route. But remembering that integer exponents specify a series of multiplications, we follow the General Principle and replace the numbers being multiplied by their remainders. Since \(\text{rem}(44427, 36) = 3\), \(\text{rem}15555858, 36) = 6\), and \(\text{rem}403, 36) = 7\), we find that (\ref{8.7.1}) equals the remainder on division by 36 of

\[\label{8.7.2} (3^{3456789} + 6^{5555}) 7^{6666666}.\]

That’s a little better, but \(3^{3456789}\) has about a million digits in its decimal representation, so we still don’t want to compute that. But let’s look at the remainders of the first few powers of 3:

\[\begin{aligned} \text{rem}(3, 36) &= 3 \\ \text{rem}(3^2, 36) &= 9 \\ \text{rem}(3^3, 36) &= 27 \\ \text{rem}(3^4, 36) &= 9. \end{aligned}\]

We got a repeat of the second step, \(\text{rem}(3^2, 36)\) after just two more steps. This means means that starting at \(3^2\), the sequence of remainders of successive powers of 3 will keep repeating every 2 steps. So a product of an odd number of at least three 3’s will have the same remainder on division by 36 as a product of just three 3’s. Therefore,

\[\nonumber \text{rem}(3^{3456789}, 36) = \text{rem}(3^3, 36) = 27.\]

What a win!

Powers of 6 are even easier because \(\text{rem}(6^2, 36) = 0\), so 0’s keep repeating after the second step. Powers of 7 repeat after six steps, but on the fifth step you get a 1, that is \(\text{rem}(7^6, 36) = 1\), so (\ref{8.7.2}) successively simplifies to be the remainders of the following terms:

\[\begin{aligned} &(3^{3456789} + 6^{5555}) 7^{6666666} \\ &(3^3 + 6^2 \cdot 6^{5553})(7^6)^{1111111} \\ &(3^3 + 0 \cdot 6^{5553})1^{1111111} \\ &= 27 \end{aligned}\]

Notice that it would be a disastrous blunder to replace an exponent by its remainder. The general principle applies to numbers that are operands of plus and times, whereas the exponent is a number that controls how many multiplications to perform. Watch out for this.

The ring \(\mathbb{Z}_n\)

It’s time to be more precise about the general principle and why it works. To begin, let’s introduce the notation \(+n\) for doing an addition and then immediately taking a remainder on division by \(n\), as specified by the general principle; likewise for multiplying:

\[\begin{aligned} i + _n j &::= \text{rem}(i + j, n), \\ i \cdot _n j &::= \text{rem}(ij, n). \end{aligned}\]

Now the General Principle is simply the repeated application of the following lemma.

Lemma 8.7.1.

\[\begin{align} \label{8.7.3} \text{rem}(i + j, n) &= \text{rem}(i, n) + _n \text{rem}(j, n), \\ \label{8.7.4} \text{rem}(ij, n) &= \text{rem}(i, n) + _n \text{rem}(j, n), \end{align}\]

Proof. By Corollary 8.6.3, \(i \equiv \text{rem}(i, n)\) and \(j \equiv \text{rem}(j, n)\), so by the Congruence Lemma 8.6.4

\[\nonumber i + j \equiv \text{rem}(i, n) + \text{rem}(j, n) \pmod n.\]

By Corollary 8.6.3 again, the remainders on each side of this congruence are equal, which immediately gives (\ref{8.7.3}). An identical proof applies to (\ref{8.7.4}). \(\quad \blacksquare\)

The set of integers in the range \([0 . . n)\) together with the operations \(+_n\) and \(\cdot n\) is referred to as \(\mathbb{Z}_{n}\), the ring of integers modulo \(n\). As a consequence of Lemma 8.7.1, the familiar rules of arithmetic hold in \(\mathbb{Z}_{n}\), for example:

\[\nonumber (i \cdot _n j) \cdot _n k=i \cdot _n(j \cdot _n k).\]

These subscript-\(n\)'s on arithmetic operations really clog things up, so instead we'll just write "\((\mathbb{Z}_{n})\)" on the side to get a simpler looking equation:

\[\nonumber (i \cdot j) \cdot k=i \cdot(j \cdot k)\left(\mathbb{Z}_{n}\right)\]

In particular, all of the following equalities⁸ are true in \(\mathbb{Z}_{n}\):

\[\begin{aligned} (i \cdot j) \cdot k &=i \cdot(j \cdot k) & \text { (associativity of } \cdot), \\ (i+j)+k &=i+(j+k) &\text { (associativity of }+), \\ 1 \cdot k &= k & \text{identity for }\cdot), \\ 0+k &= k & \text{(identity for }+), \\
k+(-k) &= 0 & \text{(inverse for }+), \\
i+j &= j+i & \text{(commutativity of } +) \\
i \cdot(j+k) &= (i \cdot j)+(i \cdot k) & \text{(distributivity)}, \\
i \cdot j &= j \cdot i & \text{(commutativity of }\cdot) \end{aligned}\]

Associativity implies the familiar fact that it’s safe to omit the parentheses in products:

\[\nonumber k_1 \cdot k_2 \cdots k_m\]

comes out the same in \(\mathbb{Z}_n\) no matter how it is parenthesized.

The overall theme is that remainder arithmetic is a lot like ordinary arithmetic. But there are a couple of exceptions we’re about to examine.

 

⁸A set with addition and multiplication operations that satisfy these equalities is known as a commutative ring. In addition to \(\mathbb{Z}_n\), the integers, rationals, reals, and polynomials with integer coefficients are all examples of commutative rings. On the other hand, the set \(\{\mathbf{T, F}\}\) of truth values with \(\text{OR}\) for addition and \(\text{AND}\) for multiplication is not a commutative ring because it fails to satisfy one of these equalities. The \(n \times n\) matrices of integers are not a commutative ring because they fail to satisfy another one of these equalities.