NTIC Groups and Number Systems

🔗

Section 9.1 Groups and Number Systems

🔗

There is a lot that the integers modulo

$n$ can teach us. We can approach new horizons by rethinking the problems we have just studied.

🔗

Subsection 9.1.1 Solving linear equations – again

🔗

What is a group, again? As we saw in Section 8.3, a group is any ‘number system’ where we can solve linear equations.

🔗

Example 9.1.1.

Here are some familiar group examples.

The integers modulo $n\text{,}$ $\mathbb{Z}_n\text{,}$ is a group under addition. As an example, $3+x\equiv 2$ (mod $4$ ) has a solution.

Namely, we use the (group) inverse, $-3\equiv 1\text{,}$ to solve it, so that

$\begin{equation*} x\equiv 2+(-3)\equiv 2+1\equiv 3\text{ (mod }4\text{)} \end{equation*}$

is the solution.
Similarly, we can solve equations like $\frac{2}{3}\cdot x=5$ over the rational numbers. Why? Because $\frac{2}{3}$ has a (group) inverse in the group $\mathbb{Q}\setminus\{0\}$ (under multiplication), namely $\left(\frac{2}{3}\right)^{-1}=\frac{3}{2}\text{,}$ and

$\begin{equation*} x=5\cdot\frac{3}{2} \end{equation*}$

does indeed solve this equation.

🔗

Let us use this idea to help us with solving congruences modulo

$n\text{.}$ Using the above framework, I should be able to solve

$\begin{equation*} 43x\equiv 2\text{ (mod }997) \end{equation*}$

🔗

by using something like

$a=43^{-1}\text{,}$ the notation we saw before.

🔗

That would get us

$\begin{equation*} x\equiv 2a\equiv 2\cdot 43^{-1}\text{ (mod }997)\text{.} \end{equation*}$

🔗

Let's try this in Sage.

xxxxxxxxxx
 
a=mod(43,997)
x=2*a^-1
print("a is %s"%a)
print("a^-1 is %s"%a^-1)
print("2a^-1 is %s"%x)

🔗

This checks out, of course:

xxxxxxxxxx
 
mod(43*742,997)

🔗

We can similarly try to solve with a composite modulus:

$\begin{equation*} 53y\equiv 29\text{ (mod }100) \end{equation*}$

🔗

using

$b=53^{-1}\text{,}$ so that

$\begin{equation*} y\equiv 29\cdot b\equiv 29\cdot 53^{-1}\text{ (mod }100)\text{.} \end{equation*}$

xxxxxxxxxx
 
y=29*mod(53,100)^-1
print("y is %s"%y)

xxxxxxxxxx
 
y=29*mod(53,100)^-1
53*y

🔗

Subsection 9.1.2 A new group

🔗

Subsubsection 9.1.2.1 The group of units

🔗

So solving this should often be possible. But it can't always work, otherwise I could use it to solve something like

$\begin{equation*} 52y\equiv 29\text{ (mod }100) \end{equation*}$

🔗

and we already know this does not have a solution. We can't just use this idea willy-nilly; indeed, there isn't a

$52^{-1}$ in this case.

🔗

Hence we introduce a new group – and it's even a simple set to define.

🔗

Definition 9.1.2.

We let $U_n\text{,}$ the group of units modulo $n$ , be the set of equivalence classes $[a]$ modulo $n$ such that $\gcd(a,n)=1\text{.}$

🔗

This will be the set where we are allowed to do inverses, and hence to solve things easily. Recall Definition 5.3.3 and Question 5.3.5.

🔗

Example 9.1.3.

Before going on, figure out for yourself the elements of $U_5$ and $U_{8}\text{.}$

🔗

Now, naming something doesn't guarantee it's useful, or that it performs as claimed! So we need to check some things from Definition 8.3.3.

🔗

Proposition 9.1.4.

The group of units is really a group.

🔗

Proof.

First, this is certainly a set. Since we earlier proved that any two elements of a residue class have the same gcd with a modulus, the definition makes sense, and we know how to check if something is in it.

Next, the set is associative with respect to multiplication, because it's really the same as multiplication over $\mathbb{Z}\text{.}$ The identity element $[1]$ is likewise inherited from $\mathbb{Z}\text{.}$ We have inverses because we only allow elements that will have solutions to $ax\equiv 1$ according to Proposition 5.1.1; see also Question 5.3.5 and Exercise 5.6.5.

Finally, we do need to check whether the multiplication is closed on this set. After all, it's not obvious that if $ax\equiv 1$ and $bx\equiv 1$ have solutions, then so does $(ab)x\equiv 1\text{!}$ But if $\gcd(a,n)$ and $\gcd(b,n)$ are both $1\text{,}$ then $ab$ will also be coprime to $n\text{,}$ which is all that is needed. All in all, that means $U_n$ really and truly is a group.

🔗

Subsubsection 9.1.2.2 More facts and examples

🔗

The terminology units makes sense too. If you are in a number system with addition and multiplication, then a unit is an element that has a multiplicative inverse.

🔗

Example 9.1.5.

Here are some examples of units.

In the integers, $\pm 1$ are the units.
More unusual is the set of complex numbers (!), which are all units (except zero). In fact, the inverse of $r\left(\cos(\theta)+i\sin(\theta)\right)$ is

$\begin{equation*} \frac{1}{r}\left(\cos(-\theta)+i\sin(-\theta)\right)\text{.} \end{equation*}$
And $U_n$ is the set of all the integers modulo $n$ that have multiplicative inverses. By our previous investigations, we know this is when $ax\equiv 1$ (mod $n$ ) has a solution. Since multiplication is the operation, there are inverses!

🔗

Naturally, it can take a while to list all the elements of

$U_n\text{,}$ but it's worth doing. Try it for

$n=10\text{,}$

$n=11\text{,}$ and

$n=12$ by hand (see Exercise 9.6.1).

🔗

Sage has commands to list the group of units and give the order of the group. Try them interactively here, or individually below.

xxxxxxxxxx
 
@interact
def _(n=22):
    pretty_print(html("The units of $\\mathbb{Z}_{%s}$ are"%n))
    pretty_print(html( Integers(n).list_of_elements_of_multiplicative_group()) )
    pretty_print(html("There are $%s$ of them."%Integers(n).unit_group_order()))

🔗

Sage note 9.1.6. Reminder to try things out.

Remember, you can use these yourself by using these commands, or by cutting and pasting them in a Sage or Jupyter notebook, CoCalc, or command line interface. They are tedious to type, though!

xxxxxxxxxx
 
Integers(50).list_of_elements_of_multiplicative_group()

xxxxxxxxxx
 
Integers(50).unit_group_order()