# Proof of lemma 1 Paillier encryption

In the original paper of Paillier, lemma 1 shows why $$n$$ must divide the order of $$g$$. What I don't understand in the proof of this lemma is why $$g^{x_2-x_1}(y_2/y_1)^n$$ implies $$g^{\lambda(x_2-x_1)}$$. Where does this result come from?

This is obtained by raising to $$\lambda=\lambda(n)$$: since the order of any element in $$\mathbb{Z}_{n^2}$$ divides $$n\cdot\lambda$$, the second part cancels out:
\begin{align} g^{x_1-x_2}\cdot(y_2/y_1)^n=1\bmod{n^2} &\Leftrightarrow\\ g^{(x_1-x_2)\cdot\lambda}\cdot(y_2/y_1)^{n\cdot\lambda}=1\bmod{n^2}&\Leftrightarrow\\ g^{(x_1-x_2)\cdot\lambda}\cdot 1=1\bmod{n^2}&\Leftrightarrow\\ g^{(x_1-x_2)\cdot\lambda}=1\bmod{n^2} \end{align}