Modular Arithmetic

4. Modular Arithmetic#

4.1. Congruences#

Congruences are very important in Number Theory in general, and will play a big role in many of our applications in cryptography.

Definition 4.1

Let \(a\), \(b\), and \(m\) be integers, with \(m > 1\). We say that \(a\) is congruent to \(b\) modulo \(m\) if \(m \mid (a - b)\). We can denote it by:

\[a \equiv b \pmod{m}.\]

In this case, \(m\) is called the modulus.

So, it is easy to check if numbers are congruent: it is just a question about divisibility.

Examples:

  1. Is \(43\) congruent \(11\) modulo \(8\)? We just check if \(8\) divides \(43-11 = 32\). Since it does, the answer is yes:

\[43 \equiv 11 \pmod{8}.\]

  1. Is \(-21\) congruent to \(50\) modulo \(11\)? We just check if \(11\) divides \(-21 - 50 = -71\). Since it doesn’t, the answer is no:

\[-21 \not\equiv 50 \pmod{11}.\]

  1. Is \(2{,}694{,}540\) congruent to \(412{,}004{,}939\) modulo \(3{,}544\)? Well, this is hard to do by hand, but easy with Sage:

a, b, m =  2694540, 412004939, 3544
(a - b) % m == 0

False

So, no!

Here are some important remarks about congruences:

Remark

  1. We have that \(a \equiv b \pmod{m}\) if, and only if, we have that \(a = b + km\) for some integer \(k\).

    (Proof: Since \(a-b\) is divisible by \(m\), it is equal to \(km\) for some integer \(k\).)

  2. We always have \(a \equiv a \pmod{m}\).

    (Proof: Any integer \(m\) divides \(0 = a - a\).)

  3. If \(a \equiv b \pmod{m}\), then \(b \equiv a \pmod{m}\).

    (Proof: If \(m\) divides \(a-b\), then it also divides \(-(a-b) = b-a\).)

  4. If \(a \equiv b \pmod{m}\) and \(b \equiv c \pmod{m}\), then \(a \equiv c \pmod{m}\).

    (Proof: If \(m\) divides \(a-b\) and \(b-c\), it also divides its sum \((a-b) + (b-c) = (a-c)\).)

  5. We have that \(a \equiv 0 \pmod{m}\) if, and only if, \(a\) is divisible by \(m\).

  6. If \(r\) is the remainder of the division of \(a\) by \(m\), then \(a \equiv r \pmod{m}\).

    (Proof: By long division, we have that \(a = mq + r\), so \(a-r = qm\).)

  7. If \(r \in \{0, 1, 2, \ldots, m- 1\}\) (this means that \(r\) belongs to the set \(\{0, 1, 2, \ldots, m-1\}\)), then \(a \equiv r \pmod{m}\) only if \(r\) is the remainder of the division of \(a\) by \(m\).

  8. We have that \(a \equiv b \pmod{m}\) if, and only if, \(a\) and \(b\) have the same remainder when divided by \(m\).

These last three facts are very important. They say we can break the set of all integers in \(m\) parts, depending on the remainder of the division by \(m\). More concretely, for \(m=5\), every integer is congruent to one, and only one, among \(0\), \(1\), \(2\), \(3\), and \(4\) (the possible remainders of the division by \(5\)):

\[\begin{split}\begin{align*} \cdots -15 \equiv -10 \equiv -5 \equiv {\color{red} 0} \equiv 5 \equiv 10 \equiv 15 \equiv \cdots \pmod{5}\\ \cdots -14 \equiv -9 \equiv -4 \equiv {\color{red} 1} \equiv 6 \equiv 11 \equiv 16 \equiv \cdots \pmod{5}\\ \cdots -13 \equiv -8 \equiv -3 \equiv {\color{red} 2} \equiv 7 \equiv 12 \equiv 17 \equiv \cdots \pmod{5}\\ \cdots -12 \equiv -7 \equiv -2 \equiv {\color{red} 3} \equiv 8 \equiv 13 \equiv 18 \equiv \cdots \pmod{5}\\ \cdots -11 \equiv -6 \equiv -1 \equiv {\color{red} 4} \equiv 9 \equiv 14 \equiv 19 \equiv \cdots \pmod{5} \end{align*}\end{split}\]

So, we often call the remainder of \(a\) when divided by \(m\) the residue modulo \(m\). Most calculators have a “MOD” button to compute this residue/remainder. In Python/Sage we have %.

