Powers in \mathbb{Z}/m\mathbb{Z}

5. Powers in $\mathbb{Z}/m\mathbb{Z}$#

5.1. Bases and Binary Numbers#

We work with numbers with decimal notation (or, equivalently, in base $10$). This means that we have ten digits, $0$ to $9$, and when we run out of digits (i.e., we have a number larger than ten) we add another digit “in front”. Let’s express this idea in a more mathematical way.

Remember that

\[\begin{split}\begin{align*} 10^0 &= 1 \\ 10^1 &= 10 \\ 10^2 &= 100 \\ 10^3 &= 1{,}000 \\ &\;\;\vdots \\ 10^n &= 1\underbrace{000\ldots 000}_{\text{$n$ zeros}} \end{align*}\end{split}\]

This allows to write, say, the number $9{,}217$ as

\[\begin{split}\begin{align*} 9{,}217 &= 9{,}000 + 200 + 10 + 7\\ &= 9 \cdot 10^3 + 2 \cdot 10^2 + 1 \cdot 10 + 7 \cdot 10^0. \end{align*}\end{split}\]

So, we can write any number as a sum of powers of $10$ times a digit in $\{0, 1, 2, \ldots , 9\}$. In practice, counting from the right, we multiply the $k$-th digit by $10^{k-1}$ and then add all this products to get the number. For example:

\[\begin{split}\begin{align*} 81 &= 8 \cdot 10 + 1 \cdot 10^0, \\ 107 &= 1 \cdot 10^2 + 0 \cdot 10 + 7 \cdot 10^0, \\ 3{,}445 &= 3 \cdot 10^3 + 4 \cdot 10^2 + 4 \cdot 10 + 5 \cdot 10^0. \end{align*}\end{split}\]

Now, let’s say that, for some reason, we want to only use $8$ digits: $\{0, 1, 2, \ldots, 7\}$, for instance, because we might have only $8$ fingers to count on, instead of $10$. So, the digits $8$ and $9$ do not exist for us. How would we write numbers, then? Well, we follow the same idea: when we run out of digits, we start adding digits in front!

The problem is that then, our number $9$ would be represented as $10$, since when counting it would go:

\[0, 1, 2, 3, 4, 5, 6, 7, {\color{red} 10}, 11, 12, 13, 14, 15, 16, 17, {\color{red} 20}, 21 \ldots\]

To make this a little less confusing, let’s use a subscript of $8$, as in $10_8$, when we mean that we are using eight digits, on in base $8$. (This representation is also called octal.) So, that is to say that

\[10_8 = 8, \qquad 11_8 = 9, \qquad 12_8 = 10, \qquad \cdots\]

Mathematically, this is very similar to numbers base $10$, but now we use powers of $8$, our new base. So,

\[\begin{split}\begin{align*} 7_8 &= 7 \cdot 8^0 = 7,\\ 10_8 &= 1 \cdot 8^1 + 0 \cdot 8^0 = 8, \\ 215_8 &= 2 \cdot 8^2 + 1 \cdot 8 + 5 = 141, \\ 1{,}046_8 &= 1 \cdot 8^3 + 0 \cdot 8^2 + 4 \cdot 8 + 6 \cdot 8^0 = 550. \end{align*}\end{split}\]

You might have heard that computers use binary numbers, meaning, numbers in base $2$. Therefore, we use only two digits, $0$ and $1$. The reason is due to how computers work. Very roughly speaking, primitive computers involved a series of switches, which could be either on, represented by $1$, or off, represented by $0$:

So, if you have, say, $5$ switches, you can give on/off instructions to them with a sequence of $5$ zeros and ones, from $00000_2$ (all off) to $11111_2$ (all on), so, a number between $0$ and $1 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2 + 1 \cdot 2^0 = 31$. Each individual digit is called a bit.

Sometimes in computer science we use hexadecimal numbers, meaning numbers in base $16$. So, we need $16$ digits. Since we only have $10$, we add letters for the next six:

