🌀 Modular Arithmetic: The World of Congruences and Modulo Operations

When we look at a clock, we unconsciously use one of the most fundamental tools in mathematics. If it is 9:00 now, in 5 hours it will not be 14:00, but 2:00. In fact, we automatically “wrap” the time around a 12-hour cycle. In short, this is the essence of modular arithmetic—a system that deals with remainders.

Ultimately, this field, often called “clock arithmetic,” was formalized by Carl Friedrich Gauss and is a cornerstone of number theory, cryptography, computer science, and many other disciplines.

1. What is Congruence?

To begin, at the heart of modular arithmetic is the concept of congruence. Two integers, \(a\) and \(b\), are called congruent modulo \(m\) if they have the same remainder when divided by \(m\).

Formally, this is written as:
$$a \equiv b \pmod{m}$$
And it is read as “\(a\) is congruent to \(b\) modulo \(m\).”

What does this mean in practice? In other words, this simply means that the difference \((a – b)\) is evenly divisible by \(m\).

Examples of Congruence Modular Arithmetic

• \(17 \equiv 5 \pmod{12}\)
  This is true because \(17 – 5 = 12\), which is divisible by 12.
  Another check: 17 divided by 12 gives a remainder of 5. And 5 divided by 12 gives a remainder of 5. The remainders are the same.
• \(14 \equiv 0 \pmod{7}\)
  Similarly, \(14 – 0 = 14\), which is divisible by 7.
• \(-3 \equiv 7 \pmod{10}\)
  Likewise, \(-3 – 7 = -10\), which is divisible by 10.

Moreover, the number \(m\) is called the modulus. In this system, all numbers that have the same remainder when divided by \(m\) form an equivalence class. For example, modulo 12, the numbers {…, -7, 5, 17, 29, …} all belong to the same class (the remainder class of 5).

2. The “mod” Operation: Taking the Remainder

Closely related, but slightly different, is the modulo operation (often written as \(a \pmod{m}\) or, in programming, as \(a \ \% \ m\)). Essentially, this operation simply finds the remainder of \(a\) when divided by \(m\).

For example, \(17 \pmod{12} = 5\), \(14 \pmod{7} = 0\), and \(7 \pmod{3} = 1\).

Therefore, the relationship is: \(a \equiv b \pmod{m}\) if and only if \(a \pmod{m} = b \pmod{m}\).

3. Modular Arithmetic Operations

However, the most interesting part is that we can perform standard arithmetic operations with congruences: addition, subtraction, and multiplication.
To do this, suppose we know that \(a \equiv b \pmod{m}\) and \(c \equiv d \pmod{m}\).
Then the following properties hold. Namely:

➕ Addition

$$(a + c) \equiv (b + d) \pmod{m}$$

• Example (mod 10):
  • \(12 \equiv 2 \pmod{10}\)
  • \(19 \equiv 9 \pmod{10}\)
  • \(12 + 19 = 31\). And \(31 \pmod{10} = 1\).
  • \(2 + 9 = 11\). And \(11 \pmod{10} = 1\).
  • As a result, \(31 \equiv 11 \pmod{10}\), which is true (both are 1).
• Practical Rule: To find \((a + b) \pmod{m}\), you can find the remainders of \(a\) and \(b\) separately, add them, and then take the remainder of the sum.
      $$(a + b) \pmod{m} = \left( (a \pmod{m}) + (b \pmod{m}) \right) \pmod{m}$$

➖ Subtraction

$$(a – c) \equiv (b – d) \pmod{m}$$

• Example (mod 10):
  • Take the same numbers: \(19 \equiv 9 \pmod{10}\) and \(12 \equiv 2 \pmod{10}\).
  • \(19 – 12 = 7\). And \(7 \pmod{10} = 7\).
  • \(9 – 2 = 7\). And \(7 \pmod{10} = 7\).
  • As you can see, it works!
• The same rule applies:
      $$(a – b) \pmod{m} = \left( (a \pmod{m}) – (b \pmod{m}) \right) \pmod{m}$$
      (This might result in a negative number, but remember that \(-3 \equiv 7 \pmod{10}\))

