Section 9.1 Groups and Number Systems
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
is a group under addition. As an example, (mod ) has a solution.Namely, we use the (group) inverse,
to solve it, so thatis the solution.
-
Similarly, we can solve equations like
over the rational numbers. Why? Because has a (group) inverse in the group (under multiplication), namely anddoes indeed solve this equation.
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)
xxxxxxxxxx
mod(43*742,997)
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 likeDefinition 9.1.2.
We let
Example 9.1.3.
Before going on, figure out for yourself the elements of
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.6 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 1 . 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,
are the units.-
More unusual is the set of complex numbers (!), which are all units (except zero). In fact, the inverse of
is And
is the set of all the integers modulo that have multiplicative inverses. By our previous investigations, we know this is when (mod ) has a solution. Since multiplication is the operation, there are inverses!
xxxxxxxxxx
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()