\[\begin{split}\begin{align*} A &= 10, & B &= 11, & C &= 12, \\ D &= 13, & E &= 14, & F &= 15. \end{align*}\end{split}\]

Hence, for instance:

\[A3D7_{16} = 10 \cdot 16^3 + 3 \cdot 16^2 + 13 \cdot 16 + 7 \cdot 16^0 = 41{,}943.\]

The advantage is that now each digit corresponds to $4$ bits.

5.1.1. Converting Bases#

It should be clear by now how we can convert a number in some base to base $10$. But how about the opposite way?

Algorithm 5.1 (Base Change)

To convert a positive integer $n$ from base $10$ to base $b$, we perform a series of long divisions by $b$: while the quotient $q_i$ is not zero, we do:

\[\begin{split}\begin{align*} n &= b \cdot q_0 + r_0, \\ q_0 &= b \cdot q_1 + r_1, \\ q_1 &= b \cdot q_2 + r_2, \\ &\;\; \vdots \\ q_{k-1} &= b \cdot q_k + r_k, \\ q_k &= b \cdot 0 + r_{k+1}. \end{align*}\end{split}\]

Then, we have that

\[n = r_{k+1} \cdot b^{k+1} + r_k \cdot b^k + \cdots + r_2 \cdot b^2 + r_1 \cdot b + r_0 \cdot b^0,\]

i.e.,

\[n = (r_{k+1}r_k\cdots r_2r_1r_0)_b.\]

Note

Note that the first remainder is the last digit!

Let’s show it in action. We’ve seen that $1{,}046_8 = 550$. So, let’s double check it by converting $550$ to base $8$.

We divide our number by $8$:

divmod(550, 8)  # divmod gives the quotient and remainder, in that order

(68, 6)

The remainder is $6$, so our representation in base $8$ ends with $\boxed{6}$! So now, we take the quotient and divide by $8$:

divmod(68, 8)

(8, 4)

The second to the last digit is then $\boxed{4}$. Since the quotient is not $0$ (it’s $8$), we keep dividing, i.e., we divide the last quotient by $8$:

divmod(8, 8)

(1, 0)

We get a remainder of $0$, so the next digit (to the left) is $\boxed{0}$. The quotient is $1$, not zero, so we continue:

divmod(1, 8)

(0, 1)

Now the quotient is $0$, so we are done, and the first digit (or last, from right to left) is $\boxed{1}$.

So, indeed, the digits from left to right were $550 = 1{,}046_8$.

Homework

Again, you will implement this algorithm in your homework.

But, as usual, Sage can do it for us using the method .digits:

550.digits(base=8)

[6, 4, 0, 1]

Note that the digits are given left to right, as you can see.

If the base is greater than $10$, it gives the corresponding numbers, not really digits. For example, we’ve see that $A3D7_{16} = 41{,}943$ (where $A=10$ and $D=13$):

41943.digits(base=16)

[7, 13, 3, 10]

We can specify the digits using the optional argument digits:

41943.digits(base=16, digits="0123456789ABCDEF")

['7', 'D', '3', 'A']

For base $2$, we can also use the .bits method:

41943.bits()

[1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1]

41943.digits(base=2)

[1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1]

5.2. Fast Powering#

As we will soon see, many encryption methods will rely on computations of very large powers, so it is important that we have an efficient way to compute them.

The naive way to compute $g^N$ is to perform $N-1$ products:

\[\begin{split}\begin{align*} g^2 &= g \cdot g \\ g^3 &= g^2 \cdot g \\ g^4 &= g^3 \cdot g \\ &\;\; \vdots \\ g^N &= g^{N-1} \cdot g. \end{align*}\end{split}\]

But there is a much more efficient way:

Algorithm 5.2 (Fast Powering Algorithm (Successive Squaring))

To compute $g^N$, where $g$ is in $\mathbb{Z}/m\mathbb{Z}$:

Write $N$ in base $2$, i.e.,

\[N = N_0 + N_1 \cdot 2 + N_2 \cdot 2^2 + \cdots N_r \cdot 2^r\]

