Relation between $N = P \times Q$, and $\Phi(N)$ When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem.

I did understand how from invertible finite groups I could derive Euler's theorem and Fermat's little theorem, etc. But one point remained...

When extracting the invertibles from $N \rightarrow U(N)$, we get the elements which form a group. I also saw that the order of any element in that belongs to $U(N)$, which is the order of $U(N)$. For example, if the number $10$ is $N$, $1,3,7,9$, it forms a group under multiplication $\bmod 10$. Now any element $a$, let it be $7$, the order of $7$, is $4$, which is also the sum total of the co-primes or the order of $U(N)$. This proves Euler's theorem, and thus, Fermat's as well. But when doing RSA, we do the same thing; however,  during key generation, we choose a number that is a co-prime to the order of $U(N)$, which also does from an invertible group $1$ and $4$.

Therein lies the rub, which I don't understand at this moment. What does the order of $U(N)$ have to do with key generation?

I have been unable to find a direct visual link. Ultimately, we are not choosing an element $E$ that belongs to $U(N)$, but an element that forms a group under $U|U(N)|$. And again, when encrypting, we are doing $M^{ed} \bmod N$.

I am not getting the relation between $U(N)$ and the number of elements in $U(N)$ when we are not using the order as an exponent to any element within $U(N)$ to get $1$ or something like that. Why are we generating the key from the number of elements in $U(N)$, and why does it work? What's the relation?
What does the order of $U(N)$ has to do with RSA key generation?


The usual notation is $\Bbb Z_N^*$ for the multiplicative group modulo $N$, that the question names $U(N)$, and $\Phi(N)$ or equivalently $\varphi(N)$ for its order (number of elements), as given by Euler's totient function.

$\forall x\in\Bbb Z_N^*$, it holds $x^{\Phi(N)}\equiv1\pmod N$. This implies:
$$\forall x\in\Bbb Z_N^*,\ \forall k\in\Bbb N,\ \text{ it holds }\ x^{(k\,\Phi(N)+1)}\equiv x\pmod N\tag{1}\label{eq1}$$

We want the RSA encryption exponent $e$ and decryption exponent $d$ (both strictly positive integers) to be such that textbook RSA encryption of a plaintext $m$ followed by decryption consistently returns the original plaintext. That is, we want that $\forall m\in[0,N)$, it holds $((m^e)\bmod N)^d\bmod N=m$. We can write this goal as:
$$\forall m\in[0,N),\ \text{ it holds }\ m^{(e\,d)}\bmod N=m\tag{2}\label{eq2}$$

We can now see what $\Phi(N)$ has to do with RSA key generation: if
$$e\,d\equiv 1\bmod\Phi(N)\tag{3}\label{eq3}$$
then by definition of that, and given that $e$ and $d$ are strictly positive integers, $\exists k\in N$ such that $e\,d=k\,\Phi(N)+1$, and we nearly can use $\eqref{eq1}$ to prove that $\eqref{eq2}$ holds. The one gap is that we only prove the weaker
$$\forall m\in[0,N),\ \text{ if }\ \gcd(m,N)=1\ \text{ then }\ m^{(e\,d)}\bmod N=m\tag{2'}\label{eq2'}$$

We have proven that condition $\eqref{eq3}$ is sufficient to insure that textbook RSA encryption of a plaintext $m$ followed by decryption returns the original plaintext, at least when $\gcd(m,N)=1$. Since $N$ is the product of large primes, $\gcd(m,N)=1$ holds for most $m$.



Further, under the extra condition that $N$ is squarefree (including $ N=p\,q$ with $p$ and $q$ distinct primes), it can be proven that for all $m$ textbook RSA encryption followed by decryption returns the original plaintext.

Otherwise said: one way to see RSA is as working with message and ciphertext in the group $(\Bbb Z_N^*,*)$, but that restricts the message space. It can be extended to $(\Bbb Z_N,*)$ when $N$ is squarefree, that is when $N$ is not divisible by the square of any prime.

We first prove that $\eqref{eq3}$ implies that $m^{(ed)}-m\equiv0\pmod{p_i}$ for each prime $p_i$ dividing $N$, by treating separately the case $m\equiv 0\pmod{p_i}$. The integer $m^{(ed)}-m$ is thus divisible by each $p_i$, thus by their product, which is $N$ when $N$ is squarefree, thus $m^{(ed)}-m\equiv0\pmod N$.



Notice that the condition $\eqref{eq3}$ is sufficient, but not necessary. For a necessary and sufficient condition, we want 
$$e\,d\equiv 1\bmod\lambda(N)\tag{3'}\label{eq3'}$$
where $\lambda$ is the Carmichael function.



Notations:


$\forall$ is read "for all". $\in$ is read "in". $\exists$ is read "exists".
$\Bbb N$ is the set of natural numbers: $\Bbb N=\{0,1,2,3,4,5,\ldots\}$.
$\Bbb P$ is the subset of $\Bbb N$ consisting of primes: $\Bbb P=\{2,3,5,7,11,\ldots\}$.
$\Bbb Z$ is the set of (signed) integers: $\Bbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$.
$(\Bbb Z,+)$ is a group.
$x\equiv y\pmod n$ is read "$x$ is equivalent to $y$ modulo $n$".
It means that $n$ exactly divides $x-y$ (for $n$ a strictly positive integer).
Alternative notations are $x\equiv y\ \ [n]$ or $x=y\pmod n$ or $x=y\ \ [n]$.
$x=y\bmod n$ is read "$x$ is set to $y$ modulo $n$" or "$x$ equals $y$ modulo $n$".
It means that (after the setting, if any) $0\le x&lt;n$ and $x\equiv y\pmod n$ (see above for the meaning).
When $y\ge0$, the quantity $y\bmod n$ is the remainder of the Euclidean division of $y$ by $n$. The quantity $y\bmod n$ is $0$ when $n$ divides $y$ (and the C programmer writesx = y % n for a computation orx == y % n for a test). When $y&lt;0$, we can compute $y\bmod n$ as $n-1-((-y-1)\bmod n)$.
Note: Textbook RSA encryption and decryption reduce their result $\bmod N$, ensuring that the ciphertext and the deciphered plaintext are in $[0,N)$. 
$\Bbb Z_n$ is the finite set of integers modulo $n$. That is, the elements of $\Bbb Z$ equivalent modulo $n$ are regrouped into a single element of $\Bbb Z_n$. Thus $\Bbb Z_n$ has $n$ elements.
$(\Bbb Z_n,+)$ is a group. With multiplication noted $*$ when not omitted, it becomes the ring $(\Bbb Z_n,+,*)$.
When the modulo $n$ is prime, $(\Bbb Z_n,+,*)$ is a field, because all elements except $0$ have a multiplicative inverse. As practice of notation: $\forall p\in\Bbb P$, $\forall x\in\Bbb Z_p$, if $x\ne0$ then $\exists y\in\Bbb Z_p$ such that $x*y=1\pmod p$ (also noted $x\,y=1\pmod p$ as a shortcut).
$\Bbb Z_n^*$ is the set of the elements of $\Bbb Z_n$ that have an inverse under multiplication, that is the set of $x$ with $n$ and $x$ having no common positive divisor beyond $1$, that is $\gcd(x,n)=1$.
$(\Bbb Z_n^*,*)$ is a group including when $n$ is not prime. It has $\Phi(n)$ elements.