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 12-hour 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\bmod 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.\)

The easiest way to understand modular arithmetic is to think of it as finding the remainder of a number upon division by another 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 have a simple way of doing modular arithmetic: first perform the usual arithmetic, and then find the remainder. For example, to find \(123 + 321 \pmod{11}\), we can take

\[123 + 321 = 444\]

and divide it by 11, which gives us

\[123 + 321 \equiv 4\pmod{11}.\]

However, this could get messy when the numbers get larger. One approach that we could take is to first find the remainders of 123 and 321 when divided by 11 (the remainders are both 2), perform the usual arithmetic, and find the remainder again. In this example, since \(123 \equiv 2\pmod{11}\) and \(321 \equiv 2\pmod{11}\), we can conclude that

\[\begin{aligned} 123 + 321 & \equiv 2+2 & \pmod{11} \\ & \equiv 4 & \pmod{11}. \end{aligned}\]

For a positive integer \(n\), the integers \(a\) and \(b\) are congruent \( \bmod\ n\) if their remainders when divided by \(n\) are the same.

\[52 \equiv 24\pmod 7\]

As we can see above, 52 and 24 are congruent (mod 7) because \(52\pmod 7 = 3\) and \(24\pmod 7 = 3.\)

Note that \(=\) is different from \(\equiv.\)

Another way of defining this is that integers \(a\) and \(b\) are congruent \( \bmod\ n\) if their difference \((a - b)\) is an integer multiple of \(n\), that is, if \(\frac{a-b}{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.\)

Properties of addition in modular arithmetic:

1. If \(a+b = c\), then \(a\pmod N+b\pmod N \equiv c \pmod N.\)
2. If \(a\equiv b\pmod N\), then \(a+k \equiv b+k \pmod N\) for any integer \(k.\)
3. If \(a\equiv b\pmod N\) and \(c\equiv d\pmod N\), then \(a+c \equiv b+d \pmod N.\)
4. If \(a \equiv b\pmod N\), then \(-a \equiv -b\pmod N.\)

It is currently 7:00 PM. What time (in AM or PM) 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 wiki, 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\)

Modular multiplication appears in many fields of mathematics and has many far-ranging applications, including cryptography, computer science, and computer algebra.

Properties of multiplication in modular arithmetic:

1. If \( a \cdot b = c\), then \( a\pmod N\cdot b\pmod N \equiv c \pmod{N}\).
2. If \( a \equiv b \pmod{N}\), then \( ka \equiv kb \pmod{N}\) for any integer \( k\).
3. 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} .\ _\square \]

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 \(c-d\) is a multiple of \(N.\) That is,

\[ a-b = k_1N, \quad c-d = k_2N\]

for constants \(k_1\) and \(k_2\). Then

\[ \begin{align} ac - bd &= ac - bd + bc - bc\\ & = c(a-b) + b(c-d)\\ & = 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\)

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\).

We can write \(a\) in the form of \(a = Np + b\), where \(p\) is some integer. Then we have

\[a^{k} = (Np + b)^{k} = \sum_{i = 0}^{k}\binom{k}{i}(Np)^{k-i}b^{i}.\]

Now notice how all the terms of this sum are multiples of \(N\), except the last when \(i = k\). Hence

\[a^{k} \equiv 0 + 0 + \cdots + 0 + b^{k} = b^{k} \pmod{N}.\ _\square\]

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

\[\begin{align} 3^{16} \pmod{4} &\equiv \big(3^2\big)^8 \pmod{4} \\ &\equiv (1)^8 \pmod{4} \\ &\equiv 1 \pmod{4}. \ _\square \end{align}\]

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 \big(7^2\big)^8 \cdot 7 & \pmod{10}\\ & \equiv (49)^8 \cdot 7 & \equiv 9^8 \cdot 7 & \pmod{10} \\ & \equiv \big(9^2\big)^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} &=& \big(2^{10}\big)^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.

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}\).

This property is true because if \( k(a-b)\) is a multiple of \( N\) and \( \gcd(k,N)=1\), then \( N\) must divide \( a-b\), or equivalently, \( a \equiv b \pmod{N}\).

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.\)

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

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y
def modinv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

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 \)

• Chinese Remainder Theorem

• Finding the Last Digit of a Power