with $N_i \in \{0, 1\}$. (Note that $r = \lfloor \log_2(N) \rfloor$, where $\lfloor x \rfloor$ is just rounding down $x$ to the largest integer less than or equal to $x$, the so called floor function.)
Compute the powers:

\[\begin{split}\begin{align*} a_0 &\equiv g && \pmod{m} \\ a_1 &\equiv a_0^2 \equiv g^2 && \pmod{m} \\ a_2 &\equiv a_1^2 \equiv g^{2^2} &&\pmod{m} \\ a_3 &\equiv a_2^2 \equiv g^ {2^3} &&\pmod{m} \\ &\;\;\vdots \\ a_r &\equiv a_{r-1}^2 \equiv g^{2^r} &&\pmod{m} \end{align*}\end{split}\]

reducing modulo $m$ at every step! (Note that this gives a total of $r$ products, one for each squaring.)
Now, using properties of powers, we have

\[\begin{split}\begin{align*} g^N &= g^{N_0 + N_1 \cdot 2 + N_2 \cdot 2^2 + \cdots N_r \cdot 2^r} \\ &= g^{N_0} \cdot (g^2)^{N_1} \cdot (g^{2^2})^{N_2} \cdots (g^{2^r})^{N_r} \\ &= a_0^{N_0} \cdot a_1^{N_1} \cdot a_2^{N_2} \cdots a_r^{N_r}. \end{align*}\end{split}\]

Note that the powers of $N_i$ do not require extra products, since if $N_i$ is $0$, the factor $a^{N_i} = 1$ and can be simply skipped, and if $N_i=1$, then $a_i^{N_i} = a_i$. Hence, this last step requires at most another $r$ products.

Therefore, with this method, we can compute $g^N$ in at most $2 r = 2 \cdot \lfloor \log_2(N) \rfloor$ products.

Warning

In the second step above, it is very important the we compute $g^{{2^k}}$ by squaring the previously computer $g^{2^{k-1}}$ (as I do below), and not directly, as in g^(2^k).

How does it compare to the previous naive method, that required $N-1$ products?

N = 10^6
2 * floor(log(N, base=2))

So, for $N$ equal to one million, we go from $999{,}999$ products to only $21$! That’s a huge improvement!

Let’s do a concrete example, with the help from Sage.

Example 5.1

Compute $11^{156}$ in $\mathbb{Z}/1237\mathbb{Z}$.

First, we compute $156$ in base 2:

digits_base_2 = 156.digits(base=2)
digits_base_2

[0, 0, 1, 1, 1, 0, 0, 1]

The length is:

len(digits_base_2)

Now, we could create a list with the powers of $11$ modulo $1237$, but this can take some memory. So, we will do one step at a time. We initialize a variable res to keep the result (the final power) as $1$ and a variable a as $g$, or $11$ in our case. Our computations will be much faster if we make g = Mod(11, 1237), as Sage then will automatically (and efficiently) reduce the result of each squaring modulo $1237$:

res = 1
a = Mod(11, 1237)

Now, at each step we look at the correspond binary digit:

if the digit is $1$, we replace res by its product with a;
if the digit is $0$, we do not change res.

Then, we replace a by a^2.

So, let’s look at our first binary digit, remembering that Sage starts at index $0$:

digits_base_2[0]

Since it’s zero, we only square a:

a ^= 2  # same as a = a^2

Next digit:

digits_base_2[1]

Also zero, so we just square a again:

a ^= 2  # same as a = a^2

digits_base_2[2]

Now the digit is $1$, so we do two steps:

res *= a  # same as res = res * a
a ^= 2

Next digit:

digits_base_2[3]

One again:

res *= a
a ^= 2

digits_base_2[4]

Two steps:

res *= a
a ^= 2

digits_base_2[5]

Since the digit is now $0$, we only square a:

a ^= 2

Continue:

digits_base_2[6]

Square ony again:

a ^= 2

digits_base_2[7]

