ENT - Residue Classes and Modulus

7-minute read

Introduction

This document introduces the basics of residue classes and the modulus. Residue classes are sometimes referred to as congruence classes or equivalence classes. A residue class is a specific example of an equivalence class.

Division Algorithm

The division algorithm states that $\forall a, b \in \mathbb{Z}$ where $b > 0$ $\exists$ unique $q,r \in \mathbb{Z}$ such that $a = bq + r$ and $0\leq r < b$

The important part we will focus on is $0\leq r < b$ . The remainder $r$ is bounded by $b$.

Lets observe the remainder when we alternate $a$, and keep $b$ the same.

Example

$b=6$

  • $a = 0$ : $0 = 6 \times0 + 0$ ($r=0$)
  • $a = 1$ : $1 = 6 \times0 + 1$ ($r=1$)
  • $a = 2$ : $2 = 6 \times0 + 2$ ($r=2$)
  • $a = 3$ : $3 = 6 \times0 + 3$ ($r=3$)
  • $a = 4$ : $2 = 6 \times0 + 4$ ($r=4$)
  • $a = 5$ : $2 = 6 \times0 + 5$ ($r=5$)
  • $a = 6$ : $6 = 6 \times1 + 0$ ($r=0$)
  • $a = 7$ : $7 = 6 \times1 + 1$ ($r=1$)
  • $a = 8$ : $8 = 6 \times1 + 2$ ($r=2$)
  • $a = 9$ : $9 = 6 \times1 + 3$ ($r=3$)
  • $a = 10$ : $10 = 6 \times1 + 4$ ($r=4$)
  • $a = 11$ : $11 = 6 \times1 + 5$ ($r=5$)
  • $a = 12$ : $12 = 6 \times2 + 0$ ($r=0$)

There seems to be a pattern!

Observe

  • From the division algorithm, indeed we see that the remainder is bounded above by b which is 6.
  • We also note that increasing a by 1 increases the remainder by 1, but due to our first observation, it wraps back around to zero once the remainder gets to b.

We now define a new operator that will essentially be a shorthand version of the division algorithm, when we care about the remainder.

Modulo Operator

Given two integers $a$ and $b$, we define $a \ mod \ b = r$ where $a = bq + r$ and $0\leq r < b$ .

We call b the modulus.

Written: Given two integers a and b, we define a $mod$ b to be the remainder when the division algorithm is applied to a and b.

Observe

  • $a \ mod \ b$ can give the same value for different a’s. Recall the example above; $1\ mod \ 6 = 7\ mod \ 6$ because the remainder was the same on both of those lines. Residue classes capture this equivalence.

Residue class

To define residue classes, you must first have a modulus. ie. You must first fix b, like in the example above.

Okay so b is fixed. Good.

  • Residue classes are sets.
  • Two elements $a_0$ , $a_1$ are in the same set if $a_0 \ mod \ b = a_1 \ mod \ b$. ie two elements belong to the same set, if they leave the same remainder when divided by b.

Lets fix b to be 6.

We denote the residue class which leaves a remainder of $0$ when divided by 6 as $[0]_6$. Note, this is a set; there are other elements that when divided by 6 leave a remainder of $0$. $[0]_6 = \{0,6,12,18,24,30,…\}$

These are just the multiples of 6, we can succinctly write out each residue class for 6 as :

$[r]_6$ = $\{ 6k+r : k,r\in \mathbb{Z}\}$

Indeed, if we fix r to be 0 we get all of the multiples of 6, which do indeed leave a remainder of 0 when divided by 6.

In general the residue class for a modulus b is can be written as :

$[r]_b$ = $\{ bk+r : k,r\in \mathbb{Z}\}$

Note on Syntax

Although there are many elements that can leave a remainder of 6, we usually choose a representative element.

Elaborating:

$[0]_6$ = $[6]_6$. We usually denote 0 as the reduced form or the representative for all numbers that leave a remainder of zero when divided by 6. It is only by convention that this is done, you can choose any representative.

