# Why is asked that gcd(pq,(p-1)(q-1))=1 in the Paillier encryption scheme?

I don't see this property $$\gcd(p\,q,(p-1)(q-1))=1$$ used in the scheme. And in Paillier's original paper, I don't find this requirement.

Is it required just for the difficulty of factoring $$n$$?
Or is it related to the specific security of Paillier Encryption?

• Hint: the condition (or rather, an equivalent one) is in Paillier's paper, in "Since $\gcd(\lambda,n)=1$" in the proof of Lemma 3. What happens if this condition is not met (and proving that the probability of that is extremely low for a conventionally generated RSA modulus $n$) is left to an answer (that I do not plan to write) to an interesting question. Also, if someone can spot the justification for the "Since" rather than Further assuming the overwhelmingly likely condition, I want to know.
– fgrieu
Sep 29 at 4:44
• $gcd(\lambda,n)=1$ and $gcd(n,(p-1)(q-1)=1$ implies each other, so they are equivalent. However, I still don't know why it is required. Since in wiki, $g$ is not generated as in Paillier's paper. Sep 29 at 7:08
• Does anyone know where the wiki version comes from? Sep 29 at 7:41
• Extra hint: if we take the artificially small example of $p=23$, $q=47$, $n=1081$, there is the problem that $1^n\equiv24^n\pmod{n^2}$, hence whatever $g$ we choose the function $\varepsilon_g:\mathbb Z_n\times\mathbb Z_n^*\to\mathbb Z_{n^2}^*$ defined by $(x,y)\mapsto x^g y^n\bmod n^2$ will collide.
– fgrieu
Sep 29 at 10:49