Now, in principle we need two steps, since the digit is $1$, but since it is the last digit, there is no need to square, only update res:

res *= a

Now, res should contain our power:

res

We can check with Sage:

Mod(11, 1237)^156

Note that we only had $11$ products (instead of $155$!) and we kept the numbers we are multiplying relatively small since we reduced the result modulo $1237$ at each step!

Homework

As you might expect, you will implement this algorithm in your homework. Hopefully the steps above give you an idea on how to use a loop (and some if clauses) to automate the process.

5.3. Negative Powers#

So far we’ve only defined positive powers of elements of $\mathbb{Z}/m\mathbb{Z}$. In general, there is no “natural” was to define negative powers. But if $a$ is a unit of $\mathbb{Z}/m\mathbb{Z}$, then we can define negative powers! If $k$ is a positive integer, then we define

\[a^0 = 1 \qquad \text{and} \qquad a^{-k} = \underbrace{a^{-1} \cdot a^{-1} \cdots a^{-1}}_{\text{$k$ factors of $a^{-1}$}}.\]

(As usual, $a^{-1}$ here is the inverse of $a$ (a unit) $\mathbb{Z}/m\mathbb{Z}$.) Moreover, the properties of powers we had before for positive exponents also work for if allow zero or negative exponents

5.4. The Euler $\varphi$-Function#

We start by introducing some notation:

Definition 5.1 ((Number of Elements of a Set))

If $S$ is a finite set, we denote by $|S|$ the number of elements of $S$. If $S$ is infinite, we write $|S| = \infty$.

The following arithmetic function will be quite important to some of our applications in cryptography:

Definition 5.2 (The Euler $\varphi$-Function)

Given a positive integer $m$, we define the $\varphi(m)$ as $|(\mathbb{Z}/m\mathbb{Z})^{\times}|$, i.e., the number of elements of $(\mathbb{Z}/m\mathbb{Z})^{\times}$, in other words

\[\varphi(m) = |\{a \in \{1, 2, \ldots, m-1\} \; : \; \gcd(a, m) = 1 \}|.\]

We also define $\varphi(1)$ as $1$. This function is called the Euler $\varphi$-function.

Example

Since $(\mathbb{Z}/5\mathbb{Z})^{\times} = \{1, 2, 3, 4\}$, then $\varphi(5) = 4$.
Since $(\mathbb{Z}/24\mathbb{Z})^{\times} = \{1, 5, 7, 11, 13, 17, 19, 23\}$, then $\varphi(24) = 8$.

Note

If $p$ is prime, then $\varphi(p) = p-1$, as all integers between $1$ and $p-1$ are relatively prime to $p$.

As we will later see, this function will be important for the RSA Cryptosystem.

One might ask if there is another way to compute $\varphi(m)$, besides just checking for integers relatively prime to $m$, which can be slow if $m$ is large.

We have:

Theorem 5.1 (Formula for $\varphi(m)$)

Let $m$ be a positive integer greater than one and

\[m = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\]

be its prime decomposition. Then

\[\varphi(m) = \left( (p_1 - 1) \cdot p^{e_1 -1} \right) \cdot \left((p_2 - 1) \cdot p_2^{e_2 - 1}\right) \cdots \left((p_k - 1) \cdot p_k^{e_k - 1}\right).\]

Example

Since $5$ is prime, then $\varphi(5) = (5 - 1) \cdot 5^{1-1} = 4$.
More generally, for any prime $p$ we have that $\varphi(p) = p-1$.
Since $24 = 2^3 \cdot 3$, we have $\varphi(24) = \left( (2-1) \cdot 2^{3-1} \right) \cdot \left( (3-1) \cdot 3^{1-1} \right) = 4 \cdot 2 = 8$.

Let’s check that this formula works using Sage’s euler_phi implementation of $\varphi$. First, let’s create a function that uses the prime factorization for the computation:

