CODEWITHSUNDEEP
pythonmodulopow
Fahim
Fahim

Reputation: 348

How does Python pow() function work with a negative power and a mod value

The documentation about the pow(base, exp[, mod]) function says,
"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."

I don't understand the line at all and also how it works. The provided example is as follows:

>>> pow(38, -1, mod=97)
23
>>> 23 * 38 % 97 == 1
True

Shouldn't it behave like (38**-1)%97 = 0.02631578947368421 ?
If I try to go from 23 * 38 % 97 == 1 to backward, I don't know what's the inverse of modulo.

Can anyone kindly give me a clear explanation of how it ended being 23? A mathematical explanation will be highly helpful.

Upvotes: 3

Views: 1809

Answers (3)

Fahim
Fahim

Reputation: 348

The answer from @wim and the example by @Tim Peters helps me understand what's going on in this pow() function. Let's take an example,

>>> pow(3, -1, 8)
3

Modulo by a number m must be in the range(0,m). For example 14%5 must be in range(0,5), hence it's 4.

So modulo 1/3 % 8 must be in the range(8). But as 1/3=0.33 which is not in the range, we need a way around to find it.

1/3 % 8 cannot be zero, as it's not divisible. So the lowest possible value is 1. That means, we need to represent 1/3 in such a way that x % 8 == 1 becomes True. It's obvious that 9 % 8 == 1.
As 3(target value) * 3(base) = 9, hence, the answer is 3(target value).

For a complex example, let's take:

>>> pow(38, -1, mod=97)
23

1/38=0.026. Again, need a way around. As the lowest mod should be 1, hence x % 97 == 1. Obviously 98 % 97 == 1, but 98/38 is not a whole number. Next, (2*97+1) or 195 % 97 == 1, but 195/38 is not a whole number.

In this process, (9*97+1) or 874 % 97 == 1 and 874/38=23. So the final expression becomes:

23 * 38 % 97 == 1

Hence, the answer is 23.

Upvotes: 0

wim
wim

Reputation: 363616

In modular arithmetic division does not have a unique answer, so we do not have a division operation. Instead you have modular inverses.

The docs are trying to explain that pow(b, -1, mod=m) can be used to calculate the inverse of b, modulo m. That is, finding some number d such that d * b % m = 1.

The line 23 * 38 % 97 == 1 is simply demonstrating that the answer 23, which was the result of pow(38, -1, mod=97), is the correct modular inverse of 38.

The explanation in the docs seems to be assuming the reader already has some familiarity with modular arithmetic.

Can anyone kindly give me a clear explanation of how it ended being 23? A mathematical explanation will be highly helpful.

Try running this code snippet:

for i in range(97): 
    s = f"{i} * 38 % 97" 
    print(s, "==", eval(s))

Exactly one of the lines will reveal the congruence d * 38 % 97 == 1. There are, of course, smarter ways to compute the inverse but the brute force demonstration above should make it easier to understand what a modular inverse means.

Upvotes: 3

Tim Peters
Tim Peters

Reputation: 70735

With integer arguments and mod specified, pow() does arithmetic in the "multiplicative group of integers modulo mod"

For example, the integers relatively prime to 8 (1, 3, 5, and 7) form a group under multiplication mod 8. The identity is 1. Since 3*3 = 9 is congruent to 1 modulo 8, 3 is its own inverse in this group, and

>>> pow(3, -1, 8)
3

In the doc example, 23 and 38 are inverses modulo 97.

>>> pow(23, -1, 97)
38
>>> pow(38, -1, 97)
23

This isn't particularly esoteric, but rather basic tools in number theory.

Upvotes: 1

Related Questions