modular_inverse_fermat_little_theorem.cpp File Reference

C++ Program to find the modular inverse using Fermat's Little Theorem More...

#include <iostream>
#include <vector>

Include dependency graph for modular_inverse_fermat_little_theorem.cpp:

Functions
int64_t	binExpo (int64_t a, int64_t b, int64_t m)
bool	isPrime (int64_t m)
int	main ()

Detailed Description

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

• a = 3 and m = 7
• \(a^{-1} \;\text{mod}\; m\) is equivalent to \(a^{m-2} \;\text{mod}\; m\)
• \(3^5 \;\text{mod}\; 7 = 243 \;\text{mod}\; 7 = 5\)
  Hence, \(3^{-1} \;\text{mod}\; 7 = 5\) or \(3 \times 5 \;\text{mod}\; 7 = 1 \;\text{mod}\; 7\) (as \(a\times a^{-1} = 1\))

Function Documentation

binExpo()

int64_t binExpo	(	int64_t	a,
		int64_t	b,
		int64_t	m )

Recursive function to calculate exponent in \(O(\log n)\) using binary exponent.

                                                 {
    a %= m;
    int64_t res = 1;
    while (b > 0) {
        if (b % 2) {
            res = res * a % m;
        }
        a = a * a % m;
        // Dividing b by 2 is similar to right shift.
        b >>= 1;
    }
    return res;
}

isPrime()

bool isPrime

(

int64_t

m

)

Prime check in \(O(\sqrt{m})\) time.

                        {
    if (m <= 1) {
        return false;
    } else {
        for (int64_t i = 2; i * i <= m; i++) {
            if (m % i == 0) {
                return false;
            }
        }
    }
    return true;
}

main()

int main

(

void

)

Main function

           {
    int64_t a, m;
    // Take input of  a and m.
    std::cout << "Computing ((a^(-1))%(m)) using Fermat's Little Theorem";
    std::cout << std::endl << std::endl;
    std::cout << "Give input 'a' and 'm' space separated : ";
    std::cin >> a >> m;
    if (isPrime(m)) {
        std::cout << "The modular inverse of a with mod m is (a^(m-2)) : ";
        std::cout << binExpo(a, m - 2, m) << std::endl;
    } else {
        std::cout << "m must be a prime number.";
        std::cout << std::endl;
    }
}

Here is the call graph for this function: