Take the 2-minute tour ×

I'm having a bit of trouble working through an example in the RSA entry on Wikipedia.

At step 5, $d$ is calculated as $2753$. However, $d$, which is the multiplicative inverse of $e$, can be calculated by applying Bézout to $$ de - k\phi(n)=1 ,$$ correct? When I run that calculation using Wolfram Alpha, I get $-367$. I'm assuming that I'm doing something wrong and that the Wikipedia entry is correct.

share|improve this question
add comment

1 Answer

You (and Wolfram Alpha) got the right answer, so it is very likely that you set up things correctly. Wikipedia also got the right answer. For note that $-367\equiv 2753\pmod{3120}$. (In the Wikipedia article, $\phi(n)=3120$, and we are calculating the inverse of $17$ modulo $\phi(n)$.)

Any two numbers that have the same remainder on division by $3120$ are treated as being "the same" modulo $3120$. So for example $5873$ would also be a correct answer. Wikipedia chose to give the smallest positive integer that works. Wolfram Alpha chose to give the number of smallest absolute value that works. There are legitimate arguments in favour of each choice.

share|improve this answer
Ah, okay. That was a really helpful answer. Thank you very much! –  dap Nov 14 '11 at 6:38
add comment

Your Answer


