Modular Arithmetic
Modular arithmetic is a system of arithmetic for integers, which considers the remainder. In modular arithmetic, numbers "wrap around" upon reaching a given fixed quantity (this given quantity is known as the modulus) to leave a remainder. Modular arithmetic is often tied to prime numbers, for instance in Wilson's theorem, Lucas's theorem, and Hensel's lemma, and generally appears in fields like cryptography, computer science, and computer algebra.
An intuitive usage of modular arithmetic is with a 12hour clock. If it is 10:00 now, then in 5 hours the clock will show 3:00 instead of 15:00. 3 is the remainder of 15 with a modulus of 12.
A number \(x \pmod{N} \) is the equivalent of asking for the remainder of \(x\) when divided by \(N\). Two integers \(a\) and \(b\) are said to be congruent (or in the same equivalence class) modulo \(N\) if they have the same remainder upon division by \(N\). In such a case, we say that \( a \equiv b \pmod{N}. \)
Contents
Modular Arithmetic as Remainders
The easiest way to understand modular arithmetic is to think of it as finding the remainders of a number. For example, since both \(15\) and \(9\) leave the same remainder \(3\) when divided by \(12,\) we say that
\[ 15 \equiv 9 \pmod{12}. \]
This allows us to a simple way of doing modular arithmetic, by first performing the usual arithmetic, and then finding the remainder. For example, to find \( 123 + 321 \pmod{11} \), we can take
\[ \begin{array} { l l } 123 + 321 & = 444 \\ & \equiv 4 & \pmod{11}. \\ \end{array} \]
However, this could get messy when the numbers get larger. One approach that we could take is to first find the remainder, then perform the usual arithmetic, and then find the remainder again. In this example, since \( 123 \equiv 2 \pmod{11} \) and \( 321 \equiv 2 \pmod{11} \), we can conclude that
\[ \begin{array} {l l} 123 + 321 & \equiv 2 + 2 & \pmod{11} \\ & \equiv 4 & \pmod{11}. \end{array} \]
Congruence
For a positive integer \(n\), the integers \(a\) and \(b\) are congruent \(\pmod{n}\) if their remainders when divided by \(n\) are the same.
\(52 \equiv 24 \pmod{7}\)
52 and 24 are said to be congruent (mod 7) because 52 (mod 7) is 3 and 24 (mod 7) is also 3.
Another way of defining this is that integers \(a\) and \(b\) are congruent (mod n) if their difference \((a  b)\) is an integer multiple of \(n\). That is, if \((ab)/n\) has a remainder of 0.
\(36 \equiv 10\pmod{13}\)
36 and 10 are said to be congruent (mod 13) because their difference \(36  10 = 26\) is an integer multiple of \(n=13.\) That is, \(26=2\times 13.\)
Addition
Properties of addition in modular arithmetic:
 If \(a+b = c\), then \(a + b \equiv c \pmod {N}\).
 If \( a \equiv b \pmod{N}\), then \( a+k \equiv b+k \pmod {N}\) for any integer \( k\).
 If \( a\equiv b \pmod{N}\) and \(c\equiv d \pmod{N}\), then \( a + c \equiv b + d \pmod {N}\).
 If \( a \equiv b \pmod{N} \), then \( a \equiv b \pmod{N} \).
