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.
More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions
- GATE 2018 CS Q37
- GATE 2015 CS (CS1) Q11
- GATE 2015 CS (CS1) Q20
- GATE 2015 CS (CS1) Q42
- GATE 2016 CS (CS1) Q38
- GATE 2014 CS (CS1) Q60
All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →