Modular Arithmetic Part 2

Continuing Where We Left Off

On this page we will discuss some theorems and topics that are slightly more advanced and would likely scare 👻 anyone away.

Remember that equivalence $\mod n$ is literally an equivalence relation, that means we can actually create equivalence classes of items that are all equivalent to each other. As a mini refresher, lets do the following example

Example: Write all equivalence classes of the integers modulo $5$ , which is the quotient set of the integers $\mod 5$

Let’s write out the quotient set starting with $[0]$ which is all the items equivilent to $0 \mod n$ . This is $[0] = {0, 5, - 5, 10, - 10, 15, \dots}$ and we can do the same thing with all the other integers $\begin{aligned} [1] & = {1, 6, - 4, 11, - 9, 16, \dots} \\ [2] & = {2, 7, - 3, 12, - 8, 17, \dots} \\ [3] & = {3, 8, - 2, 13, - 7, 18, \dots} \\ [4] & = {4, 9, - 1, 14, - 6, 19, \dots} . \end{aligned}$

This is all possible equivalence classes, which gives us that our quotient set is ${[0], [1], [2], [3], [4]}$ . Notice that, even though we could have picked any item of the set, for all the representatives of our equivalence classes, I selected the smallest non-negative item. In order to explain why this is meaningful lets define some terminology. Normally when we say that $26 \equiv 1 \mod 5$ we think of $1$ as the remainder from division, which is true. However, there is nothing saying that the remainder needs to be smaller than $5$ similarly we have $26 \equiv 11 \mod 5 ⟹ 26 = 3 \cdot 5 + 11$ whereas in this case $11$ is still a remainder, just not the smallest possible remainder that we can have. In fact there is a term for this remainder¹

Definition: Given some value $k$ , if we have that $k \equiv a \mod n$ then we say that $a$ is a residue of $k$ $\mod n$ . If $0 \leq a < n$ then we say that $a$ is the least residue of $k$ .

So in our prior example when $k = 26$ and $n = 5$ we have that $11$ is a residue and $1$ is the least residue. In fact, $26$ is actually a residue of itself! Notice that all residues are equivalent and are in the same equivalence class, and similarly we have that items in different equivalence classes are not equal; this all follows from equivalence class properties and partitions.

Definition: The quotient set of all equivalence classes $\mod n$ is called a complete system of incongruent residues, and is notated as $Z / n Z = {[0], [1], \dots, [n - 1]} .$ Often people will leave out the square brackets and only include the least residue, and in the notation often leave out the first $Z$ writing $n Z = {0, 1, \dots, n - 1} .$

So from our previous example we would have that $5 Z = {0, 1, 2, 3, 4}$ which is a brief way to write the subsets of integers.

This might seem like a pretty theoretical way of looking at things, but surprisingly modular arithmetic proofs can include the usage of sets of residue classes. Lets prove a small lemma that will provide us some help later.

Lemma: If $[x], [y]$ are two distinct residue classes $\mod n$ , and $gcd (k, n) = 1$ , then $\cdot [k x] \neq [k y]$

Before we prove this what is this saying. We are saying that if you have a number that is coprime to $n$ and then multiply the items of two different equivalence classes by said number $k$ , then those two classes will still be different to each other (although they may or may not be the same class as before). We can see in our $5 Z$ example that $[0] \neq [4]$ . Since $gcd (5, 7) = 1$ we know that $[7 \cdot 0] \neq [7 \cdot 4]$ which is $[0] \neq [3]$ ². Now let us prove this

Proof

Let

a \in [x]

and

b \in [y]

. We know that

a ≢ b \mod n ⟹ n ∤ a - b .

As such since

gcd (n, k) = 1

we know that

n ∤ k (a - b) ⟹ n ∤ k a - k b ⟹ k a ≢ k b \mod n

Since $k a ≢ k b$ they cannot be in the same equivalence class which means the two classes must be distinct.
Q.E.D.

Corollary: If $gcd (k, n) = 1$ and $Z / n Z = {[a_{1}], [a_{2}], \dots, [a_{n}]},$ where $a_{j}$ may not necessarily be the least residue, then $Z / n Z = {[k a_{1}], [k a_{2}], \dots, [k a_{n}]} .$ This means that the function $f : Z / n Z \to Z / n Z$ with $f ([x]) = [k x]$ is bijective

