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

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.

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.

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.