✖️ Multiplication

$$(a \times c) \equiv (b \times d) \pmod{m}$$

• Example (mod 10):
  • \(12 \equiv 2 \pmod{10}\)
  • \(19 \equiv 9 \pmod{10}\)
  • \(12 \times 19 = 228\). And \(228 \pmod{10} = 8\).
  • \(2 \times 9 = 18\). And \(18 \pmod{10} = 8\).
  • Unsurprisingly, it works!
• And again, the practical rule is:
      $$(a \times b) \pmod{m} = \left( (a \pmod{m}) \times (b \pmod{m}) \right) \pmod{m}$$

💣 What About Division?

This is where things get complicated. Division in modular arithmetic is not always possible in the traditional sense. Instead of “dividing by \(b\),” we look for “multiplying by the inverse of \(b\).”
To clarify, the inverse of \(b\) (denoted \(b^{-1}\)) modulo \(m\) is a number such that:
$$b \times b^{-1} \equiv 1 \pmod{m}$$
However, this inverse (called the modular multiplicative inverse) exists only when \(b\) and \(m\) are coprime (meaning their greatest common divisor is 1).

4. Practical Applications of Modular Arithmetic

Of course, modular arithmetic isn’t just an academic exercise. It forms the basis of our modern digital world. For instance, in cryptography, all asymmetric cryptography (like RSA, which secures your bank transactions) is built on modular operations. It’s difficult to compute \(a^b \pmod{m}\) even knowing \(a\), \(b\), and \(m\), but it’s even harder (virtually impossible) to find \(b\) just from the result. Additionally, in computer science, it’s used for:

• Pseudorandom Number Generators (PRNGs): Many use formulas like \(X_{n+1} = (aX_n + c) \pmod{m}\).
• Hash Tables: Calculating an index in an array is often done using a hash function that takes a value modulo the size of the array.

It is also used for check digits; ISBNs (for books), EANs (barcodes), and bank card numbers use a checksum calculated modulo (often 10 or 11) to instantly detect typing errors. Finally, it’s used with calendars, as calculating the day of the week for any given date is a problem in modular arithmetic (modulo 7).

5. Advanced Techniques & Problem-Solving

Now that we have the basics, let’s look at how to solve common problems involving modular arithmetic, such as division (finding inverses) and solving equations.

🔑 How to Find the Modular Multiplicative Inverse in Modular Arithmetic

As we noted, “division” is just multiplication by a modular inverse. How do we find that inverse?
As a quick recap, the inverse \(a^{-1}\) for \(a\) modulo \(m\) satisfies \(a \cdot a^{-1} \equiv 1 \pmod{m}\). It only exists if \(\text{GCD}(a, m) = 1\).
Specifically, the most common method is the Extended Euclidean Algorithm. This algorithm finds integers \(x\) and \(y\) that satisfy the equation:
$$ax + my = \text{GCD}(a, m)$$
For instance, if \(\text{GCD}(a, m) = 1\), the equation becomes:
$$ax + my = 1$$
Furthermore, if we look at this equation modulo \(m\):
\((ax + my) \equiv 1 \pmod{m}\)
\((ax + 0) \equiv 1 \pmod{m}\)
$$ax \equiv 1 \pmod{m}$$
Therefore, this means the coefficient \(x\) is the modular inverse \(a^{-1}\) we were looking for!

Example: Find \(5^{-1} \pmod{26}\)

1. We need to find \(x\) in the equation \(5x + 26y = 1\).
2. Next, apply the Euclidean Algorithm:
   • \(26 = 5 \times 5 + 1\)
   • \(5 = 5 \times 1 + 0\)
   • The \(\text{GCD}(26, 5) = 1\). The inverse exists.
3. Then, work backward to express 1:
   • From the first line: \(1 = 26 – 5 \times 5\)
4. Rearrange into the form \(ax + my = 1\):
   • \(1 = 5 \times (-5) + 26 \times (1)\)
   • We have \(a=5\), \(x = -5\), \(m=26\), \(y=1\).
