Before we get to groups, there is something to remind you of. Namely, you never did see a pattern with the prime $p$ such that $$x^2\equiv 1\text{ mod }(p)$$ has a solution! So let's see this table and see if you can find something.
Click to the left again to hide and once more to show the dynamic interactive window 
Proving this will be HW! As will something similar for $x^2+y^2=p$ for such primes $p$.
The reason I point this out is not just because I can, but because it shows simple congruence patterns can have a big result. Recall our search through Mordell/Bachet curves, and let's look at the particular case $y^2=x^3+7$.
Click to the left again to hide and once more to show the dynamic interactive window 
Thus it seems that a perfect square can't ever be exactly seven more than a perfect cube. Is this true? Here's where congruences come into play.
What kind of $x$ could solve $y^2=x^3+7$?
[0, 1, 4, 1, 0, 1, 4, 1] [0, 1, 4, 1, 0, 1, 4, 1] 
I hope that seems cool enough! Congruences are amazingly powerful. So let's make them even more powerful, and bring groups into play.
Next business is to recall what a group is. In short, a group is any "number system" where we can solve linear equations.
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, because $\frac{2}{3}$ has a (group) inverse in the group $\mathbb{Q}\setminus\{0\}$, $(\frac{2}{3})^{1}=\frac{3}{2}$, and $$x=5\cdot\frac{3}{2}$$ does indeed solve this equation.
Now we will 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)\; .$$ And below, if I just do the naive thing in Sage, I get the following:
a is 43 a^{1} is 371 2a^{1} is 742 a is 43 a^{1} is 371 2a^{1} is 742 
This checks out, of course:
2 2 
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)\, .$$
y is 93 y is 93 
29 29 
So this should often be possible. But it can't always work, otherwise I could use it to solve something like $52y\equiv 29$ 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 willynilly.
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.
Now, naming something doesn't guarantee it's useful, or that it performs as claimed! So we need to check some things.
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.
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)$.).
So $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. Try it for $n=10$, $n=11$, and $n=12$ by hand.
It turns out that Sage has commands to list the group of units and give the order of the group.
Click to the left again to hide and once more to show the dynamic interactive window 
You can use these yourself by doing the commands below as well, though they are a little long to type out! (There is a new command for going straight to them in the works, but it gives away some of our investigation, so I am choosing not to use it.)
[1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49] [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49] 
20 20 
We give the size of the group of units mod ($n$) a special name.
This is the socalled Euler $\phi$ function. It can also be written phi, it is pronounced 'fee', and it's occasionally notated $\varphi$ just for fun. Do you see any patterns on the value of $\phi(n)$? Let's take some time to inspect this.
Now, so far this is a relatively abstract concept. What follows is not abstract at all, but very, very useful!
Thus Lagrange's Theorem nearly immediately gives us one of Euler's many celebrated Theorems:
Euler's Theorem: If $gcd(a,n)=1$, then $a^{\phi(n)}\equiv 1$ mod ($n$).
If you guessed well on patterns in $\phi(n)$, you should see how to recover Fermat's Little Theorem from this.
We can use this to compute, too. One has to be just a little clever to use it to compute inverses mod $(n)$. If $$a^{\phi(n)}\equiv 1\text{ mod }(n)\; ,$$ then certainly multiplying both sides by $a^{1}$ yields $$a^{\phi(n)1}\equiv a^{1}\text{ mod }(n)\; .$$ We can check this using Sage.
Click to the left again to hide and once more to show the dynamic interactive window 
So to solve things like $$53y\equiv 29\text{ mod }(100)$$ from earlier, we could in theory multiply both sides by the inverse of 53 in this form, or $$y\equiv 29\cdot 53^{\phi(100)1}\text{ mod }(100)\; .$$ This would look like the following in Sage.
93 93 
This answer jells with our previous calculation. And now I didn't have to solve a different linear congruence in order to solve my original one; I just have to have a way to do multiplication mod $(n)$.
Notice that Sage has a command to get $\phi(n)$, namely $\verb+euler_phi(n)+$. This is much easier to use, but doesn't have the direct connection that $\verb+Integers(n).unit_group_order()+$ does, of course.
Our final use of this for today is again computational. Namely, it turns out that we can use this to do Chinese Remainder Theorem systems much more easily, as long as we have access to $\phi$.
Remember that in the algorithm for the CRT, where we tried to solve systems like
There, we had to calculate many solutions to congruences of the form $$\frac{N}{n_i}x\equiv 1\text{ mod }(n_i)\; .$$ (This was to get the $d_i$ numbers.) Our new information means that this inverse is just $$\left(\frac{N}{n_i}\right)^{1}\equiv \left(\frac{N}{n_i}\right)^{\phi(n_i)1}\; ,$$ since we are looking at a congruence modulo $n_i$. So the things in the final solution which looked like $$a_i\cdot \frac{N}{n_i}\cdot \left(\frac{N}{n_i}\right)^{1}$$ can be thought of as $$a_i\cdot \frac{N}{n_i}\cdot \left(\frac{N}{n_i}\right)^{\phi(n_i)1}=a_i\left(\frac{N}{n_i}\right)^{\phi(n_i)}\; ,$$ which is much cooler and simpler! So the answer to the general system is just $$x\equiv \sum_{i=1}^k a_i \Big(\frac{N}{n_i}\Big)^{\phi(n_i)}\, .$$
210 210 
206 206 
It's possible to do it more concisely if you know a little Python and something called 'list comprehension'.
206 206 
But that's not necessary for our purposes.
We can do this one step even better. Take a huge system like
Can we find solutions for this using the same mechanism? Yes, and without too much difficulty now.
Since one can solve $bx\equiv c$ mod ($n$) with $$x\equiv b^{\phi(n)1}\cdot c\; ,$$ any likely system of congruences with coprime moduli $$b_i x\equiv c_i\text{ mod }(n_i)$$ where $N$ is the product of the moduli could be solved by $$x\equiv \sum_{i=1}^k \left(b_i^{\phi(n_i)1}c_i\right)\left(\frac{N}{n_i}\right)^{\phi(n_i)}\text{ mod }(N)\, .$$ Let's use this to solve the system above,
79 79 
Notice that we make as much stuff modulo $M$ to begin with as possible. Even for bigger numbers, asking Sage to first make things modular is a big help  it takes essentially no time! We can demonstrate this with a much larger example, picking essentially random large primes to compute with.
Our primes are 2753, 577, and 6427 6752297785 CPU time: 0.01 s, Wall time: 0.01 s Our primes are 2753, 577, and 6427 6752297785 CPU time: 0.01 s, Wall time: 0.01 s 
Our primes are 29019637, 19020247, and 180032459 57792586318644815467045 CPU time: 0.01 s, Wall time: 0.01 s Our primes are 29019637, 19020247, and 180032459 57792586318644815467045 CPU time: 0.01 s, Wall time: 0.01 s 
Homework for Monday  not handed in, but many likely to reappear for handing in Wednesday!