def euler_phi_from_fact(m):
    """
    Given a positive integer m, returns the Euler phi-function of n by
    using the prime factorization of m.

    INPUT:
    m: positive integer.

    OUTPUT:
    The Euler phi-function at m (a positive integer).
    """
    return prod((p - 1) * p^(e - 1) for p, e in factor(m))

Now, let’s test it:

number_tries = 100
max_number = 10^5

for _ in range(number_tries):
    m = randint(2, max_number + 1)
    if euler_phi(m) != euler_phi_from_fact(m):
        print(f"Failed for {m = }.")
        breal
else:
    print("It seems to work!")

It seems to work!

The problem with is this method, as we shall see, is that the prime factorization can be slow for very large $m$ with only very large prime factors!

5.5. Reducing Powers#

Remember that we cannot reduce powers modulo $m$ in computations in $\mathbb{Z}/m\mathbb{Z}$. As we’ve seen, in $\mathbb{Z}/4\mathbb{Z}$ we have that $4 = 0$, but

\[2^0 = 1 \not \equiv 0 \equiv 2^4 \pmod{4}.\]

That is, again, because the exponent must be in $\mathbb{Z}$, and not in $\mathbb{Z}/4\mathbb{Z}$. But there is something we can do:

Proposition 5.1 (Reducing Powers)

Let $a$ in $\mathbb{Z}/m\mathbb{Z}$ and suppose that $k$ is a positive integer such that $a^k = 1$. Then, if $r \equiv s \pmod{k}$ (so, modulo $k$, and not $m$!), then $a^r = a^s$. Therefore, we can reduce exponents modulo $k$ (and not $m$).

Let’s see some examples: we have that in $\mathbb{Z}/7\mathbb{Z}$ that $3^6 = 1$.

Mod(3, 7)^6

Then, it should be the case that for any exponent $r$ we should have that $2^r$ is the same, in $\mathbb{Z}/7\mathbb{Z}$, as $2^s$ where $s$ is the residue of $r$ modulo $6$ (and not 7!). Let’s test it:

number_tries = 1000
max_exp = 3000

for _ in range(number_tries):
    r = randint(7, max_exp)
    s = r % 6  # residue modulo 6
    if Mod(3, 7)^r != Mod(3, 7)^s:
        print(f"Failed for {r = } and {s = }.")
        break
else:
    print("It seems to work!")

It seems to work!

This is not hard to see why this is true in general. Suppose $a^k = 1$ in $\mathbb{Z}/m\mathbb{Z}$ and $r \equiv s \pmod{k}$. This means that $s = r + nk$ for some integer $n$. Then, using properties of exponents:

\[a^s = a^{r + nk} = a^r \cdot a^{nk} = a^r \cdot (a^k)^s = a^r \cdot 1^s = a^r.\]

Of course, this is all based on the fact that $a^k = 1$ for some $k$, but such an exponent might not exist. If $a^k = 1$, then $a \cdot (a^{k-1}) = a^k = 1$, and so $a$ must be a unit!

But, assuming that $a$ is a unit, how would we find such $k$? Does it even exist? The answers are given by the following theorem:

Theorem 5.2 (Euler’s Theorem)

Let $a$ be a unit in $\mathbb{Z}/m\mathbb{Z}$ (i.e., $\gcd(a, m) = 1$). Then $a^{\varphi(m)} = 1$ in $\mathbb{Z}/m\mathbb{Z}$ (i.e., $a^{\varphi(m)} \equiv 1 \pmod{m}$). (Here $\varphi$ is the Euler $\varphi$ function.)

We will not prove it here, although it is not terribly difficult to do so, but instead we will test it empirically for many random cases using Sage:

number_tries = 1000
max_m = 3000

for _ in range(number_tries):
    m = randint(4, max_m)
    while True:
        a = randint(2, m  - 1)
        if gcd(a, m) == 1:
            break
    if Mod(a, m)^euler_phi(m) != Mod(1, m):
        print(f"Failed for {m = } and {a = }.")
        break
else:
    print("It seems to work!")

It seems to work!

The particular case when $m$ is a prime has a different name:

