Main content

### Course: Computer science theory > Unit 2

Lesson 5: Modular arithmetic- What is modular arithmetic?
- Modulo operator
- Modulo Challenge
- Congruence modulo
- Congruence relation
- Equivalence relations
- The quotient remainder theorem
- Modular addition and subtraction
- Modular addition
- Modulo Challenge (Addition and Subtraction)
- Modular multiplication
- Modular multiplication
- Modular exponentiation
- Fast modular exponentiation
- Fast Modular Exponentiation
- Modular inverses
- The Euclidean Algorithm

© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Modular exponentiation

Finally, let's explore the

**exponentiation property**:**A^B mod C = ( (A mod C)^B ) mod C**

Often we want to calculate

Unfortunately,

**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

Even if they didn't, it would take a

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

Answer is in comments.(26 votes)- 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.(16 votes)

- Is there a proof for the modular exponentiation property

(A^B) mod C = ((A mod C) ^ B) mod C ?(2 votes)- 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(22 votes)

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

Check out:

https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/modular-inverses

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(5 votes)

- a^-b mod c.

How to calculate where a,b,c positive integer(3 votes) - I like that cliffhanger(3 votes)
- Help! My math teacher gave me something like this for our project: -3^1007829071(3 votes)
- 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)(2 votes)`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)

- can someone solve 216^2011 mod 3127(1 vote)
- Use fast modular exponentiation as described in the next lesson. Right after that lesson there is a calculator for modular exponents, so you can check your calculations.(1 vote)

- exponentiations applying the “square and multiply” , how to do this ??(1 vote)
- what is the reminder if 3^287/23(1 vote)
- This article will show you how to figure out the answer to that question:

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation(1 vote)