Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section9.1Groups 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.

Subsection9.1.1Solving 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.

Example9.1.1

Here are some familiar group examples.

  • The integers modulo \(n\), \(\mathbb{Z}_n\), 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\), 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}\), 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\). 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}\), the notation we saw before.

That would get us \begin{equation*}x\equiv 2a\equiv 2\cdot 43^{-1}\text{ (mod }997)\; .\end{equation*} Let's try this in Sage.

This checks out, of course:

We can similarly try to solve with a composite modulus: \begin{equation*}53y\equiv 29\text{ (mod }100)\end{equation*} using \(b=53^{-1}\), so that \begin{equation*}y\equiv 29\cdot b\equiv 29\cdot 53^{-1}\text{ (mod }100)\, .\end{equation*}

Subsection9.1.2A new group

Subsubsection9.1.2.1The 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.

Definition9.1.2

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

This will be the set where we are allowed to do inverses, and hence to solve things easily. Before going on, figure out for yourself the elements of \(U_5\) and \(U_{8}\).

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.

Proof

We can even give a formula of sorts for the inverse (this should work in any group).

Proof

Subsubsection9.1.2.2More 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.

Example9.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 all are units except 0. (In fact, the inverse of \(r\left(\cos(\theta)+i\sin(\theta)\right)\) is \(\frac{1}{r}\left(\cos(-\theta)+i\sin(-\theta)\right)\).).

  • 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 these guys, but it's worth doing. Try it for \(n=10\), \(n=11\), and \(n=12\) by hand.

Sage has commands to list the group of units and give the order of the group.

Sage note9.1.6Reminder to try things out

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