Theorem 5.3 (Fermat’s Little Theorem)

If $p$ is prime and $p \nmid a$, then $a^{p-1} = 1$ in $\mathbb{Z}/p\mathbb{Z}$ (i.e., $a^{p-1} \equiv 1 \pmod{p}$).

This follows from Euler’s Theorem since, when $p$ is prime, we have that $\varphi(p) = p-1$ and $\gcd(a, p) = 1$ if, and only if, $p \nmid a$.

Let’s apply these ideas in an example.

Example

What is the remainder of $100324^{657483384}$ when divided by $15$?

First we reduce $100324$ modulo $15$:

100324 % 15

So, $100324^{657483384} \equiv 4^{657483384} \pmod{15}$. Now, observe that $\gcd(4, 15) = 1$ since the only divisors of $4$ are $1$, $2$, and $4$ and, among these, only $1$ divides $15$. Now, by $\varphi(15) = \varphi(3 \cdot 5) = 2 \cdot 4 = 8$, and by Euler's Theorem and Proposition 5.1, we can reduce the exponent modulo $8$:

657483384 % 8

So, combining Euler's Theorem and Theorem 4.1, we get:

\[100324^{657483384} \equiv 4^0 = 1 \pmod{15}.\]

Hence, the remainder of $100324^{657483384}$ when divided by $15$ is $1$.

Let’s check it with Sage:

Mod(100324, 15)^657483384

Important

Note that we do Mod(100324, 15)^657483384 and not Mod(100324^657483384, 15), as the latter is much less efficient and might involve numbers that are too large even for computers.

5.6. Order of Units#

Note that although raising a unit of $\mathbb{Z}/m\mathbb{Z}$ to the exponent $\varphi(m)$ always yields $1$ (by Euler’s Theorem), it might not be the smallest positive power that gives $1$. For instance, in $\mathbb{Z}/7\mathbb{Z}$, we have $\varphi(7) = 6$ and although $6^6 = 1$, we also have that $6^2 = 36 = 1 + 5 \cdot 7 = 1$.

This motivates the following definition:

Definition 5.3 (Order of an Element)

If $a$ is a unit of $\mathbb{Z}/m\mathbb{Z}$, then the order of $a$, usually denoted by $|a|$, is the smallest positive power $k$ such that $a^k = 1$.

(So, by Euler’s Theorem, in $\mathbb{Z}/m\mathbb{Z}$, for any unit $a$, we have that $|a| \leq \varphi(m)$.)

Caution

We have three different meanings to the $| \cdot |$ symbol, depending on context:

If $x$ is a real number, then $|x|$ is the absolute value of $x$.
If $S$ is a set, then $|S|$ is the number of elements of $S$.
If $a \in (\mathbb{Z}/m\mathbb{Z})^{\times}$, then $|a|$ is the order of $m$ in $(\mathbb{Z}/m\mathbb{Z})^{\times}$ (as defined above).

We have:

Proposition 5.2

Let $a$ be a unit of $\mathbb{Z}/m\mathbb{Z}$. If $a^k = 1$, for some integer $k$, then $|a| \mid k$. In particular, we always have that $|a| \mid \varphi(m)$.

Proof. This is not too hard to see: suppose that $a^k$ and let’s denote $n = |a|$. We can perform the long division of $k$ by $n$: $k = qn + r$, for integers $q$ and $r$, with $r \in \{0, 1, 2, \ldots, (n-1)\}$. Then,

\[1 = a^k = a^{nq + r} = a^{nq} \cdot a^r = (a^n)^q \cdot a^r = 1^q \cdot a^r = a^r.\]

Therefore $r$ is a power smaller than $n=|a|$ that gives $1$. But since, by definition of order $n$ is the smallest positive power that gives $1$, we must have that $r=0$ (remember $0$ is neither positive, nor negative!), i.e., $n \mid k$.

Homework

