Paillier paper: Number Theoretic Lemma doesn't seem to work I'm reading the original Paillier paper.

I've reached Lemma 3: If the order of $g$ is a nonzero multiple of $n$, then $\varepsilon_g(x,y) = g^x y^n \mod n^2$ is a bijection, where $x \in \mathbb{Z}_n$ and $y \in \mathbb{Z}_n^*$.

Take for example $n=6$, $n^2=36, \mathbb{Z}_6^* = \{1, 5\}$.

Let $g=5$. The order of $5$ modulo $36$ is $6$ (see WolframAlpha), which is a multiple of $6$, so $\varepsilon_g$ should be a bijection. 

Let $(x_1, y_1) = (1, 1)$ and $(x_2, y_2) = (1, 5)$. Then:


$y_1, y_2 \in \mathbb{Z}_6^*$ as required.
$\varepsilon(x_1, y_1) = 5^1 \cdot 1^6 = 5$
$\varepsilon(x_2, y_2) = 5^1 \cdot 5^6 = 5$ (assuming operations are modulo $36$.)


So... It's not a bijection. Am I missing something?
Short answer: This appears to be an error in the paper, but it's not a problem in practice.

The proof of Lemma 3 uses the following implication:


  Since $\gcd(\lambda,n)=1$, $x_2-x_1$ is necessarily a multiple of $n$. Consequently, $x_2-x_1=0\bmod n$ and $(y_2/y_1)^n=1\bmod n^2$, which leads to the unique solution $y_2/y_1=1$ over $\mathbb Z_n^\ast$.


As your example shows, the assertion $\gcd(\lambda,n)=1$ is wrong in general: $n=2\cdot 3$, hence $\lambda=(2-1)\cdot(3-1)=2$, and $\gcd(\lambda,n)=2\neq1$. Structurally, this becomes manifest in the fact that the ring $\mathbb Z/n^2$ contains nontrivial $n$th roots of unity — in your case the element $5$ — which voids the uniqueness claim.

It is not hard to prove that for $n=pq$ a product of two primes, this phenomenon occurs if and only if $p=2$ or $q=2kp+1$ for some $k\in\mathbb N$. (Modulo reordering of $p$ and $q$.)
The chance of this happening is negligible for any realistically-sized and randomly generated pair of primes $(p,q)$, hence this is not going to be an issue in practice.