101 % 37  # residue of 101 modulo 37, or remainder of 101 when divided by 37

27

4.2. Arithmetic and Congruences#

Here is very important result:

Theorem 4.1 (Arithmetic Properties of Congruences)

Let \(m\) be an integer greater than \(1\) and suppose that

\[a_1 \equiv a_2 \pmod{m} \quad \text{and} \quad b_1 \equiv b_2 \pmod{m}.\]

Then

\[\begin{split}\begin{align*} a_1 + b_1 &\equiv a_2 + b_2 &&\pmod{m}, \\ a_1 - b_1 &\equiv a_2 - b_2 &&\pmod{m}, \\ a_1 \cdot b_1 &\equiv a_2 \cdot b_2 &&\pmod{m}, \\ a_1^k &\equiv a_2^k &&\pmod{m} \quad \text{for any positive integer $k$.} \end{align*}\end{split}\]

So, “\(\equiv\)” is similar to “\(=\)” in computations. In congruences with sums, differences, and products, we can replace a number by any other number that is congurent to it. Let’s see it in action in an example:

Example 4.1

What is the remainder of

\[5647438438 \cdot 85948594584 - 7548376839\]

when divided by \(5\)?

We could compute this huge number, then do the long division to find the remainder. But note that asking for the remainder modulo \(5\) is the same as asking for a number between \(0\) and \(4\) congruent to the original number:

\[5647438438 \cdot 85948594584 - 7548376839 \equiv \, ??? \pmod{5}.\]

The idea now is that the Theorem 4.1 above tells us that we can replace each of the three large numbers by smaller numbers congruent to them modulo \(5\), making the computation much simpler! As we’ve seen above, we can replace them by their residues modulo \(5\) (i.e., their remainders when divided by \(5\)), so numbers between \(0\) and \(4\).

Of course, we could just ask Sage for their residues, but we can in fact compute residues modulo \(5\) quite easily using the Theorem 4.1 and the fact that \(10 \equiv 0 \pmod{5}\). For example, let’s find the residue of the first number modulo \(5\):

\[\begin{split}\begin{align*} 5647438438 &= 5647438430 + 8 \\ &= 564743843 \cdot {\color{red} 10} + 8 \\ &\equiv 564743843 \cdot {\color{red} 0} + 8 && \text{(since $10 \equiv 0 \pmod{5}$)} \\ &= 8 \\ &= {\color{red} 5} + 3 \\ &\equiv {\color{red} 0} + 3 && \text{(since $5 \equiv 0 \pmod{5}$)} \\ &= 3 \pmod{5} \end{align*}\end{split}\]

The same idea shows that a positive number is always congruent to its last digit modulo \(5\)! So, we have:

\[\begin{split}\begin{align*} 8594859458{\color{blue} 4} &\equiv {\color{blue} 4} \pmod{5},\\ 754837683{\color{blue} 9} & \equiv {\color{blue} 9} = {\color{red} 5} + 4 \equiv {\color{red} 0} + 4 = 4 \pmod{5}. \end{align*}\end{split}\]

So, we have:

\[\begin{split}\begin{align*} {\color{red} 5647438438} &\equiv {\color{red} 3} \pmod{5}, \\ {\color{blue} 85948594584} &\equiv {\color{blue} 4} \pmod{5},\\ {\color{green} 7548376839} & \equiv {\color{green} 4} \pmod{5}. \end{align*}\end{split}\]

Now, using the theorem, we can do:

\[\begin{split}\begin{align*} {\color{red} 5647438438} \cdot {\color{blue} 85948594584} - {\color{green} 7548376839} &\equiv {\color{red} 3} \cdot {\color{blue} 4} - {\color{green} 4} \\ &\equiv 8 = {\color{orange} 5} + 3 \\ &\equiv {\color{orange} 0} + 3 = \boxed{3} \pmod{5} \end{align*}\end{split}\]

So, the remainder is \(3\)!

Example 4.2

What is the remainder of \(13^{1{,}000{,}000{,}000}\) when divided by \(7\)?

We can again think in terms of congruences and we are asking for a number between \(0\) and \(6\) congruent to \(13^{1{,}000{,}000{,}000}\) modulo \(7\). And again, by Theorem 4.1, we can replace \(13\) by its residue modulo \(7\) in a congruence, and clearly \(13 = 7 \cdot 1 + 6\), so we have