In your homework you will write a function that takes a unit of $\mathbb{Z}/m\mathbb{Z}$ and computes its order. One could do it by sheer “brute force”, meaning testing if $a^1=1$, if not test if $a^2=1$, if not test if $a^3=1$, etc., until we find the first power that does result in $1$. (This power is the order.)

For instance, let’s find the order of $3$ in $\mathbb{Z}/11\mathbb{Z}$:

Mod(3, 11)^2

Not, one, so we continues:

Mod(3, 11)^4

No…

Mod(3, 11)^5

Ah, so in $\mathbb{Z}/11\mathbb{Z}$ we have that $|3|=5$.

An alternative would be to only test divisors of $\varphi(m)$, using Sage’s divisors function. This would work better for most numbers, but $\varphi(m)$ can be hard to compute. In those cases, the “brute force” method would be better.

In our particular case above in $\mathbb{Z}/11\mathbb{Z}$, we would only to test divisors of $\varphi(11) = 10$, so $\{1, 2, 5, 10\}$.

Of course, Sage can do it native way to compute it using .multiplicative_order():

Mod(3, 11).multiplicative_order()

Caution

Sage also has .order(), but it is not what we want! (It is an additive order, that does not concern us here.)

For example:

Mod(3, 11).order()

5.6.1. Orders of Powers#

Suppose we know the order $|a|$ for some unit $a$. It is often useful to know orders of powers of $a$. (This will be useful, in particular, when we deal with primitive roots.)

Proposition 5.3 (Order of a Power)

Let $a \in (\mathbb{Z}/m\mathbb{Z})^{\times}$ with $|a| = n$. Then, we have that

\[|a^k| = \frac{n}{\gcd(n, k)}.\]

It is not too hard to give a mathematical proof of this fact. Note that if $d = \gcd(n, k)$, the $d$ divides both $n$ and $k$, so both $n/d$ and $k/d$ are integers. So, we have that

\[\begin{split}\begin{align*} (a^k)^{n/d} &= a^{(kn)/d} && \text{[properties of exponents]} \\ &= a^{n \cdot k/d} \\ &= (a^n)^{k/d} && \text{[since $k/d$ is an integer!]} \\ &= 1^{k/d} && \text{[since $n=|a|$]} \\ &= 1. \end{align*}\end{split}\]

Then, by Proposition 5.2, we have that $|a^k|$ divides $n/d$. But we are still left to prove that this power, $n/d$, is the smallest power of $a^k$ that gives $1$.

This is not too hard either, but for the sake of brevity, let’s just check it with many random tests in Sage:

# bounds for the modulus
min_m = 30
max_m = 10^6

# number of tests
number_tries = 10^4

for _ in range(number_tries):
    # find random m
    m = randint(min_m, max_m)

    # find random *unit* a
    a = randint(2, m - 1)
    while gcd(a, m) != 1:
        # if not unit, try again!
        a = randint(2, m - 1)

    n = Mod(a, m).multiplicative_order()
    k = randint(1, euler_phi(m) - 1)
    d = gcd(n, k)

    # check!
    if (Mod(a, m)^k).multiplicative_order() != n // d:
        print(f"Fails for {m = }, {a = }, and {k = }.")
        break
else:
    print("It seems to work!")

It seems to work!

5.6.2. Computing Successive Powers#

In many concrete examples, like the “brute force” computation of the order of a unit above, one needs to compute successive powers of an element. In these cases, if one cares about performance (like we do here!), one should not use powers, but single products. As an example, suppose we need to compute

\[3^0, 3^1, 3^2, \ldots, 3^{100{,}000}.\]

Here, as an example, we will not use the powers for anything, but just compute them. Here is one way:

%%time
max_power = 10**5
base = 3

for i in range(max_power + 1):
    x = base ** i

CPU times: user 3.74 s, sys: 60 µs, total: 3.74 s
Wall time: 3.74 s

In each iteration, we compute base ** i, which involves several multiplications (if i is large).

We can do much better!

%%time
max_power = 10**5
base = 3

x = 1
for i in range(max_power):
    x *= base

