GATE 2019 CS – Question 64
In an RSA cryptosystem, the value of the public modulus parameter $n$ is 3007. If it is also known that $\varphi(n)=2880$, where $\varphi()$ denotes Euler's Totient Function, then the prime factor of $n$ which is greater than 50 is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 97
Explanation
For $n=pq$, $\varphi(n)=(p-1)(q-1)=n-(p+q)+1$, so $p+q=3007+1-2880=128$. Then $p$ and $q$ are roots of $x^2-128x+3007=0$, giving $x=\frac{128\pm\sqrt{16384-12028}}{2}=\frac{128\pm66}{2}=97$ or $31$. The prime above 50 is 97.