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.**

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