4
$\begingroup$

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?$

  • 2
    possible duplicate of [finding inverse of $x\bmod y$](http://math.stackexchange.com/questions/14124/finding-inverse-of-x-bmod-y)2011-05-10

4 Answers 4

8

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.

3

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.

1

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.

0

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)$.