Modular Arithmetic

Modular Arithmetic is another important concept in the field of computer science. For example, we use modular arithmetic to manage the problem of overflow in data types. To fully understand modular arithmetic, we'll define a relation on the set of integers that is compatible with operations addition, subtraction and multiplication. The relation can be defined as,

The number n is defined as the modulus of congruence. The congruence relation can be written as,

b need not be the remainder of the division of a by n. More precisely, what the above statement asserts is that a and b have the same remainder when divide by n. That is,

Subtracting both the equations,

For example,

This asserts that both 38 and 14 give us the same remainder when divided by 12. Now that we have defined what the relation is, let's define some of the important properties of this relation.

• Reflexivity :
• Symmetry :
• Transitivity :

Consider and and , then:

• 
• 
• 
• 
• 
• Modular Exponentiation , you may find the derivation here.

Modular Inverse

What is a modular inverse?

In modular arithmetic we do not have a division operation. However, we do have modular inverses.

• The modular inverse of A (mod C) is A^-1
• (A * A^-1) ≡ 1 (mod C) or equivalently (A * A^-1) mod C = 1
• Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (mod C)

How to find the modular inverse?

A naive method of finding a modular inverse for A (mod C) is:

step 1. Calculate A * B mod C for B values 0 through C-1

step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1

Note that the term B mod C can only have an integer value 0 through C-1, so testing larger values for B is redundant.

Check out the implementation here

A better method would be to use Fermat's little theorem

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number a^p – a is an integer multiple of p.

We can use this theorem to calculate the modular inverse,

a^(m-1) ≡ 1 (mod m) 

If we multiply both sides with a^(-1), we get 

a^(-1) ≡ a^(m-2) (mod m) 

Check out the implementation here