Modular Arithmetic

What is Modular Arithmetic?

This is an important concept in many aspects of computer science, namely cryptography and error correction among many others.

Key Ideas

Modular Equivalence: If you're looking at a clock and it becomes 25:00, you know it's actually the same as 1:00. Even if they're technically not the same number, they can be treated the same way.

Arithmetic

Addition

Multiplication

Division and Inverses

Algorithms

Now, let's explore three famous algorithms for computing useful information using modular arithmetic: Euclid's Algorithm for GCD and inverses, the Chinese Remainder Theorem, and Fermat's Little Theorem.

Euclid's Algorithm

  • Base Case: If y is 0, then any value for x is the GCD since everything can divide 0 to get 0.

  • Inductive Case: Proof of the GCD Mod Corollary.

For an example of a computation, check out the Extended Algorithm section below (the computation is extremely similar).

Using Euclid's Extended Algorithm for Inverses

Great! We got the GCD. So what?

Remember that if the GCD of x and m is 1, then there is an inverse of x. In more concrete terms, we can state Euclid's Extended GCD Theorem (Bezout's Theorem) as such:

The process can be tedious to compute by hand, but here's a nice video that walks through that process:

The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) guarantees existence and uniqueness of a solution to a system of modular congruences. More formally stated:

Formal Statement of CRT:

Alternative Statement of CRT:

Uniqueness of CRT Solution

Computation

Fermat's Little Theorem

The Formal Definition

An Alternative Definition

For an application of Fermat's Little Theorem, head over to RSA Cryptography!

Last updated