\[13^{1{,}000{,}000{,}000} \equiv 6^{1{,}000{,}000{,}000} \pmod{7}.\]

The problem is that, although much better, the number of the right is still humongous, too large even for computers!

Warning

We cannot replace the exponent by its residue modulo \(7\)! It is not part of the theorem and it does not work in general. We will later see how we can reduce the exponent as well, but with a different modulus!

So, for now, we can use a different trick. Note that \(6 \equiv -1 \pmod{7}\), and so we have:

\[\begin{split}\begin{align*} 13^{1{,}000{,}000{,}000} &\equiv 6^{1{,}000{,}000{,}000} \\ &\equiv (-1)^{1{,}000{,}000{,}000} \\ &= \boxed{1} \pmod{7}. \end{align*}\end{split}\]

4.3. Inverses Modulo \(m\)#

Definition 4.2 (Inverse Modulo \(m\))

Let \(a\), \(b\), and \(m\) be integers with \(m>1\). Then we say that \(a\) is the inverse of \(b\) modulo \(m\) (or that \(b\) is the inverse of \(a\) modulo \(m\)) if \(ab \equiv 1 \pmod{m}\).

For instance, \(2\) is the inverse of \(3\) modulo \(5\), since \(2 \cdot 3 = 6 = 1 + 5 \equiv 1 \pmod{5}\).

Note

Here I said “the” inverse instead of “a” inverse, since any two inverses will be congruent. For instance, we also have that \(2 \cdot 8 = 16 \equiv 1 \pmod{5}\), but note that \(8 \equiv 3 \pmod{5}\). In fact, we have that \(2b \equiv 1 \pmod{5}\) if, and only if, we have that \(b \equiv 3 \pmod{5}\).

Note that not all numbers have inverses. Clearly \(0\) has no inverse, no matter the modulus. But also, for instance, \(2\) has no inverse modulo \(6\):

for i in range(6):
    print(f"2 * {i} is {(2 * i) % 6} modulo 6.")

2 * 0 is 0 modulo 6.
2 * 1 is 2 modulo 6.
2 * 2 is 4 modulo 6.
2 * 3 is 0 modulo 6.
2 * 4 is 2 modulo 6.
2 * 5 is 4 modulo 6.

So, we never get \(1\). Note we do not need to go beyond \(5\) by the previous theorem, as \(6 \equiv 0 \pmod{6}\), \(7 \equiv 1 \pmod{6}\), etc.

Let’s write a function that given a modulus \(m\), returns all the numbers between \(0\) and \(m-1\) which have inverses:

def find_inverses(m):
    """
    Given a modulus m, finds all invertible elements modulo m.

    INPUT:
    m: the modulus (integer greater than 1.)

    OUTPUT:
    A set of elements between 0 and m-1 invertible modulo m.
    """
    invertible = set()  # all invertible elements
    for i in xsrange(m):  # test them all
        if i not in invertible:  # no need to test if already there
            for j in xsrange(m):  # look for inverse
                if (i * j) % m == 1:
                    # both i and j are invertible!
                    invertible = invertible.union({i, j})
    return invertible

Let’s see if we can find some pattern:

for m in xsrange(2, 21):
    print(f"{m:>2}: {sorted(list(find_inverses(m)))}")

 2: [1]
 3: [1, 2]
 4: [1, 3]
 5: [1, 2, 3, 4]
 6: [1, 5]
 7: [1, 2, 3, 4, 5, 6]
 8: [1, 3, 5, 7]
 9: [1, 2, 4, 5, 7, 8]
10: [1, 3, 7, 9]
11: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
12: [1, 5, 7, 11]
13: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
14: [1, 3, 5, 9, 11, 13]
15: [1, 2, 4, 7, 8, 11, 13, 14]
16: [1, 3, 5, 7, 9, 11, 13, 15]
17: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
18: [1, 5, 7, 11, 13, 17]
19: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
20: [1, 3, 7, 9, 11, 13, 17, 19]

Can we tell something from these examples?

If we pay attention, we will see:

Theorem 4.2 (Inverses Modulo \(m\))

An integer \(a\) is invertible modulo \(m\) if, and only if, \(\gcd(a, m) = 1\). In other words,

\[ax \equiv 1 \pmod{m}\]

has a solution (with \(x\) integer) if, and only if, \(\gcd(a, m) = 1\).

This is not hard to see.

First, suppose that \(\gcd(a, m) = 1\). (We want to show that \(a\) has an inverse modulo \(m\).) By Bezout's Lemma, we have that there are integers \(u\) and \(v\) such that

