CODEWITHSUNDEEP
pythonpython-3.xpow
ibarrond
ibarrond

Reputation: 7591

What does pow(a, b, c) do when the exponent is negative?

Python allows a third argument in the built-in function pow that basically computes the exponentiation modulo this third argument (pow(a,b,c) = a**b % c).

How does it work when the exponent is negative? E.g.:

pow(6, -2, 13)
#-> 4

pow(6, -2, 12)
#-> Traceback (most recent call last):
#->  File "<stdin>", line 1, in <module>
#->  ValueError: base is not invertible for the given modulus

Upvotes: 3

Views: 6284

Answers (5)

Veky
Veky

Reputation: 2745

I think nobody answered your exact question. pow(6, -2, 13) is six to the minus second power modulo 13, that is, something (from range(13)) that gives 1 when multiplied with 6 squared. That is 4, because 4 * 6**2 == 144, which is 1 modulo 13.

The same thing modulo 12 doesn't exist, since whatever you multiply by 36 will be divisible by 12, so you'll always get 0 (and never 1) mod 12.

Upvotes: 1

Susheel
Susheel

Reputation: 1679

pow(base, exp) =  base**exp
pow(12,2) = 144 = 12**2

Now computation of modular inverses in supported 3.8 afterwards. Before that they denied to inverse to base modulu

Upvotes: 0

Jay
Jay

Reputation: 35

Have you tried to check it out for yourself? Python used to not support negative exponents when the third argument was supplied, something they changed in version 3.8.x, and now what it does is allow you to compute the modular inverse (as opposed to the 'standard' inverse when dealing with the reals).

So, if example pow(2, -1, 3) would tell you the inverse in mod 3 which would be 2, because 2*2 =4 = 1 mod 3

Upvotes: 0

Yotam Alon
Yotam Alon

Reputation: 178

From the python built-in functions documentation:

For int operands base and exp, if mod is present, mod must also be of integer type and mod must be nonzero. If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.

which means that in your example, python calculates the inverse of 6 (so that 6 * inverse = 1) and calculates pow(inverse, 2, 13). In this case the inverse of 6 mod 13 is 11 (6 * 11 = 66 = 1 mod 13) and you calculate 11 ** 2 = 121 = 4 mod 13.

Upvotes: 4

Marcel
Marcel

Reputation: 1048

When the second argument is -1, it calculates the modular inverse of a (mod c). Using other negative powers -n will return the modular inverse to the n-th power (mod c).

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Upvotes: 0

Related Questions