Modular Arithmetic

Modular arithmetic refers to performing arithmetic operations with integers modulo some number n. This creates a cyclic number system from 0 to n-1.

Operations like addition, multiplication, exponentiation are defined to “wrap around” back to 0 after reaching n-1.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Modular exponentiation
int powMod(int base, int exp, int mod) {
  int result = 1;
  while (exp > 0) {
    if ((exp & 1) == 1) {
      result = (result * base) % mod; 
    }
    base = (base * base) % mod;
    exp >>= 1;
  }
  return result;
}

System.out.println(powMod(2, 5, 7)); // 6 

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// Modular multiplicative inverse  
int modInv(int a, int m) {
  a %= m;
  for (int x = 1; x < m; x++) {
    if ((a * x) % m == 1) {
      return x;
    }
  }
  return 1;
}

Python example:

1
2
3
4
5

# Modular addition 
def modAdd(a, b, n):
  return (a % n + b % n) % n

print(modAdd(9, 5, 7)) # 4

Modular arithmetic appears frequently in combinatorics, number theory, cryptography, and computer algebra systems.

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” after reaching a certain value, called the modulus. The notation for modular arithmetic is ( a \mod m ), which represents the remainder when ( a ) is divided by ( m ).

Explain the Code

Java

1
2
3

public static int mod(int a, int m) {
    return ((a % m) + m) % m;
}

In Java, the % operator provides the remainder. But in some cases, it can return a negative number, so the code ensures it’s positive.

C++

1
2
3
4
5
6

#include <iostream>
using namespace std;

int mod(int a, int m) {
    return ((a % m) + m) % m;
}

In C++, just like in Java, the % operator is used for modulus. We also handle negative numbers similarly.

Python

1
2

def mod(a, m):
    return (a % m + m) % m

Python’s % operator is more forgiving with negative numbers but to maintain uniformity across languages, we use the same approach.

This code performs modular arithmetic, taking care of negative numbers to always return a positive result.

The % operator is used twice in the code to ensure that the result is a positive number between 0 and (m-1), inclusive.

1. The first use of %, in (a % m), computes the initial remainder. However, in languages like Java and C++, this could be negative if a is negative.

2. To correct for the negative case, we add m to the initial remainder. This doesn’t affect positive remainders but turns a negative remainder into a positive value.

3. The second use of %, in ((a % m) + m) % m, takes the result and modulos it again by m. This is to handle the cases where adding m resulted in a value greater than or equal to m.

So the double use of % ensures that the result is always in the range [0, m-1].

Let’s consider m = 5 for the modular arithmetic operation ( a \mod 5 ).

Here is a table that shows the effect of the double use of % on some sample values of a:

The columns describe the following:

1. ( a ): The original number.
2. ( a \mod 5 ): The remainder of ( a ) when divided by 5.
3. ( (a \mod 5) + 5 ): Add 5 to the remainder. This turns a negative remainder into a positive one.
4. ( ((a \mod 5) + 5) \mod 5 ): Modulo 5 again to ensure the number is between 0 and ( m-1 ).

By following the values across each row, you can see how the double use of % ensures that you end up with a positive value between 0 and ( m-1 ).