ed ≡ 1 modλ(n) stuck Given $p = nq$, $n \not\equiv q$, and
$\forall m: m ≡ m^{ed} \bmod n$, how can we show that $ed \equiv 1 \bmod \lambda(n)$?
My idea was to show it using the $k$ exponent, but I got stuck.
So:

From Fermat's Little Theorem we know, that
 $$ m^p = m \bmod p $$
 $ m^{\lambda(n)} = 1 \bmod n$ (Carmichael theorem)

$$\forall m, m^k \equiv 1 \bmod n$$
 so I add $k$:
 $$m^{\lambda(n) \cdot k} \equiv 1 \bmod n$$

In other words:  $$m^{kλ(n)+1} \equiv m \bmod n$$
 $$ed = k\lambda(n)+1$$ so:
 $$m^{ed} = m \bmod n$$
How then do I show that $ed \equiv 1 \bmod \lambda(n)$?
Given $n=pq$ and $\forall m: m ≡ m^{ed} \bmod n$, how can we show that $ed \equiv 1 \pmod {\lambda(n)}$?


Well, the most straightforward approach is first to show that we must have both:

$$ed \equiv 1 \pmod{p-1}$$

$$ed \equiv 1 \pmod{q-1}$$

We can combine these equivalancies into one, using the Chinese Remainder Theorem; however as $p-1$ and $q-1$ are not relatively prime, we get:

$$ed \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$$

This turns out to be a necessary and sufficient condition.  Sometimes, we denote $\lambda(pq) = \text{lcm}(p-1, q-1)$; you'll sometimes see this formulation.