Welcome, guest | Sign In | My Account | Store | Cart

Very rarely it is necessary to find the multiplicative inverse of a number in the ring of integers modulo p. Thie recipe handles those rare cases. That is, given x, an integer, and p the modulus, we seek a integer x^-1 such that x * x^-1 = 1 mod p. For example 38 is the inverse of 8 modulo 101 since 38 * 8 = 304 = 1 mod 101. The inverse only exists when a and p are relatively prime.

Python, 25 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25``` ```def invmodp(a, p): ''' The multiplicitive inverse of a in the integers modulo p. Return b s.t. a * b == 1 mod p ''' for d in xrange(1, p): r = (d * a) % p if r == 1: break else: raise ValueError('%d has no inverse mod %d' % (a, p)) return d def __invmodp__test__(): p = 101 for i in range(1, p): iinv = invmodp(i, p) assert (iinv * i) % p == 1 a = 3 p = 4 assert (a * invmodp(a, p)) % p == 1 __invmodp__test__() ``` Thomas Ahle 11 years, 4 months ago

In case p is also prime, you can use fermats little theorem and the build in pow method: pow(a, p-2, p). Daniel Müllner 10 years, 4 months ago

Contrary to advertisement, this recipe does not work if p is not prime. Try a=3 and p=4 for example. Justin Shaw (author) 10 years, 4 months ago

Thanks Daniel, fixed. Created by Justin Shaw on Sun, 3 May 2009 (MIT)

### Required Modules

• (none specified)