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?
• In modular arithmetic A^-1 (mod B) denotes the modular inverse of A (mod B).
Check out:

The following property holds in the regular math that you are used to and also holds in modular math:
A^B * A^-C = A^(B-C)
Example 1: A^-1 * A^1 = A^0 = 1 e.g. 2^-1 * 2 = 1
Example 2: A^2 * A^-1 = A^1 = A e.g. 2^2 * 2^-1 = 2

So here's how we could solve 42^(-1) mod5 :
42 mod 5 ≡ 2
We can see that 2 * 3 = 6 and 6 ≡ 1 (mod 5), thus 2^-1=3 (mod 5)
(note that 2 * 2^-1 = 1),

(Just to show that it works on 42 we can write:
42 * 3 = 126
126 mod 5 = 1
Thus 42^-1 mod 5 = 3
)

Hope this makes sense
• a^-b mod c.
How to calculate where a,b,c positive integer
• I like that cliffhanger
• yup
(1 vote)
• Help! My math teacher gave me something like this for our project: -3^1007829071
• SO basically, its really ez the awnser is 3
(1 vote)
• 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