Reputation: 348
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
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
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
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