What is a group, again? In short, a group is any "number system" where we can solve linear equations. Examples:

• So \(\mathbb{Z}_n\) is a group under addition, because \(3+x\equiv 2\) mod (4) has a solution.
  • Namely, we use the (group) inverse, \(-3\equiv 1\), to solve it. so that \[x\equiv 2+(-3)\equiv 2+1\equiv 3\text{ mod }(4)\] 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\}\), namely \(\left(\frac{2}{3}\right)^{-1}=\frac{3}{2}\), and \[x=5\cdot\frac{3}{2}\] 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 \[43x\equiv 2\text{ mod }(997)\] by using something like \(a=43^{-1}\), the notation we saw before.

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

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

So this should often be possible. But it can't always work, otherwise I could use it to solve something like \[52y\equiv 29\text{ mod }(100)\] and we already know this does not have a solution.

There isn't a \(52^{-1}\) in this case, and so we can't just use this idea willy-nilly.

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

This will be the set where we are allowed to do inverses, and hence to solve things easily. Right now, figure out 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.