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 have been going through the RSA cipher and have been wondering if there is a way other than the Extended Euclid Method to find

$a^{-1} \mod n$

where a,n $\in$ Z

P.S : n is not necessarily prime

share|cite|improve this question
Why do you want a method other than the extended Euclidean algorithm? It is extremely simple and fast to compute. – Brandon Carter Mar 5 '11 at 5:08
@Brendom : I am just enthusiastic – Prasoon Saurav Mar 5 '11 at 5:09
To check that the inverse mod n exists at all you need to do Euclid (the basic version). With a little extra bookkeeping (extended Euclid) we get the inverse for free. BTW, to do RSA itself you do not need this operation at all. Only at set-up, where we have to compute $d = e^{-1} \mod \phi(n)$ do we need it. – Henno Brandsma Mar 5 '11 at 12:44
up vote 5 down vote accepted

Let $a \in \mathbb{Z}$ with $(a,n)=1$. Then by Euler's Theorem, $$a^{\varphi(n)} \equiv 1 \pmod n$$ Then, it follows, since $a$ is invertible mod $n$, that $$a^{-1} \equiv a^{\varphi(n)-1} \pmod n$$ As a note, in practice this is much harder to compute than by using the extended Euclidean algorithm, as computing $\varphi(n)$ requires factoring $n$.

share|cite|improve this answer

Step 1: Compute the product $ax$ for all integers $1\leq x \leq n-1$. Stop when $ax\equiv 1 \pmod n$.

Step 2: The $x$ you get from the previous step is $a^{-1}$.


share|cite|improve this answer

Do the standard Euclidean algorithm with n^2 and an+1. The first remainder less than n that appears is the inverse of a.


Find the inverse of 16 mod 21:

Apply the Euclidean algorithm to 21^2 = 441 and 16*21+1 = 337 to get

441 = 337 + 104 337 = 3*104 + 25 104 = 4*25 + 4

Since 4 is less than 21, 4 is the inverse of 16 mod 21.

share|cite|improve this answer

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.