Invertible Numbers Modulo N

A number $ a $ is invertible modulo $ n $ if there exists a number $ b $ such that: \[ a \cdot b \equiv 1 \pmod{n} \]

Invertible numbers modulo $ n $ are those that have a multiplicative inverse in modular arithmetic.

In other words, multiplying $ a $ by $ b $ results in a remainder of 1 when divided by $ n $. In this case, $ b $ is called the multiplicative inverse of $ a $ modulo $ n $.

Such an inverse exists only if $ a $ is coprime (relatively prime) with $ n $, meaning the greatest common divisor (GCD) of $ a $ and $ n $ is 1:

$$ \gcd(a, n) = 1 $$

Note: The total number of invertible elements modulo $ n $ is given by Euler's totient function $ \varphi(n) $, which counts the integers from 1 to $ n $ that are coprime to $ n $. Furthermore, these invertible numbers form a multiplicative group, denoted $ U(\mathbb{Z}_n) $. Within this group, we also find primitive roots modulo $ n $, which are numbers whose powers generate the entire group.

A Practical Example

Let’s examine the case where $ n = 7 $. Which numbers are invertible?

We look for multiplicative inverses among the numbers from 0 to 6:

$ 0 $ is never invertible since $ 0 \cdot x \equiv 0 \pmod{7} $ for any $ x \in [0,6] $.
$ 1 $ is invertible since $ 1 \cdot 1 \equiv 1 \pmod{7} $, meaning its own inverse is itself.
$ 2 $ is invertible because $ 2 \cdot 4 \equiv 8 \equiv 1 \pmod{7} $, so 2 and 4 are multiplicative inverses of each other.
$ 3 $ is invertible because $ 3 \cdot 5 \equiv 15 \equiv 1 \pmod{7} $, so 3 and 5 are multiplicative inverses of each other.
$ 4 $ is invertible since $ 4 \cdot 2 \equiv 8 \equiv 1 \pmod{7} $ (already noted).
$ 5 $ is invertible since $ 5 \cdot 3 \equiv 15 \equiv 1 \pmod{7} $ (already noted).
$ 6 $ is invertible because $ 6 \cdot 6 \equiv 36 \equiv 1 \pmod{7} $.

It’s worth noting that zero is never invertible, which is why it’s typically excluded from consideration.

Thus, the invertible numbers modulo 7 are:

$$ U(\mathbb{Z}_7) = \{1, 2, 3, 4, 5, 6\} $$

These numbers form the multiplicative group modulo 7.

Among them, some play a special role—they are known as "primitive roots modulo $ n $," meaning their powers generate the entire group.

For example, 2 is not a primitive root because its powers fail to produce all numbers in the group: $$ 2^1 = 2 \pmod{7} \\ 2^2 = 4 \pmod{7} \\ 2^3 = 8 \equiv 1 \pmod{7} $$ By contrast, 3 is a primitive root modulo 7 because its powers generate every element in the group: $$ 3^1 = 3 \pmod{7} \\ 3^2 = 9 \equiv 2 \pmod{7} \\ 3^3 = 27 \equiv 6 \pmod{7} \\ 3^4 = 3^2 \cdot 3^2 = 9 \cdot 9 = 81 \equiv 4 \pmod{7} \\ 3^5 = 3^3 \cdot 3^2 = 6 \cdot 9 = 54 \equiv 5 \pmod{7} \\ 3^6 = 3^3 \cdot 3^3 = 6 \cdot 6 = 36 \equiv 1 \pmod{7} $$

Example 2

Now let’s determine the invertible numbers modulo 14.

A number $ a $ is invertible if and only if it is coprime with 14, meaning $ \gcd(a, 14) = 1 $. In other words, $ a $ must not share any common divisors with 14 other than 1.

The numbers from 1 to 13 are:

\[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 \]

Next, we eliminate those that are not coprime with 14.

Since 14 is divisible by 2 and 7, any number that shares a factor with 14 is not invertible modulo 14.

2, 4, 6, 8, 10, and 12 are all divisible by 2, so they are not invertible modulo 14.
7 is divisible by 7, so it is not invertible modulo 14.

The remaining numbers are the ones that are invertible modulo 14:

\[ U(\mathbb{Z}_{14}) = \{1, 3, 5, 9, 11, 13\} \]

These elements form the multiplicative group modulo 14. This is where primitive roots come into play—a primitive root is a number whose powers generate all the elements of this group.

For example, in the case of modulo 14, one primitive root is $ r = 5 $ because its successive powers generate all the invertible numbers modulo 14: \[ 5^1 \equiv 5 \pmod{14} \\ 5^2 \equiv 11 \pmod{14} \\ 5^3 \equiv 13 \pmod{14} \\ 5^4 \equiv 9 \pmod{14} \\ 5^5 \equiv 3 \pmod{14} \\ 5^6 \equiv 1 \pmod{14} \] After six iterations, the sequence cycles back to 1. Other primitive roots include $ r = 3 $ and $ r = 5 $. Conversely, the numbers $ r = 9 $, $ r = 11 $, and $ r = 13 $ are not primitive roots modulo 14 because their powers fail to generate the entire set of invertible elements. For instance, the powers of $ r = 9 $ produce only three distinct values: \[ 9^1 \equiv 9 \pmod{14} \\ 9^2 = 81 \equiv 11 \pmod{14} \\ 9^3 = 9^2 \cdot 9^1 = 11 \cdot 9 = 99 \equiv 1 \pmod{14} \] Since this sequence cycles back to 1 after just three steps, it does not generate all elements of $ U(\mathbb{Z}_{14}) $, confirming that 9 is not a primitive root.

And so on.