It is currently 7:00 PM. What time will it be in 1000 hours?
Time repeats every 24 hours, so we work modulo 24. Since
\[ 1000 \equiv 16 + (24\times 41) \equiv 16 \pmod{24},\]
the time in 1000 hours is equivalent to the time in 16 hours. Therefore, it will be 11:00 AM in 1000 hours. \(_\square\)
Find the sum of \(31\) and \(148\) in modulo \(24\).
Solution 1:
\(31\) in modulo \(24\) is equivalent to 7. If we use the first modular addition rule stated in this summary, we find that \(31 + 148 \equiv 7 + 148 \equiv 155 \pmod {24}\). 155 in modulo 24 is \(11\). \(_ \square\)Solution 2:
As stated previously, 31 in modulo 24 is 7. Instead of using the first rule, we'll use the second rule. 148 is 4 in modulo 24. So now, all we need to find is 7+4, which is \(11\). \(_ \square\)
Find the remainder when \(123 + 234+ 32+ 56+ 22 + 12 + 78\) is divided by \(3.\)
We know that \(123 \equiv 0 \pmod{3}\), \(234 \equiv 0 \pmod{3}\), \(32 \equiv 2 \pmod{3}\), \(56 \equiv 2 \pmod{3}\), \(22 \equiv 1 \pmod{3}\), \(12 \equiv 0 \pmod{3}\), and \(78 \equiv 0 \pmod{3}\). From property 3, we have
\[123 + 234+ 32+ 56+ 22 + 12 + 78 \equiv 0+0+2+2+1+0+0 \equiv 5 \pmod{3}. \]
Since \(5\) has a remainder of \(2\) when divided by \(3\), so does \(123 + 234+ 32+ 56+ 22 + 12 + 78,\) and thus the answer is \(2\). \(_\square\)
Multiplication
Modular multiplication appears in many fields of mathematics and has many farranging applications, including cryptography, computer science, and computer algebra.
Properties of multiplication in modular arithmetic:
 If \( a \cdot b = c\), then \( a\cdot b \equiv c \pmod{N}\).
 If \( a \equiv b \pmod{N}\), then \( ka \equiv kb \pmod{N}\) for any integer \( k\).
 If \( a \equiv b \pmod{N}\) and \(c \equiv d \pmod{N}\), then \( ac \equiv bd \pmod{N}\).
What is \( (8 \times 16) \pmod{7}\)?
Since \(8 \equiv 1 \pmod{7}\) and \(16 \equiv 2 \pmod{7}\), we have
\[ (8 \times 16) \equiv (1 \times 2) \equiv 2 \pmod{7} . \]
Find the remainder when \(124 \cdot 134 \cdot 23 \cdot 49 \cdot 235 \cdot 13\) is divided by \(3\).
We did a similar problem above, where the signs were all \( + \) instead of \( \times \). In that case, manually adding the numbers up wouldn't take that much time, though the modular arithmetic solution was faster.
In this example, multiplying the numbers would be very tedious. Instead, we use property 3 repeatedly. We know that \(124 \equiv 1\), \(134 \equiv 2\), \(23 \equiv 2\), \(49 \equiv 1\), \(235 \equiv 1\), and \(13 \equiv 1\). Therefore,
\[124 \cdot 134 \cdot 23 \cdot 49 \cdot 235 \cdot 13 \equiv 1 \cdot 2 \cdot 2 \cdot 1 \cdot 1 \cdot 1 \equiv 4 \equiv 1 \pmod{3}, \]
implying the product, upon division by \(3,\) leaves a remainder of \(1.\) \(_\square\)
Prove property 3 of multiplication in modular arithmetic as stated below:
\[ \] If \( a \equiv b \pmod{N} \) and \(c \equiv d \pmod{N}\), then \(ac \equiv bd \pmod{N}\).
By the definition of equivalence, \(a b\) is a multiple of \(N\) and \(cd\) is a multiple of \(N.\) That is,
\[ ab = k_1N, \quad cd = k_2N\]
for constants \(k_1\) and \(k_2\). Then
\[ \begin{align} ac  bd &= ac  bd + bc  bc\\ & = c(ab) + b(cd)\\ & = c (k_1 N ) + b (k_2N)\\ & = (ck_1 + bk_2) N. \end{align}\]
This implies \( ac  bd \) is a multiple of \(N\) and therefore \(ac  bd \equiv 0 \pmod{N}\), or \(ac \equiv bd \pmod{N}\). \(_\square\)
Exponentiation
Since exponentiation is repeated multiplication, we have the following:
Property of Exponentiation in Modular Arithmetic:
If \( a\equiv b\pmod{N}\), then \(a^k \equiv b^k \pmod{N}\) for any positive integer \(k\).
What is \(3^{16} \pmod{4}\)?
We observe that \[3^2 \equiv 9 \equiv 1 \pmod{4}.\] Then by the property of exponentiation, we have \[ 3^{16} \pmod{4} \equiv (3^2)^8 \pmod{4} \equiv (1)^8 \pmod{4} \equiv 1 \pmod{4}. \ _\square\]
In the above example, we do not need to find the exact value of \( 3 ^ {16} \), which is very large
What is the last digit of \( 17^{17}\)?
The last digit of a number is equivalent to the number taken modulo 10. Working modulo 10, we have
\[\begin{array} { l l l l } 17^{17} & \equiv 7^{17} & \equiv (7^2)^8 \cdot 7 & \pmod{10}\\ & \equiv (49)^8 \cdot 7 & \equiv 9^8 \cdot 7 & \pmod{10} \\ & \equiv (9^2)^4 \cdot 7 & \equiv (81)^4 \cdot 7 & \pmod{10} \\ & \equiv 1^4 \cdot 7 & \equiv 7 & \pmod{10}. \ _\square \end{array} \]
Find the last three digits of \(2^{40}.\)
We have
\[\begin{eqnarray*}2^{40} &=& \left(2^{10}\right)^4 \\ &=& 1024^4 \\ &\equiv& 24^4 \\ &\equiv& 576^2 \pmod{1000}.\end{eqnarray*}\]
We can write \(576^2\) as
\[\begin{eqnarray*}(500+76)(500+76) &=& 250000+2\times500\times 76+76\times76 \\ &=& 250000 + 76000 + 5776 \\ &\equiv& 0 + 5776 \\ &\equiv& 776 \pmod{1000}.\end{eqnarray*}\]
Since \(2^{40}\) leaves a remainder of \(776\) when divided by \(1000\), its last three digits are \(776\). \(_\square\)
Find an example of integers \(a, x, y, n, \) where \(x \equiv y \pmod{n}\), but \(a^x \not \equiv a^y \pmod{n}\).
Many combinations of \( a, x, y, n \) will work here. We present the case with \(n = 3, a =2, x = 2\) and \(y = 5\), where we get \(2 \equiv 5 \pmod{3}\), but \(2^2 \equiv 1 \pmod {3} \) while \( 2^5 \equiv 2\pmod{3}\). \(_\square\)
The important takeaway is that the exponentiation property only works on the base. If you want to work with the powers, you will need Euler's theorem.
Division
This is tricky. Consider \( 4 \equiv 8 \pmod{4}\). Note that we cannot simply divide both sides of the equation by 2, since \( 2 \not \equiv 4 \pmod{4}\). This shows that, in general, division is not well defined. As the following property shows, if we add the condition that \( k, N\) are coprime, then division becomes well defined.
Property of division in modular arithmetic:
If \( \gcd(k,N)=1\) and \( ka \equiv kb \pmod{N}\), then \( a \equiv b \pmod{N}\). \(_\square\)
This property is true because if \( k(ab)\) is a multiple of \( N\) and \( \gcd(k,N)=1\), then \( N\) must divide \( ab\), or equivalently, \( a \equiv b \pmod{N}\).
Multiplicative Inverses
The modular inverse of \(a\) in the ring of integers modulo \(m\) is an integer \(x\) such that
\[ax \equiv 1 \pmod{m}.\]
From the Euclidean division algorithm and Bézout's identity, we have the following result about the existence of multiplicative inverses in modular arithmetic:
If \( a\) and \(N\) are integers such that \( \gcd (a, N)=1\), then there exists an integer \( x\) such that \( ax \equiv 1 \pmod{N}\). \( x\) is called the multiplicative inverse of \( a\) modulo \( N.\) \(_\square\)
The following Python code shows how we can calculate the modulo inverse by implementing the extended Euclidean algorithm.
Python Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

