Hello Everyone,

Given three numbers a, b and c, we need to find (ab) % c

Now why do “% c” after exponentiation, because ab will be really large even for relatively small values of a, b and that is a problem because the data type of the language that we try to code the problem, will most probably not let us store such a large number.

Examples:

Input : a = 2312 b = 3434 c = 6789

Output : 6343

Input : a = -3 b = 5 c = 89

Output : 24

The idea is based on below properties.

**Property 1:**

(m * n) % p has a very interesting property:

(m * n) % p =((m % p) * (n % p)) % p

**Property 2:**

if b is even:

(a ^ b) % c = ((a ^ b/2) * (a ^ b/2))%c ? this suggests divide and conquer

if b is odd:

(a ^ b) % c = (a * (a ^( b-1))%c

**Property 3:**

If we have to return the mod of a negative number x whose absolute value is less than y:

then (x + y) % y will do the trick

**Note:**

Also as the product of (a ^ b/2) * (a ^ b/2) and a * (a ^( b-1) may cause overflow, hence we must be careful about those scenarios

`// Recursive C++ program to compute modular power`

`#include <bits/stdc++.h>`

`using`

`namespace`

`std;`

`int`

`exponentMod(`

`int`

`A, `

`int`

`B, `

`int`

`C)`

`{`

` `

`// Base cases`

` `

`if`

`(A == 0)`

` `

`return`

`0;`

` `

`if`

`(B == 0)`

` `

`return`

`1;`

` `

`// If B is even`

` `

`long`

`y;`

` `

`if`

`(B % 2 == 0) {`

` `

`y = exponentMod(A, B / 2, C);`

` `

`y = (y * y) % C;`

` `

`}`

` `

`// If B is odd`

` `

`else`

`{`

` `

`y = A % C;`

` `

`y = (y * exponentMod(A, B - 1, C) % C) % C;`

` `

`}`

` `

`return`

`(`

`int`

`)((y + C) % C);`

`}`

`// Driver code`

`int`

`main()`

`{`

` `

`int`

`A = 2, B = 5, C = 13;`

` `

`cout << `

`"Power is "`

`<< exponentMod(A, B, C);`

` `

`return`

`0;`

`}`

**Output:**

Power is 6