\[1 = au + mv.\]

But then, since \(m \equiv 0 \pmod{m}\), we have that

\[1 \equiv au + mv \equiv au + 0 = au \pmod{m}.\]

So, the \(u\) found by the Extended Euclidean Algorithm is the inverse of \(a\)!

Now, assume that \(a\) has an inverse \(b\) modulo \(m\). (We want to show that \(\gcd(a, m)=1\).) This means that

\[ab \equiv 1 \pmod{m},\]

which means that there is some integer \(k\) such that

\[ab = 1 + km, \qquad \text{or} \qquad ab - mk = 1.\]

Now, let \(d = \gcd(a,m)\). Then:

  1. \(d\) divides \(a\) and \(m\) (it is a common divisor); so

  2. \(d\) divides \(ab\) and \(mk\); so

  3. \(d\) divides \(ab - mk\); so

  4. \(d\) divides \(1\).

But the only positive integer that divides \(1\) is \(1\) itself, so, \(1 = d = \gcd(a, m)\).

4.3.1. Computing Inverses Modulo \(m\)#

As we can see above, we know how to compute inverses! We just use the Extended Euclidean Algorithm!

Example

Is \(35\) invertible modulo \(131\)? If so, find its inverse.

We can find the answer to both using Sage’s xgcd:

xgcd(35, 131)

(1, 15, -4)

The GCD (first output) is \(1\), so it is invertible. It also tells us that

\[1 = 35 \cdot 15 + 131 (-4)\]

(careful with the order of the output!), so \(15\) is the inverse. Indeed:

(35 * 15) % 131

1

4.4. The Ring of Integers Modulo \(m\)#

Definition 4.3 (Integers Modulo \(m\))

Given an integer \(m > 1\), we can create a new set:

\[\mathbb{Z} / m\mathbb{Z} = \{0, 1, 2, \ldots, (m-1)\}\]

where congruences become equalities! We call this set \(\mathbb{Z} / m\mathbb{Z}\) the set (or ring) of integers modulo \(m\).

Warning

These elements are not integers any more! They have different properties! We will discuss that in more detail below, but it is very important to observe that from the start.

To differentiate these elements from the actual integers, often times authors use a bar over the numbers for the elements of this set, as in

\[\mathbb{Z} / m\mathbb{Z} = \{\bar{0}, \bar{1}, \bar{2}, \ldots, \overline{m-1}\}\]

We will not use the bars here and will just have to be aware of the context. (Not using the bars is in fact the most common practice.)

So, while in \(\mathbb{Z}\) we had

\[\begin{split}\begin{align*} \cdots -15 \equiv -10 \equiv -5 \equiv {\color{red} 0} \equiv 5 \equiv 10 \equiv 15 \equiv \cdots \pmod{5}\\ \cdots -14 \equiv -9 \equiv -4 \equiv {\color{red} 1} \equiv 6 \equiv 11 \equiv 16 \equiv \cdots \pmod{5}\\ \cdots -13 \equiv -8 \equiv -3 \equiv {\color{red} 2} \equiv 7 \equiv 12 \equiv 17 \equiv \cdots \pmod{5}\\ \cdots -12 \equiv -7 \equiv -2 \equiv {\color{red} 3} \equiv 8 \equiv 13 \equiv 18 \equiv \cdots \pmod{5}\\ \cdots -11 \equiv -6 \equiv -1 \equiv {\color{red} 4} \equiv 9 \equiv 14 \equiv 19 \equiv \cdots \pmod{5} \end{align*}\end{split}\]

in \(\mathbb{Z}/5\mathbb{Z} = \{0, 1, 2, 3, 4\}\), we have:

\[\begin{split}\begin{align*} \cdots -15 = -10 = -5 = {\color{red} 0} = 5 = 10 = 15 = \cdots \\ \cdots -14 = -9 = -4 = {\color{red} 1} = 6 = 11 = 16 = \cdots \\ \cdots -13 = -8 = -3 = {\color{red} 2} = 7 = 12 = 17 = \cdots \\ \cdots -12 = -7 = -2 = {\color{red} 3} = 8 = 13 = 18 = \cdots \\ \cdots -11 = -6 = -1 = {\color{red} 4} = 9 = 14 = 19 = \cdots \end{align*}\end{split}\]