Word Problems
Aditya is excited for his birthday party on Saturday, March 2, 2013. He is turning 16 years old. What day of the week was Aditya born?
Details and Assumptions:
 The recent leap years are 2012, 2008, 2004, 2000, 1996, .... If your answer is Monday, type 1. If your answer is Tuesday, type 2, and so on and so forth. If your answer is Sunday, type 7.
Problem Solving  Basic
Problem Solving  Intermediate
Mark Hennings
Is there a positive integer \(n\) for which \( n^7  77 \) is a Fibonacci number?
If \(p\) is a prime of the form \( 7k + 1 \), then there are \( k + 1 \) seventh powers (where the +1 accounts for 0). This gives a fighting chance of the residues being distinct from the Fibonacci residues. So, we try the smallest prime of the form \( 7k+1\), which is 29.
We can check that \(n^7 \equiv 0, 1, 12, 17, 28 \pmod {29}\), which gives us
\[ n^7  77 \equiv 9, 10, 11, 22, 27 \pmod {29}.\]
When looking at the remainder of the Fibonacci numbers taken modulo 29, we obtain the repeating sequence
\[ 1, 1, 2, 3, 5, 8, 13, 21, 5, 26, 2, 28, 1, 0 , \ldots. \]
A quick check shows us that no number appears in both sequences, and thus the answer is no. \(_ \square \)