Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given two integers $a$ and $m$, such that $a\mathop\bot m,$ how can I find an integer $b$ such that $a\cdot b\equiv 1\mod m?$

share|improve this question
2  
I'm assuming $a\bot m$ means that $\gcd(a,m)=1$? –  Asaf Karagila May 10 '11 at 14:44
    
@Asag Karagila: Yes. –  FUZxxl May 10 '11 at 14:46
2  
possible duplicate of finding inverse of $x\bmod y$ –  Aryabhata May 10 '11 at 17:48

4 Answers 4

up vote 7 down vote accepted

Use the extended Euclidean algorithm on $a$ and $m$. If you know $\phi(m)$, you can use Euler's theorem and get $b=a^{\phi(m)-1}$ using modular exponentiation.

share|improve this answer

I will show by example, $a = 7$ and $m = 17$.

I want to solve $7b + 17y = 1$ because reducing that equation mod $m$ gives $7 \cdot b \equiv 1 \pmod {17}$.

To solve $7b + 17y = 1$ I will reduce it to an easier equation $7b + (7 + 10)y = 7(b+y) + 10y = 7(b+2y) + 3y = 1$, so now we are in a similar situation.

We want to solve $7x + 3y = 1$ and we can do the same kind of reduction, $7x+3y=4x+3(x+y)=x+3(2x+y)=1$ so again we are in the same situation.

Now we want to solve $x + 3z = 1$, that is easy, set $x = 4$ and $z = -1$.. but now we have to go backwards through this to get $b$. $-1 = z = 2x+y$ and $x=4$ so $y = -9$, further $4 = x = b+2y = b-18$ so $b = 22$.

Since this is a very long calculation is it useful to check that this is the right answer: $7 \cdot 22 \equiv 7 \cdot 9 \equiv 1 \pmod {17}$.


Once this idea is very clear it is possible to optimize it so that both forward and backward stages are done simultaneously.

share|improve this answer

By Bézout, the assumption $\gcd(a,m)=1$ implies that $ab+mc=1$ for certain integers $b,c$. Hence $ab\equiv 1 \mod m$.

This proves existence. To literally find these $b$ (and $c$) Bézout talks about, you can use the 'extended Euclidean algorithm' that lhf mentioned.

share|improve this answer

As mentioned by others, Euclid's Extended Algorithm is the usual method for computing inverses in $Z_n$. For a complete treatment, see Ch. 1 of Dasgupta, et al. This excellent text is free online (preprint version) in the link I gave.

Note that Euclid's Extended runs in $O(n^3)$ when the inputs are $n$-bits each. This is a bit slow for large $n$, but with modern computing speeds even a laptop can handle these computations in the blink of an eye.

Probably the most common setting where Euclid's Extended is used is for RSA key generation where we have to find an inverse of $e$ (usually chosen to be the prime 65537) mod $\phi(n)$ (where $n$ is the product of two large distinct random primes $p$ and $q$, so $\phi(n)=(p-1)(q-1)$). However, the overall key generation step is dominated by the cost of finding $p$ and $q$ which takes an expected $O(n^4)$.

share|improve this answer

Your Answer

 
discard

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.