5. Finally, find the inverse:
   • The coefficient \(x\) is -5.
   • So, \(5^{-1} \equiv -5 \pmod{26}\).
   • Since we usually want a positive remainder, we add the modulus: \(-5 + 26 = 21\).
   • Answer: \(5^{-1} \equiv 21 \pmod{26}\).

To be sure, check: \(5 \times 21 = 105\). \(105 \div 26 = 4\) with a remainder of 1. (\(105 = 4 \times 26 + 1\)). It works!

⚙️ How to Solve Linear Congruences in Modular Arithmetic

Now that we can “divide,” we can solve equations.
So, what is it?
By definition, a linear congruence is an equation of the form:
$$ax \equiv b \pmod{m}$$
Where \(a\), \(b\), and \(m\) are known, and \(x\) is the unknown.

Method: Multiply by the Inverse

Put simply, if \(\text{GCD}(a, m) = 1\), we can find \(a^{-1}\) and multiply both sides of the equation by it:

\(a^{-1} \cdot (ax) \equiv a^{-1} \cdot b \pmod{m}\)

\((a^{-1} \cdot a) \cdot x \equiv a^{-1} \cdot b \pmod{m}\)

\(1 \cdot x \equiv a^{-1} \cdot b \pmod{m}\)
$$x \equiv a^{-1} \cdot b \pmod{m}$$

Example: Solve \(5x \equiv 3 \pmod{26}\)

1. First, state the equation: \(5x \equiv 3 \pmod{26}\).
2. Next, find the inverse: We need \(5^{-1} \pmod{26}\). From our previous example, we know \(5^{-1} \equiv 21 \pmod{26}\).
3. Then, multiply both sides by 21:
       \(21 \cdot (5x) \equiv 21 \cdot 3 \pmod{26}\)
       \((21 \cdot 5) \cdot x \equiv 63 \pmod{26}\)
4. Now, simplify both sides:
   • Left side: \((21 \cdot 5) = 105 \equiv 1 \pmod{26}\).
   • Right side: \(63 = (2 \times 26) + 11 \equiv 11 \pmod{26}\).
5. Finally, we get the answer:
       \(1 \cdot x \equiv 11 \pmod{26}\)
       $$x \equiv 11 \pmod{26}$$

We can also check this: \(5 \times 11 = 55\). \(55 = (2 \times 26) + 3 \equiv 3 \pmod{26}\). It works!

💡 Common Modular Arithmetic Problems

Lastly, here are a few classic problems that are easily solved using these techniques.

Problem 1: Modular Exponentiation (Fast Powering)

• Problem: Find \(a^b \pmod{m}\) where \(b\) is a very large number (e.g., \(3^{1000} \pmod{7}\)). Directly calculating \(3^{1000}\) is impossible.
• Method: “Exponentiation by Squaring.” We use the multiplication property \((a \cdot b \pmod{m} = ((a \pmod{m}) \cdot (b \pmod{m})) \pmod{m})\) at each step.
• Example: Find \(3^{18} \pmod{10}\)
     
  We won’t multiply \(3 \times 3 \times 3…\) 18 times.
      Instead:
  • \(3^1 \equiv 3 \pmod{10}\)
  • \(3^2 = 3^1 \times 3^1 = 3 \times 3 = 9 \equiv 9 \pmod{10}\)
  • \(3^4 = 3^2 \times 3^2 = 9 \times 9 = 81 \equiv 1 \pmod{10}\)
  • \(3^8 = 3^4 \times 3^4 = 1 \times 1 = 1 \equiv 1 \pmod{10}\)
  • \(3^{16} = 3^8 \times 3^8 = 1 \times 1 = 1 \equiv 1 \pmod{10}\)

      From here, we break down the exponent 18 into powers of two: \(18 = 16 + 2\).
      So, \(3^{18} = 3^{16} \times 3^2\). This gives us the final calculation:
     
  \(3^{18} \pmod{10} \equiv (3^{16} \pmod{10}) \times (3^2 \pmod{10}) \pmod{10}\)
     
  Which simplifies to: \((1 \times 9) \pmod{10}\)
     
  And finally: \(9 \pmod{10}\)
     
  Answer: 9.