This theorem is actually insanely easy to prove based on the previous lemma we have. However the hardest part is saying what this theorem is actually doing. Pretty much just take all the equivalence classes of the quotient set, and if you multiply by a number prime to $n$ then you will still have all items of your quotient set. For $n = 5$ and $k = 7$ then $\begin{aligned} Z / 5 Z & = {[0], [1], [2], [3], [4]} \\ Z / 5 Z & = {[7 \cdot 0], [7 \cdot 1], [7 \cdot 2], [7 \cdot 3], [7 \cdot 4]} \\ Z / 5 Z & = {[0], [7], [14], [21], [28]} \\ Z / 5 Z & = {[0], [2], [4], [1], [3]} . \end{aligned}$

Prime Residues

Getting all the integers mod some number is cool, but sometimes its useful to work with a specific subset of those integers. There are often certain residues that have special properties that make them desireable to study in bulk. To avoid beating around the bush any longer, we will observe the idea of all residues that are relatively prime to $n$ . Let us consider $Z / 6 Z = {[0], [1], [2], [3], [4], [5]} .$ We will define the set $R_{6}$ to be the classes of all values relatively prime to $6$ , so $R_{6} = {[1], [5]} .$ All items inside of these classes are also coprime to $n$ by definition since all items in the set are equivalent to each other, none of which share a common factor with $n$ . Also notice that $[0] \notin R_{6}$ , which might seem weird, but observing other members of the class it makes sense. $6 \in [0]$ and $gcd (6, 6) \neq 1$ . In reality $gcd (0, 6) = 6$ as $\frac{0}{6}$ has no remainder.

Also, $1$ by definition is relatively prime to every number as $gcd (1, n) = 1$ which is the definition of relatively prime. So $[1]$ will always be an element. Similarly, we know³ that $gcd (n - 1, n) = 1$ always, so $[n - 1]$ will also be included in $R_{n}$ . Lets provide two more examples, however for the sake of brevity I will not write the brackets for equivalence classes, but remember that they are $\begin{aligned} R_{5} & = {1, 2, 3, 4} \\ R_{14} & = {1, 3, 5, 9, 11, 13} \end{aligned}$

Now I will define the term that we are using here

Definition: The complete system of residues prime to $n$ , $R_{n} \subset Z / n Z$ is the set of all equivalence classes who’s members are coprime to $n$ . In set notation $R_{n} = {[x] | [x] \in Z / n Z and gcd (x, n) = 1} .$

Similar to with the normal system of residues, we have the following theorem about multiplying another relatively prime item

Lemma: Let $[x], [y] \in R_{n}$ be two different prime residue classes, and let $gcd (k, n) = 1$ . Then $[k x], [k y] \in R_{n}$ are also prime residue classes, and $[k x] \neq [k y]$

This is actually the same exact theorem as before, with just a minor additional caveat that if you multiply $[k x]$ then the classes will still be prime residue classes and won’t (somehow) start sharing common factors.

Proof

By the previous theorem we already know that

[k x] \neq [k y]

. Now we will show that multiplying

[k x]

will keep it as a prime residue class. Choose some

a \in [x]

, we know that

gcd (a, n) = 1 = gcd (k, n)

. This is enough to see that

gcd (k x, n) = 1

as the product will also share no common factors as

n

by the definition of

gcd

Q.E.D.

So if we were to multiply all the classes in $R_{14}$ by $3$ we would have. $\begin{aligned} R_{14} & = {1, 3, 5, 9, 11, 13} \\ R_{14} & = {3 \cdot 1, 3 \cdot 3, 3 \cdot 5, 3 \cdot 9, 3 \cdot 11, 3 \cdot 13} \\ R_{14} & = {3, 9, 15, 27, 33, 39} \\ R_{14} & = {3, 9, 1, 13, 5, 11} \end{aligned}$ which is correct!

We can even get the same corollary

Corollary: If $gcd (k, n) = 1$ and $R_{n} = {[a_{1}], [a_{2}], \dots, [a_{i}]},$ where $a_{j}$ may not necessarily be the least residue, then $R_{n} = {[k a_{1}], [k a_{2}], \dots, [k a_{i}]} .$ This means that the function $f : R_{n} \to R_{n}$ with $f ([x]) = [k x]$ is bijective.

This is also very straightforward using the pigeonhole principle so I will leave it at that.

Practice Problems

Example: Write out $4$ residues of $29 \mod 13$ , including the least residue

Example: Write out the residues prime to $36$

Of course it can’t just be remainder that would be too easy obviously ↩︎
Note that we are doing math on the representative for the sake of brevity, but this can be proven rigorously using mod math ↩︎
Via a practice problem on the GCD Intro Page ↩︎