CS70 Guide
  • This site is now deprecated
  • LaTeX Reference
  • Discrete Math
    • Overview
    • Propositional Logic
    • Proofs
    • Stable Matching
    • Graphs
    • Modular Arithmetic
    • RSA Cryptography
    • Polynomials
    • Countability
    • Computability
  • Probability
    • Overview
    • Counting
    • Discrete Probability
    • Hashing and the Union Bound
    • Expectation and Variance
    • Concentration Inequalities
    • Continuous Probability
    • Markov Chains
    • The Beta Family
    • The Gamma Family
    • Conditional Expectation and Variance
Powered by GitBook
On this page
  • What is Modular Arithmetic?
  • Key Ideas
  • Arithmetic
  • Addition
  • Multiplication
  • Division and Inverses
  • Algorithms
  • Euclid's Algorithm
  • Using Euclid's Extended Algorithm for Inverses
  • The Chinese Remainder Theorem
  • Fermat's Little Theorem

Was this helpful?

  1. Discrete Math

Modular Arithmetic

PreviousGraphsNextRSA Cryptography

Last updated 2 years ago

Was this helpful?

What is Modular Arithmetic?

Modular arithmetic is "clock math" - that is, when numbers wrap around back to 0 if they get too big. You could think about it like a remainder: 21(mod10)21 \pmod{10}21(mod10) for example can be read as "what is the remainder of 21 when it is divided by 10?" (it's 1, by the way.)

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

Key Ideas

If d divides x and d divides y, then d divides (y-x). d∣x,d∣y  ⟹  d∣(y−x)d \mid x, d \mid y \implies d \mid (y-x)d∣x,d∣y⟹d∣(y−x) (Reminder: a∣b  ⟺  (∃q∈Z)(a=qb)a \mid b \iff (\exists q \in \mathbb{Z})(a = qb)a∣b⟺(∃q∈Z)(a=qb))

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.

  • More formally: x is congruent to y modulo m: x≡y(modm)x \equiv y \pmod{m}x≡y(modm)****

Important Notation Distinction: x(modm)x \pmod{m}x(modm) is the class of numbers that follow the mod rule mmm. It can be used to write equivalences (10≡21(mod11)10 \equiv 21 \pmod{11}10≡21(mod11)). However, mod  (x,m)\mod(x, m)mod(x,m)is just a number (the remainder when dividing x by m). mod  (x,m)=x−⌊xy⌋⋅y\mod(x,m) = x - \lfloor{\frac{x}{y}}\rfloor \cdot ymod(x,m)=x−⌊yx​⌋⋅y

Greatest Common Denominator (GCD Mod Corollary): Modular arithmetic can be used to identify an important property of the GCD, which is that GCD(x,y)=GCD(xmod  y,y)GCD(x,y) = GCD(x \mod y, y)GCD(x,y)=GCD(xmody,y).

Arithmetic

Addition

Given that a≡b(modm)a \equiv b \pmod{m}a≡b(modm), a+c≡b+c(modm)a+c \equiv b+c \pmod{m}a+c≡b+c(modm). This result shouldn't be too surprising, and suggests that adding a constant value to both sides won't change the congruence, just like any other equation.

Multiplication

Multiplication works pretty much how you'd expect it to work after seeing how addition works. Formally defined, if a≡b(modm)a \equiv b \pmod{m}a≡b(modm), then ka=kb(modm)ka = kb \pmod{m}ka=kb(modm). Intuitively, this means that if you want to multiply a big number, you can take the mod of the big number before multiplying it, and that will be equivalent to multiplying before taking the mod.

As an example, let's try to figure out what day it is in 8 years. We know that there will be 2 leap years with 366 days each, and 6 normal years with 365 days each. We don't really feel like computing (365⋅6)+(366⋅2)(mod7)(365 \cdot 6) + (366 \cdot 2) \pmod{7}(365⋅6)+(366⋅2)(mod7), so we can instead take the mod of 365 and 366 first. This yields the much simpler expression (1⋅6)+(2⋅2)(mod7)≡1(1 \cdot 6) + (2 \cdot 2) \pmod{7} \equiv 1(1⋅6)+(2⋅2)(mod7)≡1. Therefore, the day in 8 years will be one day after today.

Division and Inverses

In normal number spaces, the multiplicative inverse of x is a y such that xy=1xy = 1xy=1. This concept still applies to modular arithmetic!

If we have x(modm)x \pmod{m}x(modm), then the multiplicative inverse is defined as a number y such that xy=1(modm)xy = 1 \pmod{m}xy=1(modm).

For example, let's take a look at 4x=5(mod7)4x = 5 \pmod{7}4x=5(mod7). We can multiply both sides by 2 in order to get 8x=10(mod7)8x = 10 \pmod{7}8x=10(mod7). At this point, we can use the (mod7)\pmod{7}(mod7)to reduce the 8 into a 1 and the 10 into a 3, resulting in x=3(mod7)x = 3 \pmod{7}x=3(mod7).

There are some values where it's impossible to get an equivalence into the form 1(modm)1 \pmod{m}1(modm). This usually happens when there is a common factor (like 8x≡y(mod12)8x \equiv y \pmod{12}8x≡y(mod12)). In other words, if the greatest common divisor of x and m is 1, then x has a multiplicative inverse modulo m. (x is relatively prime to y).

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

Euclid's Algorithm is a recursive procedure for calculating the greatest common denominator. Remember that GCD(x,y)=GCD(xmod  y,y)GCD(x,y) = GCD(x \mod y, y)GCD(x,y)=GCD(xmody,y) by the GCD Mod Corollary. We can prove that this works using induction:

  • 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.

This is a rather efficient algorithm: at every iteration, the value of x and y decrease dramatically- at least by a factor of 2. This makes it θ(log⁡2(x))\theta(\log_2(x))θ(log2​(x))(in other words, we need one division for each bit that is needed to represent xxx).

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:

ax+by=gcd(x,y)ax + by = gcd(x,y)ax+by=gcd(x,y)

In other words, the GCD can be written as a scalar multiple of x and y. Since we remember that the definition of the inverse is that ax+by=1ax + by = 1ax+by=1for some integers a and b, Euclid's Extended Theorem checks out for showing that the inverse exists if the GCD is 1.

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:

There is a unique solution x(modmn)x \pmod{mn}x(modmn)such that x=a(modm)x = a \pmod{m}x=a(modm), x=b(modn)x = b \pmod{n}x=b(modn), and gcd(m,n)=1gcd(m,n) = 1gcd(m,n)=1. Here are a few ways to word it (see which one clicks better):

Formal Statement of CRT:

Let n1⋯nkn_1 \cdots n_kn1​⋯nk​be positive coprime integers. (Any two of them must be relatively prime.) Then, for any combination of integers a1⋯aka_1 \cdots a_ka1​⋯ak​, a unique x exists such that x≡aimod  nix \equiv a_i \mod n_ix≡ai​modni​for all 0<i≤k0 < i \le k0<i≤k.

Alternative Statement of CRT:

Let n1,…nkn_1, \ldots n_kn1​,…nk​ be pairwise co-prime, i.e. nin_ini​ and njn_jnj​ are co-prime for all i≠ji \neq ji=j. The Chinese Remainder Theorem (CRT) tells us that there exist solutions to the following system of congruences:

x≡a1(modn1)x≡a2(modn2)⋮x≡ak(modnk)\begin{align} x &\equiv a_1 \pmod{n_1} \tag{1} \\ x &\equiv a_2 \pmod{n_2} \tag{2} \\ &\vdots \tag{$\vdots$} \\ x &\equiv a_k \pmod{n_k} \tag{$k$} \end{align}xxx​≡a1​(modn1​)≡a2​(modn2​)⋮≡ak​(modnk​)​(1)(2)(⋮)(k)​

Uniqueness of CRT Solution

Not only do we know that there is a unique solution xxx, but we can actually write out its exact value! Here it is:

x=∑i=1kaibi(modN)x = \sum_{i=1}^k a_i b_i \pmod{N}x=i=1∑k​ai​bi​(modN)

In this sum, bi=(Nni)⋅(Nni)−1mod  ni)b_i = (\frac{N}{n_i}) \cdot (\frac{N}{n_i})^{-1} \mod n_i)bi​=(ni​N​)⋅(ni​N​)−1modni​) , and NNNis the product of all primes n1,⋯nkn_1, \cdots n_kn1​,⋯nk​. This sum is congruent to aimod  nia_i \mod n_iai​modni​for all valid values of iii.

Computation

The Chinese Remainder Theorem often ties well together with the Extended Euclidean Algorithm, since we would need to find lots of inverse mods for each bib_ibi​. Also like the Extended Euclidean Algorithm, it's very hard to demonstrate the computation on a static webpage so here's another good video walkthrough!

Fermat's Little Theorem

The Formal Definition

For prime ppp and an integer a∈{1,2,⋯ ,p−1}a \in \{1, 2, \cdots, p - 1\}a∈{1,2,⋯,p−1}, ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp).

An Alternative Definition

If we multiply both sides by aaa, we can actually drop the restriction to aaa and allow it to be any integer. This version is sometimes more useful than the normal definition:

For prime ppp and any integer aaa, ap≡a(modp)a^p \equiv a \pmod{p}ap≡a(modp).

Fermat's Little Theorem (not to be confused with ) makes the observation that exponentiation is periodic when modulo is done by a prime number. This makes it reasonable to compute obscenely large numbers, like 2655352^{65535}265535, when in a mod space.

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

cryptography
error correction
Fermat's Last Theorem
RSA Cryptography