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.

Main content

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?

  • male robot hal style avatar for user summitwei
    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.

    Answer is in comments.
    (26 votes)
    Default Khan Academy avatar avatar for user
    • duskpin ultimate style avatar for user Freethinkingaway
      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.
      (15 votes)
  • male robot hal style avatar for user Alex Soh
    Is there a proof for the modular exponentiation property
    (A^B) mod C = ((A mod C) ^ B) mod C ?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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
      (21 votes)
  • piceratops seedling style avatar for user Neodymia
    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?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user suanmiasrt
    a^-b mod c.
    How to calculate where a,b,c positive integer
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Ghassen Faidi
    I like that cliffhanger
    (3 votes)
    Default Khan Academy avatar avatar for user
  • primosaur ultimate style avatar for user El
    Help! My math teacher gave me something like this for our project: -3^1007829071
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user yasmin kh
    if i have
    x+y ≡ 6 (mod 7)
    3x - y ≡ 2 (mod 7)
    x-y ≡ ? (mod 7)
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
       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
      (2 votes)
  • blobby green style avatar for user castilinox890
    can someone solve 216^2011 mod 3127
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Vijaya Krishna Yadlapalli
    exponentiations applying the “square and multiply” , how to do this ??
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user aparnadevi03
    what is the reminder if 3^287/23
    (1 vote)
    Default Khan Academy avatar avatar for user