# If $((p-1)*(q-1) -1)$ divisible by $e$ ($e$ is odd number) , then $\text{gcd}(e,(p-1)*(q-1)) = 1$

If $$((p-1)(q-1) -1)$$ divisible by $$e$$ ($$e$$ is odd number) , then $$\text{gcd}(e,(p-1)(q-1)) = 1$$. ($$p,q$$ are prime numbers ) Is this true, if yes why, if not why not ?

## 1 Answer

Is this true?

I'd generalize it, and replace $$(p-1)(q-1)$$ with $$X$$; that is, if $$X-1$$ is divisible by $$e$$, that is, if $$X-1 = k \times e$$ for some integer $$k$$, then $$\gcd(e, X) = 1$$. Is this true? If it is, then your original statement is also true (because if it holds for all $$X, e$$, it also holds for all $$X$$ that is of the form $$(p-1)(q-1)$$ and for all odd $$e$$.).

As a further hint, we can also observe that $$\gcd(e, X) = \gcd(e, X \bmod e)$$ (that's the central observation that makes the Euclidean method for evaluating $$\gcd$$ work).

With that, it should be fairly straight-forward to proceed...

• Yeah thank you e must be selected such that gcd(e,X) = 1 so the first part can hold. This is similar to RSA algorithm, we select e such that gcd(e,phi(n)) = 1. So question that i took this was : Prove this cryptosystem is equivalent to RSA : 1: Select an odd number e, 2: choose two primes p,q such that (p-1)(q-1) -1 is divisible by e. 3: Calculate N= p*q. 4: Calculate d = ((p-1)(q-1)(e-1) + 1)/e – MrJab Jun 20 at 22:34