CPU times: user 62.9 ms, sys: 0 ns, total: 62.9 ms
Wall time: 62.6 ms

Here, in each iteration, we perform a single product: x * base!

Important

Please remember this in your homework (and future code!), as it makes a considerable difference in performance!

And here is the system used for 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.22 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: 800 min/max: 800/5300:5600:4200 cores: 1: 800 2: 800
    3: 800 4: 800 5: 800 6: 800 7: 800 8: 800 9: 800 10: 800 11: 800 12: 800
    13: 800 14: 800 15: 800 16: 800 17: 800 18: 800 19: 800 20: 800 21: 800
    22: 800 23: 800 24: 800

Note

Side Note

If you change the base in the code above to $2$, you will see that the former code becomes slightly faster than the second (in Sage). That’s because Sage is smart enough to see this as an operation of binary numbers, which is faster. In pure Python, that is not the case and the former is still a lot faster.

5.7. Primitive Roots#

Remember the group of units of $\mathbb{Z}/m\mathbb{Z}$:

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

When the modulus is prime, this set has an interesting (and useful) property:

Theorem 5.4 (Primitive Root Theorem)

Let $p$ be a prime. (Remember then that $\mathbb{F}_p$ is just another way to write $\mathbb{Z}/p\mathbb{Z}$. Remember also that we can only use this notation for prime moduli!) Then, there is an element $g \in \mathbb{F}_p^{\times}$ such that every element of $\mathbb{F}_p^{\times}$ is a power of $g$. In other words:

\[\mathbb{F}_p^{\times} = \{1, g, g^2, g^3, \ldots, g^{p-2}\}.\]

Definition 5.4 (Primitive Root)

A $g$ as above is called a primitive root of $\mathbb{F}_p$ or a generator of $\mathbb{F}_p^{\times}$.

Note

We have that $g$ is a primitive root of $\mathbb{F}_p^{\times}$ if, and only if, $|g| = (p-1)$, the total number of elements of $\mathbb{F}_p^{\times}$. So, to find a primitive root, we just look for elements of order $p-1$.

Here are some observations. First, this element is not necessarily unique. For instance, let’s take $p=11$. Let’s find the primitive roots of $\mathbb{F}_{11}$:

for i in xsrange(1, 11):
    if Mod(i, 11).multiplicative_order() == 10:
        print(f"{i} is a primitive root (modulo 11).")

is a primitive root (modulo 11).
is a primitive root (modulo 11).
is a primitive root (modulo 11).
is a primitive root (modulo 11).

So, $2$, $6$, $7$, and $8$ are all primitive roots of $\mathbb{F}_{11}$.

Let’s check that powers indeed give us all elements of $\mathbb{F}_{11}^{\times} = \{1, 2, 3, \ldots, 10\}$:

for i in [2, 6, 7, 8]:
    powers = sorted(Mod(i, 11)^x for x in range(10))
    print(f"{i}: {powers}")

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Also, note that we need the modulus to be prime! For instance, $\mathbb{Z}/8\mathbb{Z}$ has no primitive element. We have that $\varphi(8) = \varphi(2^3) = (2-1) \cdot 2^2 = 4$, and $(\mathbb{Z}/8\mathbb{Z})^{\times} = \{1, 3, 5, 7\}$, but:

for i in [1, 3, 5, 7]:
    print(f"Order of {i} is {Mod(i, 8).multiplicative_order()}")

Order of 1 is 1
Order of 3 is 2
Order of 5 is 2
Order of 7 is 2

So, no element of order $4$.

Powers in \mathbb{Z}/m\mathbb{Z}

Contents

5. Powers in \(\mathbb{Z}/m\mathbb{Z}\)#

5.1. Bases and Binary Numbers#

5.1.1. Converting Bases#

5.2. Fast Powering#

5.3. Negative Powers#

5.4. The Euler \(\varphi\)-Function#

5.5. Reducing Powers#

5.6. Order of Units#

5.6.1. Orders of Powers#

5.6.2. Computing Successive Powers#

5.7. Primitive Roots#