Furthermore, we usually abuse notation and just use the representative number, so instead of seeing a residue class denoted as:

$\mathbb{Z_6} = \{[0]_6,[1]_6,[2]_6,[3]_6,[4]_6,[5]_6\}$

You will see

$\mathbb{Z_6} = \{0,1,2,3,4,5\}$

Note on congruence syntax

Remember we said: $[0]_6 = \{0,6,12,18,24,30,…\}$

From this we can say that $0 \in [0]_6$ and $6 \in [0]_6$ , but there is a more common way to say that $0$ and $6$ belong to the same residue class.

We use the congruence operation for this:

$6 \equiv 0\ mod\ 6$ This tells us that when the modulus is $6$, $0$ and $6$ belong to the same residue class.

$6 \neq 0 \ mod\ 6$ because $0\ mod \ 6$ is the remainder when you divide $0$ by $6$. This is $0$ and $6 \neq 0$

Congruence to Divides

Let’s link back our definition of congruence to our definition of divides.

First suppose, we have two integers a, b and q such that:

$a \equiv b\ mod\ q$

This tells us two things:

$a = k\times q$ + r and $b = l\times q$ + r

ie a and b both leave the same remainder, when divided by q.

Since r is present in both equation, we can use substitution to arrive at:

$a = k\times q + (b - l\times q)$

Now let’s massage the equation:

$a - b = k\times q - l\times q$

$a - b = q(k-l) \implies q|a-b$

So $a \equiv b\ mod\ q \implies q | a-b$

Written: a being congruent to b mod q implies that q is a factor of a minus b.

Example

$4 \equiv 44\ mod\ 20 \implies 20 | 44-4 \implies 20 | 40$

Notes on Prime numbers and Congruence

Lets say that $a \equiv b\ mod\ q$

Again we split it up into two equations:

$a = k\times q$ + r and $b = l\times q$ + r

Now lets impose some restrictions:

We make $gcd(a, q) \neq \ 1 $ and $b = 1$. Since $gcd(q,a) \neq 1$ then either $q|a$ or $a|q$ this means that the remainder will be zero. Our equation now looks like this.

$a = k\times q$ + 0 and $1 = l\times q$ + 0

$a = k\times q$ and $1 = l\times q$

Lets focus on $1 = l\times q$. This is only true, when both $l$ and $q$ are 1 or -1.

When $q \neq \pm 1$, we have no solution!

We immediately have solutions, if we remove the $gcd(a,q) \neq 1$ restriction, therefore:

$a \equiv 1\ mod\ q$ has solutions when a and q are coprime.

Notice that if $a \equiv 1\ mod\ q$ then any multiple which is also coprime with q, will also have solutions.

$10a \equiv 1\ mod\ q$ if 10 is coprime with q.

$qa \equiv 1\ mod\ q$ does not have solutions because qa is a multiple of q. This becomes more intuitive when you realise that qa is in the residue class $[0]_q$ which will always be different from the class $[1]_q$ for all possible values of q.

Why is this important?

Let say that $a\times b \equiv 1\ mod\ q$

If the above equation has a solution, we say that b is the multiplicative inverse of a or a is the multiplicative inverse of b. This notion is used a lot in cryptography!

Example

What is the multiplicative inverse of 10 mod 20 ? It does not exist! Because $gcd(10, 20) \neq 1$.

What is the multiplicative inverse of 10 mod 7 ?

Instead of using $[10]_7$ we use $[3]_7$, as they represent the same elements(all elements which leave a remainder of 3 when divided by 7).

Note that since q = 7 is a prime, the gcd will always equal one unless we use a multiple of 7.

The equation we are trying to solve is now : $3\times k \equiv 1\ mod\ 7$

As emphasized above, we know a solution exists and we immediately know that k is not a multiple of 7.

Because 7 is small, we can check each residue class and see that k = 5 is a solution.

The modulus in this case, which was 7, was small so it was easy to check. But in cryptography for example, our modulus can range from 256 bits to 1024 bits or more, depending on the desired security level.

So how do we find the multiplicative inverse, when the modulus is large?