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

1. `/*`
2. ` * C++ Program to Implement Fermat's Little Theorem`
3. ` */`
4. `#include <iostream>`
5. `using namespace std;`
6. ` `
7. `/* calculates (a^b)%MOD */`
8. `int pow(int a, int b, int MOD) `
9. `{`
10. `    int x = 1, y = a;`
11. `    while (b > 0) `
12. `    {`
13. `        if (b % 2 == 1) `
14. `        {`
15. `            x = (x * y);`
16. `            if (x > MOD) `
17. `                x %= MOD;`
18. `        }`
19. `        y = (y * y);`
20. `        if (y > MOD) `
21. `            y %= MOD;`
22. `        b /= 2;`
23. `    }`
24. `    return x;`
25. `}`
26. ` `
27. `int modInverse(int a, int m) `
28. `{`
29. `    return pow(a, m - 2, m);`
30. `}`
31. `//Main`
32. `int main()`
33. `{`
34. `    int a, m;`
35. `    cout<<"Enter number to find modular multiplicative inverse: ";`
36. `    cin>>a;`
37. `    cout<<"Enter Modular Value: ";`
38. `    cin>>m;`
39. `    cout<<modInverse(a, m)<<endl;`
40. `}`

```\$ g++ fermat_little.cpp
\$ a.out

Enter number to find modular multiplicative inverse: 1111
Enter Modular Value: 331
216

------------------
(program exited with code: 1)

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

Note: Join free Sanfoundry classes at Telegram or Youtube