The House of Lilliput is using RSA encryption to receive secret messages from all the realms. They have published their public encoding exponent $e = 37$ and their public modulus $M = pq = 527$.
Find their secret decoding exponent $d.$
First of all, the prime factorization of $527$ is $31\cdot17$, so it's either 13 or 17. After some calculations, I found that 13 is the answer. Can anything confirm or correct my answer?
I have been told that my approach is incorrect. Could something post the correct solution? Thanks!
$527 = M = pq = 31 \cdot 17$, as you say. So $\phi(M) = (p-1)(q-1) = 30 \cdot 16 = 480$.
Now $d$ is usually defined as the number $d < \phi(M)$ such that $ed = 1 \bmod \phi(M)$. This will ensure that $(m^e)^d = m^{ed} = m \bmod M$ for all $m < M$. So $d$ is required secret exponent ($e = 37$ being the public one).
As $e = 37$ is prime and does not divide $480$, they have gcd equal to $1$ and we can, using the extended Euclidean algorithm, find $x,y \in \mathbb{Z}$ such that $37x + 480y = 1$. Taking this equation modulo $480$, we see that the $x$ in this equation (modulo $\phi(M) = 480$) is the number $d$ you're looking for.
BTW, $d = 13$, from the comments, is indeed correct and can be checked as follows: $13 \cdot 37 = 481 = 1 \bmod 480$. In this case the numbers are so small that one can easily find them by trial and error or a simple minded computer program. For large numbers with known factorisations we would implement the Euclidean algorithm instead.