# Is gcd(e,p−1)=1=gcd(e,q−1) similar to gcd(e,phi(n))=1?

I wonder, is $$\gcd(e,p−1)=1=\gcd(e,q−1)$$ similar to $$\gcd(e,\phi(n))=1$$ ??

• Welcome to Cryptography.se What is the origin of this question? do you know that $\varphi(p\cdot q) = (p-1)(q-1)$ and from there what can you conclude? Nov 12 at 12:19
• Thank you for your clues and the origin question is from this link @fgrieu Nov 12 at 12:52

If $$n=p\,q$$, and $$p$$ and $$q$$ are prime, and $$p\ne q$$, then $$\varphi(p\cdot q) = (p-1)(q-1)$$, from which it follows that for any integer $$e$$, the propositions $$\gcd(e,p-1)=1=\gcd(e,q-1)$$ and $$\gcd(e,\varphi(n))=1$$ are equivalent.
Each of the conditions $$n=p\,q$$, $$p$$ and $$q$$ prime, and $$p\ne q$$, is necessary for the equivalence to hold for all $$e$$. These conditions are standard in RSA. For an example proving that $$p\ne q$$ is necessary, consider $$p=q=e=3$$: it holds $$\gcd(e,p-1)=1=\gcd(e,q-1)$$, but $$\gcd(e,\varphi(9))=\gcd(e,6)=3$$.
When generating an RSA key pair with a desired $$e$$ (which is common), $$\gcd(e,p-1)=1=\gcd(e,q-1)$$ is convenient, because it allows generating suitable $$p$$ and $$q$$ essentially independently. Also, when $$e$$ is prime (which is common: $$e$$ is typically a Fermat prime $$F_i=2^{(2^i)}+1$$ for some $$i\in\{0,1,2,3,4\}\,$$), this condition becomes $$p\bmod e\ne1$$ and $$q\bmod e\ne1$$, which are easy to check or ascertain by construction of $$p$$ and $$q$$.
• @kelalaka: the proof uses that for all integers $e,u,v\in\mathbb N^*$, it holds $\gcd(e,u\,v)=1$ $\iff$ $(\gcd(e,u)=1$ and $\gcd(e,v)=1)$ [which itself follows from the fact that prime divisors of $u\,v$ are the union of prime divisors of $u$ and prime divisors of $v$]. That's instantiated with $u=p-1$, $v=q-1$, $u\,v=\varphi(p\,q)=\varphi(n)$.