SIDE QUEST: Cyclic Groups

(A thing Quantum Computers do well)

SIDE SIDE (the mental roadmap):

Let's feel cyclic groups by looking at $2, 2^2, 2^3, 2^4, \ldots $ and just finding patterns
Quickly say what a group is: identity, closure, and inverse (ok associative but whatever)
Revisit the cycles but now look at $3*2, 3*2^1, 3*2^2, 3*2^3, \ldots $
Demo that any Group has cycles and these shadow-cycles (called cosets)
So, intuitively, the size of any cycle HAS TO DIVIDE the size of its group
So, intuitively, any element raised to the size of the group must get be 1
OK so how big is the group of numbers mod $N$?
Any number that has a factor in common with $N$ can be used to kill $N$.
When does a number $a$ have an inverse, $a^{-1}$ so $a^{-1} \cdot a \equiv 1$ mod $N$?
Now it's clear that the group of numbers mod $N$ has $\phi(N)$ numbers.
Now it's clear that $a ^ {\phi(N)} \equiv 1$
For numbers mod $p$ (Diffie-Hellman) $\phi(p) = p-1$ for RSA $\phi(p\cdot q) = (p-1)\cdot(q-1)$

Let's learn this stuff by playing, only put in a symbol/variable AFTER playing with actual numbers.

A set of numbers and some way to combine them (e.g. integers mod 12 and multiplication) that do the following:

CLOSURECombine any two things in the set and get something in the set
IDENTITY One element in the set should combine with ANY OTHER and return that OTHER number
INVERSE Each element should have an inverse which combine to get the identity
(ASSOCIATIVE) If you combine a with b and that with c it should be the same as combining a after combining b and c

OK so any 0 in a cycle will kill the cycle. You know, 0*anything...

Now imagine the modulus is 15. Then the number 6 is dangerous.

A dumb analogy is like 15 is a person with two vices and 6 shares one of those vices.

If 6 starts hanging around there's a chance 15 gets into trouble...

Math wise it goes like this:

$$\text{GCD}(x,y) = d\text{ if and only if }d=\text{min}(a \cdot x+b \cdot y \forall a,b)$$

This is math-y looking, here's what it says as a human.

Any number that divides both 35 and 77 has to divide any combination of them, like $3 \cdot 35 - 9 \cdot 77 $

If you play with those combinations long enough you will get the largest divisor of both 35 and 77.

Here's a beautiful wikipedia animation:

OK SO... imagine that $ \text{GCD}(x,y) = 1 $ then there is some magic combination of them like:

$$ 1 = a \cdot x + b \cdot y $$

OK cool, then look at that mod $y$ and you get $a$ is the inverse of $x \text{mod} y$.

So in essence a number ONLY has an inverse if the GCD of that number and the modulus is 1.