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 ?


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...

| improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – MrJab Jun 20 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.