Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
C++ Program to find the modular inverse using Fermat's Little Theorem More...
#include <iostream>
#include <vector>
Functions | |
int64_t | binExpo (int64_t a, int64_t b, int64_t m) |
bool | isPrime (int64_t m) |
int | main () |
C++ Program to find the modular inverse using Fermat's Little Theorem
Fermat's Little Theorem state that
\[ϕ(m) = m-1\]
where \(m\) is a prime number.
\begin{eqnarray*} a \cdot x &≡& 1 \;\text{mod}\; m\\ x &≡& a^{-1} \;\text{mod}\; m \end{eqnarray*}
Using Euler's theorem we can modify the equation.
\[ a^{ϕ(m)} ≡ 1 \;\text{mod}\; m \]
(Where '^' denotes the exponent operator)
Here 'ϕ' is Euler's Totient Function. For modular inverse existence 'a' and 'm' must be relatively primes numbers. To apply Fermat's Little Theorem is necessary that 'm' must be a prime number. Generally in many competitive programming competitions 'm' is either 1000000007 (1e9+7) or 998244353.
We considered m as large prime (1e9+7). \(a^{ϕ(m)} ≡ 1 \;\text{mod}\; m\) (Using Euler's Theorem) \(ϕ(m) = m-1\) using Fermat's Little Theorem. \(a^{m-1} ≡ 1 \;\text{mod}\; m\) Now multiplying both side by \(a^{-1}\).
\begin{eqnarray*} a^{m-1} \cdot a^{-1} &≡& a^{-1} \;\text{mod}\; m\\ a^{m-2} &≡& a^{-1} \;\text{mod}\; m \end{eqnarray*}
We will find the exponent using binary exponentiation. Such that the algorithm works in \(O(\log m)\) time.
Examples: -
int64_t binExpo | ( | int64_t | a, |
int64_t | b, | ||
int64_t | m ) |
Recursive function to calculate exponent in \(O(\log n)\) using binary exponent.
bool isPrime | ( | int64_t | m | ) |
Prime check in \(O(\sqrt{m})\) time.
int main | ( | void | ) |
Main function