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__()

3 comments

Thomas Ahle 12 years, 2 months ago  # | flag

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 11 years, 1 month ago  # | flag

Contrary to advertisement, this recipe does not work if p is not prime. Try a=3 and p=4 for example.

Justin Shaw (author) 11 years, 1 month ago  # | flag

Thanks Daniel, fixed.

Created by Justin Shaw on Sun, 3 May 2009 (MIT)
Python recipes (4591)
Justin Shaw's recipes (11)

Required Modules

  • (none specified)

Other Information and Tasks