Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer
Ah, okay. That was a really helpful answer. Thank you very much! – dap Nov 14 '11 at 6:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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