If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# Modular exponentiation

Finally, let's explore the exponentiation property:
A^B mod C = ( (A mod C)^B ) mod C
Often we want to calculate A^B mod C for large values of B.
Unfortunately, A^B becomes very large for even modest sized values for B.

### For example:

2^90 = 1237940039285380274899124224
7^256 = 2213595400046048155450188615474945937162517050260073069916366390524704974007989996848003433 83794038078279445526231260759886736342594056001485602786638194645895120583737911647366324673350968 0721264246243189632348313601
These huge values cause our calculators and computers to return overflow errors.
Even if they didn't, it would take a long time to find the mod of these huge numbers directly.

### What can we do to reduce the size of terms involved and make our calculation faster?

Suppose we want to calculate 2^90 mod 13, but we have a calculator that can't hold any numbers larger than 2^50.
Here is a simple divide and conquer strategy:
smaller parts
exponent rules
2^90 = 2^50 * 2^40
mod C
each part
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
multiplication properties
combine the parts
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12

### How can we calculate A^B mod C quickly if B is a power of 2 ?

How could we calculate 7^256 mod 13 using a calculator that can't hold numbers larger than 7^10 ?
We could split 7^256 into 25 parts of 7^10 and 1 part of 7^6, but this wouldn't be very efficient.
There is a better way....

## Want to join the conversation?

• What's the better way?
Is it 7^4^4^2?
Also, here's a puzzle:
prove 999,999 is a multiple of 7 using modular arithmetic. • 1) square root of 256 == 16. square root of 16 == 4.

7^4 modulo 13 == 9. 7^256 modulo 13 == 9.

7^4^4^2 is not the better way because the number is larger than 7^10 and the given calculator's memory cannot hold numbers larger than that.

2) 999999 modulo 7 == 0, use prime factorization to tease out the 7 and prove it's a multiple of 7.
• Is there a proof for the modular exponentiation property
(A^B) mod C = ((A mod C) ^ B) mod C ? • It is just repeated application of the property for multiplication
i.e. (X * Y) mod Z = (X mod Z * Y mod Z) mod Z

A^B mod C = ( A^(B-1) * A ) mod C
A^B mod C = ( A^(B-1) mod C * A mod C) mod C
A^B mod C = ( (A^(B-2) * A) mod C * A mod C) mod C
A^B mod C = ( (A^(B-2) mod C * A mod C) mod C * A mod C) mod C
A^B mod C = ( A^(B-2) mod C * A mod C * A mod C) mod C
...
A^B mod C = ( A mod C * A mod C * .... A mod C) mod C
(with B 'A mod C' terms on the right)
A^B mod C = ((A mod C)^B) mod C

Hope this makes sense
• What if the exponent B is negative? For instance, I read that 42^(-1) mod5 = 3=y. How do we arrive at that? According to what's written above,
y= (42 mod 5)^-1 mod 5 = 2^-1 mod 5 = 1/2 mod5
Now I'm getting stuck. Could someone help me? • a^-b mod c.
How to calculate where a,b,c positive integer • I like that cliffhanger • Help! My math teacher gave me something like this for our project: -3^1007829071 • if i have
x+y ≡ 6 (mod 7)
3x - y ≡ 2 (mod 7)
x-y ≡ ? (mod 7) • `` x  +  y ≡  6 (mod 7)3x  -  y ≡  2 (mod 7)``

is a system of linear congruences
You would solve it in the same manner that you would solve a system of linear equations with the following exception:
- you can't divide, so every time you would divide when solving a system of linear equations, you instead multiply by the modular inverse when solving a system of linear congruences

This would give you the values of x and y which you could simply plug into the last congruence for the solution.

e.g.
``2x  +  5y ≡ 6 (mod 13)3x  -  7y ≡ 2 (mod 13)``

Step 1) check the determinant

det = ((2 * -7) - (3 * 5)) mod 13 = -29 mod 13
-29 mod 13 = 10
The determinant is non-zero so we can find a unique solution (mod 13)
If it was 0 there would either be no solutions, or infinite solutions (mod 13)

Step 2) solve the linear congruence

We want the coefficient of the x to be 1 in the first congruence,
so we multiply the 1st congruence by 2^-1 mod 13
``2^-1 ( 2x  +  5y) ≡ 2^-1 * (6) (mod 13)       3x  -  7y  ≡          2 (mod 13)``

``(2^-1 * 2) * x  +  (2^-1 * 5) y  ≡ (2^-1 * 6) (mod 13)            3x  -            7y  ≡          2 (mod 13)``

``1x  +  (2^-1 * 5) y  ≡ (2^-1 * 6) (mod 13)3x  -            7y  ≡          2 (mod 13)``

2^-1 mod 13 = 7 since (2 * 7) mod 13 = 1

``1x  +  35y  ≡ 42 (mod 13)3x  -   7y  ≡ 2 (mod 13)``

reduce terms mod 13
``1x  +   9y  ≡ 3 (mod 13)3x  +   6y  ≡ 2 (mod 13)``

Subtract 3 times the first congrunce from the second congruence
``1x  +  9y ≡ 3  (mod 13)0x  - 21y ≡ -7 (mod 13)``

reduce terms mod 13
``1x  + 9y ≡ 3  (mod 13)0x  + 5y ≡ 6 (mod 13)``

We want the coefficient of the y to be 1 in the second congruence,
so we multiply the 2nd congruence by 5^-1 mod 13

``        1x  + 9y  ≡         3  (mod 13)5^-1 * (0x  + 5y) ≡ 5^-1 * (6) (mod 13)``

``1x  + 9y  ≡         3  (mod 13)0x  + 1y  ≡ (5^-1 * 6) (mod 13)``

5^-1 mod 13 = 8 since (5 * 8) mod 13 = 1

``1x  + 9y  ≡  3 (mod 13)0x  + 1y  ≡ 48 (mod 13)``

reduce terms mod 13
``1x  + 9y  ≡ 3 (mod 13)0x  + 1y  ≡ 9 (mod 13)``

subtract 9 times the second congruence from the first congruence
``1x  + 0y  ≡ -78 (mod 13)0x  + 1y  ≡ 9 (mod 13)``

reduce terms mod 13
``1x  + 0y  ≡ 0 (mod 13)0x  + 1y  ≡ 9 (mod 13)``

x ≡ 0 (mod 13)
y ≡ 9 (mod 13)

Step 3) check our solution against the original linear congruences
``2x  +  5y ≡ 6 (mod 13)3x  -  7y ≡ 2 (mod 13)``

Plug in x and y
``0  +  45 ≡ 6 (mod 13)0  -  63 ≡ 2 (mod 13)``

reduce terms mod 13
``6 ≡ 6 (mod 13)2 ≡ 2 (mod 13)``

So our solution is consistent with the original linear congruences

Hope this makes sense   