Number Theory Note: inverse of a number (mod x)
Assume you’re calculating a great number. However, the number is very large and you’re required to return the number mod $10^9+7$. This is really common in algorithm problems and $10^9+7$ is a large prime that widely use to reduce clash.
It’s simple to deal with add, minus and multiply: (x+y)%mod, (x-y+mod)%mod and (x*y)%mod. But what about divide?
In modular arithmetic, we don’t have ‘division’ in the traditional sense. Instead, we use the Modular Multiplicative Inverse.
If $a \times x \equiv 1$, then $x$ is the modular inverse of $a$.
Let’s make an example: $3 \times 5 = 15$ and $15 \mod 7 = 1$. Thus we can say, 5 is the modular inverse of 3 (and vice versa). Dividing by 3 is mathematically equivalent to multiplying by 5 in the world of (mod7).
Fermat’s Little Theorem
In number theory, Fermat’s little theorem states that if $p$ is a prime number, then for any integer $a$, the number $a^p$ − $a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as
\[a^{p}\equiv a{\pmod {p}}\]Also we have
\[a^{p-2} a \equiv 1{\pmod {p}}\]Then $a^{p-2}$ is the inverse we gonna calculate.
Implement
Python
See Python document pow:
https://docs.python.org/3/library/functions.html#pow
1
2
3
4
>>> pow(38, -1, mod=97)
23
>>> 23 * 38 % 97 == 1
True
C++
You’re required to write a function. Then let b = mod - 2
1
2
3
4
5
6
7
8
long long power(long long a, long long b) {
if (b == 0) return 1;
a %= mod;
long long tmp = power(a, b / 2);
tmp = (tmp * tmp) % mod;
if (b % 2 == 1) return (tmp * a) % mod;
return tmp;
}
And there’s the iterate version:
1
2
3
4
5
6
7
8
9
10
long long power(long long a, long long b) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b % 2 == 1) res = (res * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return res;
}
Ref
- The paragraph of Fermat’s Little Theorem is copied from Wikipedia.
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
- Python Document of pow:
https://docs.python.org/3/library/functions.html#pow