So, one can say that \(6 \in \mathbb{Z}/5\mathbb{Z}\), but in this new set, we have that \(6 = 1\) (since \(6 \equiv 1 \pmod{5}\)).

In this set, by our Theorem 4.1 (that allows us to replace an number by another one congruent to it in congruences), we can add, subtract, and multiply elements. But, again, with congruences becoming equality. For instance, still in \(\mathbb{Z}/5\mathbb{Z}\), we have:

\[\begin{split}\begin{align*} 3 + 4 &= 7 = \boxed{2}, \\ 3 - 4 &= -1 = \boxed{4}, \\ 3 \cdot 4 &= 12 = \boxed{2}. \end{align*}\end{split}\]

Although saying that \(3 + 4 = 7\) is technically correct, we usually want to give the result in the range \(\{0, 1, 2, 3, 4\}\) (when \(m=5\)), so it is better to say \(3 + 4 = 2\).

This last observation makes clear the fact that the elements of \(\mathbb{Z}/5\mathbb{Z}\) are not integers, as it is not true for integers that \(3 + 4 = 2\).

Important

If \(m\) and \(n\) are two different moduli, then \(\mathbb{Z}/m\mathbb{Z}\) and \(\mathbb{Z}/n\mathbb{Z}\) are unrelated, meaning that they live in different universes and do not relate to each other! This means we cannot perform operations with or even compare elements from these different sets.

To make this clear, one might think that since \(\mathbb{Z}/3\mathbb{Z} = \{0, 1, 2\}\) and \(\mathbb{Z}/4\mathbb{Z} = \{0, 1, 2, 3\}\), then \(\mathbb{Z}/3\mathbb{Z}\) is contained in \(\mathbb{Z}/4\mathbb{Z}\). But this is not the case! For instance, their \(1\)’s are not the same. In \(\mathbb{Z}/3\mathbb{Z}\) we have that \(1 + 1 + 1 = 3 = 0\), while in \(\mathbb{Z}/4\mathbb{Z}\) we have that \(1 + 1 + 1 = 3 \neq 0\).

Note

  1. The title of this section is “The Ring of Integers Modulo \(m\)”. The world ring comes from Abstract Algebra and essentially says that we can add, subtract, and multiply elements of \(\mathbb{Z}/m\mathbb{Z}\) with some of the expected properties for these operations.

  2. Many texts use \(\mathbb{Z}_m\) for \(\mathbb{Z}/m\mathbb{Z}\), since it is quicker to write. But is ambiguous, as \(\mathbb{Z}_p\) (for \(p\) prime) is often used for \(p\)-adic numbers, which is not the same as integers modulo \(p\). The notation \(\mathbb{Z}/m\mathbb{Z}\) is universally understood.

Definition 4.4 (Notation)

If \(p\) is a prime number, then we might write \(\mathbb{F}_p\) for \(\mathbb{Z}/p\mathbb{Z}\). That is because when \(p\) is prime (and only in that case), the ring \(\mathbb{Z}/p\mathbb{Z}\) is a field with \(p\) elements.

Although we won’t get into details here, the field part is saying that every element of \(\mathbb{Z}/p\mathbb{Z}\) except for \(0\) is invertible, which we know to be true from Theorem 4.2.

4.4.1. \(\mathbb{Z}/m\mathbb{Z}\) in Sage#

Fortunately, Sage allows us to create and use this set/ring \(\mathbb{Z}/m\mathbb{Z}\), with either Integers(m), IntegerModRing(m) or Zmod(m).

Zmod?

So, let’s create \(\mathbb{Z}/5\mathbb{Z}\) and save it in Z5:

Z5 = Zmod(5)
Z5

Ring of integers modulo 5

So, to convert an integer n to an element of \(\mathbb{Z}/5\mathbb{Z}\), we can do Z5(n). For example:

print(3 + 4)
print(3 - 4)
print(3 * 4)
print("-----")
print(Z5(3) + Z5(4))
print(Z5(3) - Z5(4))
print(Z5(3) * Z5(4))

7
-1
12
-----
2
4
2

We can use Sage’s function parent to determine the data type of an element:

parent(1)

Integer Ring

parent(Z5(1))

Ring of integers modulo 5

Note that when we convert an element to \(\mathbb{Z}/5\mathbb{Z}\), Sage automatically reduces it modulo \(5\) as well:

Z5(12)

2

Another way to create an element of \(\mathbb{Z}/5\mathbb{Z}\) without creating the ring first is using Mod:

Mod(2, 5)

2

parent(Mod(2, 5))

Ring of integers modulo 5

Mod(3, 5) * Mod(4, 5)

2

As observed before, Sage knows that we cannot mix different moduli: if you try

Mod(2, 3) + Mod(2, 4)

you get a Type Error:

TypeError: unsupported operand parent(s) for +: 'Ring of integers modulo 3' and 'Ring of integers modulo 4'

It also knows that the elements, like their \(1\)’s, are different:

Mod(1, 3) == Mod(1, 4)

False

4.4.2. \(\mathbb{Z}/p\mathbb{Z}\) and \(\mathbb{F}_p\) in Sage#

For prime moduli \(p\), we can also use either FiniteField(p) or GF(p) (for Galois Field) to create the field \(\mathbb{F}_p\). For instance, for \(\mathbb{F}_{11}\):

F = FiniteField(11)
F

Finite Field of size 11

FF = GF(11)
FF

Finite Field of size 11

Note that FiniteField and GF give exactly the same result/object.

FF == F

True

But, although mathematically \(\mathbb{F}_{11}\) and \(\mathbb{Z}/11\mathbb{Z}\) are the same, in Sage they have some technical differences:

Zmod(11) == FiniteField(11)

False

Zmod(11)

Ring of integers modulo 11

It mostly won’t make a difference for us here, but Zmod(11) and FiniteField(11) have some different methods. In practice, either one can be used most of the time.

Note that using Mod(a, p), we get that the result is in both Zmod(p) and FiniteField(p).

Mod(2, 11) in FiniteField(11)

True

Mod(2, 11) in Zmod(11)

True

Warning

As observed above, \(\mathbb{Z}/m\mathbb{Z}\) is a field if and only if the modulus \(m\) is prime. So, although we can create FiniteField(4) (or \(\mathbb{F}_4\)), it is not the same as Zmod(4) (or \(\mathbb{Z}/4\mathbb{Z}\)). The difference in this case goes beyond simple technicalities in the implementations of FiniteField(4) and Zmod(4) in Sage. They are really distinct and incompatible objects.

4.5. Multiplication by \(\mathbb{Z}\)#

If \(k\) is a positive integer and \(a\) is an element of \(\mathbb{Z}/m\mathbb{Z}\), we can write \(k \cdot a\), by which we mean

\[k \cdot a = \underbrace{a + a + \cdots a}_{\text{$k$ summands of $a$}}.\]

So, it is simply a shortcut. (Note that the addition is the addition above is the addition of elements of \(\mathbb{Z}/m\mathbb{Z}\).)

Now, we also define

\[0 \cdot a = 0\]

for any \(a\) in \(\mathbb{Z}/mZ\). Note: The \(0\) on left is the one from \(\mathbb{Z}\), which the one on the right is the one from \(\mathbb{Z}/m \mathbb{Z}\).

If \(k\) is a positive integer, we further define

\[(-k) \cdot a = \underbrace{(-a) + (-a) + \cdots + (-a)}_{\text{$k$ summands of $-a$}}.\]

Sage can handle that:

3 * Mod(5, 7)

1

Indeed, if \(3 \in \mathbb{Z}\) and \(5 \in \mathbb{Z}/7\mathbb{Z}\), then:

\[3 \cdot 5 = 5 + 5 + 5 = 15 = 1.\]

Also:

-3 * Mod(5, 7)

6

Indeed, if \(-3 \in \mathbb{Z}\) and \(5 \in \mathbb{Z}/7\mathbb{Z}\), then:

\[(-3) \cdot 5 = (-5) + (-5) + (-5) = 2 + 2 + 2 = 6.\]

Note

In the end, multiplying \(a\) and \(b\) when \(a \in \mathbb{Z}\) and \(b \in \mathbb{Z}/m\mathbb{Z}\) is the same as multiplying both elements as if they were in \(\mathbb{Z}/m\mathbb{Z}\).

So, we don’t have to worry about it:

Mod(3, 7) * Mod(5, 7) == 3 * Mod(5, 7)

True

Mod(-3, 7) * Mod(5, 7) == -3 * Mod(5, 7)

True

4.6. Exponents#

Similarly to how we have shortcut to add an element of \(\mathbb{Z}/m\mathbb{Z}\) to itself many times over (as in \(k \cdot a\)) we also have shortcut to multiplying: for any positive integer \(k\), we let:

