Where does the $\varphi(n)$ part of RSA come from? $e d \equiv 1 \pmod{\varphi(n)}$

Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?
$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element.

So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say that $ed-1\equiv\phi(n)$ or $ed\equiv\phi(n)+1$.

So if we look at $m^{ed}\bmod{n}$ well that is just the same as $m^{\phi(n)+1}\bmod{n}$ which is the same as $m^{\phi(n)}m^1\bmod{n}$. But since $\phi(n)$ is the order of the group, we know that $m^{\phi(n)}\equiv 1$ so we have $m^{\phi(n)}m^1\equiv 1m^1\equiv m\bmod{n}$. This proves that decryption works and we were only able to prove it since we chose $d$ accordingly.

If we didn't use $\phi(n)$ the mathematics wouldn't necessarily* work out and decryption would not be guaranteed to work. So, the designers of RSA used $\phi(n)$ out of necessity.


*See the comment by fgrieu. Any multiple of $LCM(p-1,q-1)$ would work.