Problem 2: Finding the Last Digit

• Problem: Find the last digit of the number \(7^{2025}\).
• Method: The “last digit” is just another name for “the number modulo 10.” We need to find \(7^{2025} \pmod{10}\).
     
  First, we look for a cycle of remainders:
  • \(7^1 \equiv 7 \pmod{10}\)
  • \(7^2 = 49 \equiv 9 \pmod{10}\)
  • \(7^3 = 7^2 \times 7 \equiv 9 \times 7 = 63 \equiv 3 \pmod{10}\)
  • \(7^4 = 7^3 \times 7 \equiv 3 \times 7 = 21 \equiv 1 \pmod{10}\)
  • \(7^5 = 7^4 \times 7 \equiv 1 \times 7 = 7 \pmod{10}\)

      As we can see, the cycle has repeated! The remainders are {7, 9, 3, 1}. The length of the cycle is 4.
  
  Consequently, we need to know where the 2025th power falls in this cycle.
     
  To do this, we take the exponent modulo the cycle length: \(2025 \pmod{4}\).
     
  Since \(2025 = 2024 + 1 = (4 \times 506) + 1\), it follows that \(2025 \equiv 1 \pmod{4}\).
     
  This means we need the first element of the cycle.
     
  Answer: The last digit of \(7^{2025}\) is 7.

Problem 3: Chinese Remainder Theorem in Modular Arithmetic

• Problem: Find a number \(x\) that satisfies multiple congruences at the same time.
     
  For example, we need to find an \(x\) that satisfies \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), and \(x \equiv 2 \pmod{7}\).
• Method: Successive substitution.
  1. First, from the first equation (\(x \equiv 2 \pmod{3}\)), we know \(x\) can be written as:
             \(x = 3k + 2\) (for some integer \(k\)).
  2. Second, substitute this into the second equation:
             \(3k + 2 \equiv 3 \pmod{5}\)
             \(3k \equiv 1 \pmod{5}\)
            
     We need \(3^{-1} \pmod{5}\). By inspection, \(3 \times 2 = 6 \equiv 1 \pmod{5}\). So \(3^{-1} \equiv 2\).
            
     Multiply by 2:
             \(k \equiv 1 \times 2 \pmod{5}\)
             \(k \equiv 2 \pmod{5}\).
            
     This means \(k\) can be written as \(k = 5j + 2\) (for some integer \(j\)).
  3. Third, substitute \(k\) back into our equation for \(x\):
             \(x = 3k + 2 = 3(5j + 2) + 2 = 15j + 6 + 2 = 15j + 8\).
  4. Fourth, substitute this new expression for \(x\) into the third equation:
             \(15j + 8 \equiv 2 \pmod{7}\)
            
     Simplify 15 and 8 modulo 7: \(15 \equiv 1 \pmod{7}\) and \(8 \equiv 1 \pmod{7}\).
             \((1)j + 1 \equiv 2 \pmod{7}\)
             \(j \equiv 1 \pmod{7}\).
            
     This means \(j\) can be written as \(j = 7n + 1\) (for some integer \(n\)).
  5. Finally, find the final expression for \(x\):
             \(x = 15j + 8 = 15(7n + 1) + 8 = 105n + 15 + 8 = 105n + 23\).
• Answer: \(x \equiv 23 \pmod{105}\).
     
  Any number of the form 23, 128, 233, … will satisfy all three conditions.
• Check: We can verify this: \(23 \div 3 = 7\) (rem 2), \(23 \div 5 = 4\) (rem 3), and \(23 \div 7 = 3\) (rem 2). It is correct!

Conclusion

In conclusion, modular arithmetic is an elegant system that replaces the infinite line of integers with a finite “wheel” or cycle. Not only does it simplify complex problems by allowing us to work only with remainders, but it also serves as an unseen but vital mechanism powering our modern technology.