\[a^k = \underbrace{a \cdot a \cdots a}_{\text{$k$ factors of $a$}}.\]

Note that this means that \(a^1 = a\) (for any \(a\)) and we extend the definition with

\[a^0 = 1 \qquad \text{for any $a \in \mathbb{Z}/m\mathbb{Z}$.}\]

Warning

Unlike with multiplication, we cannot replace the exponent \(k\) with an integer modulo \(m\)!

For instance, in \(\mathbb{Z}/4\mathbb{Z}\), we have that \(4 =0\), but while

\[2^ 0 = 1,\]

but

\[2^4 = 2 \cdot 2 \cdot 2 \cdot 2 = 16 = 4 \cdot 4 = 0 \cdot 0 = 0,\]

and hence

\[2^0 \neq 2^4.\]

The exponents do have familiar properties, though:

Property 4.1 (Properties of Exponents)

Let \(m\) be an integer greater than one, \(a\) and \(b\) be in \(\mathbb{Z}/m\mathbb{Z}\) and \(x\) and \(y\) be positive integers. Then:

  1. \(a^x \cdot a^y = a^{x + y}\),

  2. \(\left( a^x \right)^y = a^{x \cdot y}\),

  3. \((a \cdot b)^x = a^x \cdot b^x\).

Of course, Sage can handle exponents as well:

Mod(2, 4)^4

0

Mod(32, 101)^84938493

57

Important

In computations, you should always first convert an integer to \(\mathbb{Z}/m\mathbb{Z}\) and then compute the power, never the other way around!

We will see some reasons for the that below, but here is an illustration.

First, some information about the computer running these computations:

!inxi --system --cpu --memory

System:
  Host: dell7010 Kernel: 6.17.8-1-siduction-amd64 arch: x86_64 bits: 64
  Desktop: KDE Plasma v: 6.5.3 Distro: siduction 22.1.2 Masters_of_War -
    kde - (202303220911)
Memory:
  System RAM: total: 128 GiB available: 125.51 GiB used: 22.25 GiB (17.7%)
  Array-1: capacity: 128 GiB slots: 4 modules: 4 EC: None
  Device-1: DIMM1 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s
  Device-2: DIMM2 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s
  Device-3: DIMM3 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s
  Device-4: DIMM4 type: DDR5 size: 32 GiB speed: spec: 4800 MT/s
    actual: 3600 MT/s

CPU:
  Info: 24-core model: 13th Gen Intel Core i9-13900 bits: 64 type: MCP cache:
    L2: 32 MiB
  Speed (MHz): avg: 801 min/max: 800/5300:5600:4200 cores: 1: 801 2: 801
    3: 801 4: 801 5: 801 6: 801 7: 801 8: 801 9: 801 10: 801 11: 801 12: 801
    13: 801 14: 801 15: 801 16: 801 17: 801 18: 801 19: 801 20: 801 21: 801
    22: 801 23: 801 24: 801

Now, let’s compare the times:

%%time
Mod(32, 101)^84938493

CPU times: user 53 µs, sys: 0 ns, total: 53 µs
Wall time: 60.3 µs

57

%%time
Mod(32^84938493, 101)

CPU times: user 10.1 ms, sys: 7.05 ms, total: 17.2 ms
Wall time: 17.1 ms

57

The former is about \(250\) times faster!

Similarly, remember our computation that

\[5647438438 \cdot 85948594584 - 7548376839 \equiv 3 \pmod{5}.\]

Like doing it by hand, is much better to first reduce modulo \(5\) and then perform the operations. Since the numbers above are too small to notice a real difference in computations, below we increase them considerably:

a = 56474384387693274659724356924789347893479865923746592374659273452769469243
b = 8594859458489073409857134650891734560199032397013428957203875028435670248705
c = 754837683987509438750283475024930293023875023485702834570248549840524
m = 4389479349347575649873659287469247

%%time
Mod(a * b - c, m)

CPU times: user 337 µs, sys: 49 µs, total: 386 µs
Wall time: 388 µs

2125428931878337495052742076076766

%%time
Mod(a, m) * Mod(b, m) - Mod(c, m)

CPU times: user 17 µs, sys: 3 µs, total: 20 µs
Wall time: 21.9 µs

2125428931878337495052742076076766

4.7. The Group of Units of \(\mathbb{Z}/m\mathbb{Z}\)#

