Fermat’s Little Theorem in C++

This C++ Program demonstrates the implementation of Fermat’s Little Theorem. For the modular multiplicative inverse to exist, the number and modular must be coprime.

Here is source code of the C++ Program to implement Fermat’s Little Theorem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C++ Program to Implement Fermat's Little Theorem

```
 */
```
```
#include <iostream>
```
```
using namespace std;
```
```
 
```
```
/* calculates (a^b)%MOD */
```
```
int pow(int a, int b, int MOD) 
```
```
{
```
```
    int x = 1, y = a;
```
```
    while (b > 0) 
```
```
    {
```
```
        if (b % 2 == 1) 
```
```
        {
```
```
            x = (x * y);
```
```
            if (x > MOD) 
```
```
                x %= MOD;
```
```
        }
```
```
        y = (y * y);
```
```
        if (y > MOD) 
```
```
            y %= MOD;
```
```
        b /= 2;
```
```
    }
```
```
    return x;
```
```
}
```
```
 
```
```
int modInverse(int a, int m) 
```
```
{
```
```
    return pow(a, m - 2, m);
```
```
}
```
```
//Main
```
```
int main()
```
```
{
```
```
    int a, m;
```

    cout<<"Enter number to find modular multiplicative inverse: ";

```
    cin>>a;
```
```
    cout<<"Enter Modular Value: ";
```
```
    cin>>m;
```
```
    cout<<modInverse(a, m)<<endl;
```
```
}
```

$ g++ fermat_little.cpp
$ a.out
 
Enter number to find modular multiplicative inverse: 1111
Enter Modular Value: 331
216
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - Euler Theorem in C++

» Next - C++ Program to Implement KMP Pattern Searching Algorithm

Next Steps: