Today’s importance is inverse element, however, inverse element calculation is based on the extended Euclid algorithm. At first, we need to know the Euclid’s algorithm.
A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference. –from Wikipedia
ax+by=gcd(a,b)
From the Euclid Method of calculating gcd, we know that
gcd(a,b)=gcd(b,a
1 | typedef pair<int,int> P; |
The previous one is the direct one we can get from the mathematical function. Here is a better way of writing it.
1 | void gcdEx(int a, int b, int &x, int &y){ |
ax≡1(mod b)
There is a inverse element only if a and b are both prime numbers. The equation above means both side mod b at the same time is equal. x is a reverse element of a under mod b.
We can change the equation into this.
ax mod m=1 ax−my=1
So the code looks like this.
1 | int x, y; |
x is the inverse element of a.