Exploring U(n): Inverses Unveiled

1. The Challenge of Multiplicative Inverses in ${\mathbb{Z}}_n$

In the additive world of $({\mathbb{Z}}_n,+)$, every element has an inverse. Does the same hold true for multiplication? Let's investigate. A multiplicative inverse of an element $a$ is an element $b$ such that $a\cdot b\equiv 1(\mathrm{mod}n)$.

Not all non-zero elements in ${\mathbb{Z}}_n$ have a multiplicative inverse. For example, in ${\mathbb{Z}}_8$, is there an element $b$ such that $2\cdot b\equiv 1(\mathrm{mod}8)$? Trying all possibilities:

• $2\cdot 1=2$
• $2\cdot 2=4$
• $2\cdot 3=6$
• $2\cdot 4=8\equiv 0$
• $2\cdot 5=10\equiv 2$
• $2\cdot 6=12\equiv 4$
• $2\cdot 7=14\equiv 6$

None of these products is 1. So, 2 has no multiplicative inverse in ${\mathbb{Z}}_8$. Because of this, the set ${\mathbb{Z}}_8$ with multiplication cannot form a group.

This raises the question: can we form a group by considering only the elements that do have multiplicative inverses?

2. Identifying the Group of Units, U(n)

As the video demonstrated, the elements that have multiplicative inverses are precisely those that are relatively prime to the modulus $n$. This set of elements is called the group of units of ${\mathbb{Z}}_n$, denoted U(n).

Definition: The group of units U(n) is the set of all integers $m$ such that $1\le m<n$ and $\gcd (m,n)=1$. The group operation is multiplication modulo $n$.

For ${\mathbb{Z}}_8$, we find the integers $m$ where $\gcd (m,8)=1$:

• $\gcd (1,8)=1$
• $\gcd (2,8)=2$
• $\gcd (3,8)=1$
• $\gcd (4,8)=4$
• $\gcd (5,8)=1$
• $\gcd (6,8)=2$
• $\gcd (7,8)=1$

Thus, the elements of the group of units of ${\mathbb{Z}}_8$ are $U(8)=\{1,3,5,7\}$.

The video (Abstract Algebra 1) Units Modulo n goes on to construct the multiplication table for $U(8)$ and verify that it satisfies the four group axioms (Closure, Associativity, Identity, and Inverses).

The key takeaway is that the existence of a multiplicative inverse for an element $a$ in ${\mathbb{Z}}_n$ is equivalent to the condition $\gcd (a,n)=1$. This is a fundamental theorem of number theory.

3. Computing Multiplicative Inverses

We know when an inverse exists, but how do we find it? The tool for this comes from a result we saw in a previous lesson: Bezout's Identity.

Recall that for any two integers $a$ and $n$, there exist integers $x$ and $y$ such that:

If an element $a$ is in $U(n)$, we know $\gcd (a,n)=1$. So, for some integers $x$ and $y$, we have:

Now, let's consider this equation modulo $n$. The second term, $ny$, is a multiple of $n$, so $ny\equiv 0(\mathrm{mod}n)$. This simplifies the equation to:

This is exactly the definition of a multiplicative inverse! The integer $x$ is the multiplicative inverse of $a$ modulo $n$.

The practical algorithm for finding these integers $x$ and $y$ is the Extended Euclidean Algorithm. The following resource explains how to use it. Given your interest in coding, you'll be pleased to see it also provides a Python implementation.

Let's walk through an example to solidify the computation.

Problem: Find the multiplicative inverse of 7 in $U(26)$.

First, we check that the inverse exists: $\gcd (7,26)=1$, so it does. We use the Euclidean Algorithm to find the GCD, keeping track of the equations:

1. $26=3\cdot 7+5$
2. $7=1\cdot 5+2$
3. $5=2\cdot 2+1$ (The GCD is 1)

Now, we work backwards, solving for the remainder at each step and substituting upwards.

From step (3), solve for 1:

From step (2), solve for 2 ($2=7-1\cdot 5$) and substitute it into the equation above:

From step (1), solve for 5 ($5=26-3\cdot 7$) and substitute it into our current equation:

Finally, combine the terms for 7 and 26:

This is now in the form $1=y\cdot n+x\cdot a$. Specifically, $1=(3)(26)+(-11)(7)$.
The coefficient of 7 is -11. So, the inverse of 7 is -11. To get a value in $U(26)$, we find $-11(\mathrm{mod}26)$, which is 15.

Therefore, the multiplicative inverse of 7 in $U(26)$ is 15.
We can check: $7\cdot 15=105$. And $105=4\cdot 26+1$, so $105\equiv 1(\mathrm{mod}26)$.

Conclusion

This lesson concludes our foundational module on number theory. We've come full circle, from basic concepts like the division algorithm and GCD to constructing algebraic groups from the integers modulo $n$.

Key Takeaways:

• An element $a\in {\mathbb{Z}}_n$ has a multiplicative inverse if and only if $\gcd (a,n)=1$.
• The set of such elements forms the group of units, U(n), under multiplication modulo $n$.
• The Extended Euclidean Algorithm is the computational method used to find the multiplicative inverse of an element. It is a direct application of Bezout's Identity.

Preview of the Next Module:
We have now encountered two primary examples of finite groups: the additive group $({\mathbb{Z}}_n,+)$ and the multiplicative group $(U(n),\cdot )$. In the next module, we will abstract away from these specific examples to formally define what a group is. We will explore the group axioms in detail and encounter new types of groups, including groups of matrices and permutations. Your background in linear algebra will be particularly useful as we begin to study matrix groups.