As we’ve seen before, if \(\gcd(a, m) = 1\), then there is some integer \(b\) such that \(ab \equiv 1 \pmod{m}\), and this is \(b\) is unique modulo \(m\), meaning that if \(ab' \equiv 1 \pmod{m}\) as well, then \(b \equiv b' \pmod{m}\).

We can now translate this to \(\mathbb{Z}/m\mathbb{Z}\): if \(a \in \mathbb{Z}/m\mathbb{Z}\) and \(\gcd(a, m)=1\), then there is a unique \(b\) in \(\mathbb{Z}/m\mathbb{Z}\) such that \(ab=1\). (In this case, \(ab=ab'=1\) means that \(b=b'\).) In this case, we say that \(a\) is invertible in \(\mathbb{Z}/m\mathbb{Z}\) or a unit of \(\mathbb{Z}/m\mathbb{Z}\), and \(b\) is its inverse. We denote this inverse of \(a\) by \(a^{-1}\).

Moreover, if \(\gcd(a, m) \neq 1\), then there is no \(b \in \mathbb{Z}/m\mathbb{Z}\) such that \(ab = 1\). (In this case, \(a\) is not a unit.)

We denote the set of all units (or all invertible elements) of \(\mathbb{Z}/m\mathbb{Z}\) by \((\mathbb{Z}/m\mathbb{Z})^{\times}\). So,

\[(\mathbb{Z}/m\mathbb{Z})^{\times} = \{ a \in \mathbb{Z}/m\mathbb{Z} \; : \; \gcd(a, m) = 1 \}.\]

(We read the “\(:\)” as “such that”. The left part is read as “the set of all elements \(a\) in \(\mathbb{Z}/m\mathbb{Z}\) such that \(\gcd(a, m)=1\)”.)

Note

The title of this section is “The Group of Units of \(\mathbb{Z}/m\mathbb{Z}\)” and, again, the term group comes from Abstract Algebra. We will talk a little more about groups in a later chapter!

Property 4.2 (Properties of Unities)

Here are some basic properties of \((\mathbb{Z}/m\mathbb{Z})^{\times}\) (that in fact show it is a group) of the product:

  1. \(1 \in (\mathbb{Z}/m\mathbb{Z})^{\times}\);

  2. if \(a, b \in (\mathbb{Z}/m\mathbb{Z})^{\times}\), then \(a \cdot b \in (\mathbb{Z}/m\mathbb{Z})^{\times}\);

  3. if \(a \in (\mathbb{Z}/m\mathbb{Z})^{\times}\), then \(a^{-1}\) exists and is in \((\mathbb{Z}/m\mathbb{Z})^{\times}\) as well;

  4. if \(a, b, c \in (\mathbb{Z}/m\mathbb{Z})^{\times}\), then \(a \cdot (b \cdot c) = (a \cdot b) \cdot c\).

As you’d expect, Sage can find inverses if they exist:

Mod(32, 101)^(-1)

60

And indeed:

Mod(60, 101) * Mod(32, 101)

1

We also have the Sage function inverse_mod:

inverse_mod(32, 101)

60

But note that unlike the previous example, which gives us an element of \(\mathbb{Z}/101\mathbb{Z}\), the latter gives us an integer!

parent(Mod(32, 101)^(-1))

Ring of integers modulo 101

parent(inverse_mod(32, 101))

Integer Ring

If you try to invert an element with no inverse, it gives an error. For instance, if you try

Mod(2, 6)^(-1)

it gives

ZeroDivisionError: inverse of Mod(2, 6) does not exist

Of course, we can check if an element is a unit with the GCD, but we also have the .is_unit method:

a = Mod(2, 6)
a.is_unit()

False

Sage can also give us the whole set of units. Remembering that we’ve set above the variable Z5 as Zmod(5) meaning \(\mathbb{Z}/5\mathbb{Z}\) we have:

Z5.unit_group()

Multiplicative Abelian group isomorphic to C4

That is strange… Let’s look at the elements:

set(Z5.unit_group())

{1, f, f^2, f^3}

Still strange… What is f?

This is a related to some algebraic properties of the group of units, but we can “translate” is back to \(\mathbb{Z}/5\mathbb{Z}\):

{Z5(x) for x in Z5.unit_group()}

{1, 2, 3, 4}

So, we use this last method to explicitly obtain the set of all units. (We will not worry about the output of the previous two commands here.)

Z24 = Zmod(24)
{Z24(x) for x in Z24.unit_group()}

{1, 5, 7, 11, 13, 17, 19, 23}
Contents