Main content

## Computer science

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

© 2023 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.(24 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.(14 votes)

- Is there a proof for the modular exponentiation property

(A^B) mod C = ((A mod C) ^ B) mod C ?(3 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(21 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?(3 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(4 votes)

- a^-b mod c.

How to calculate where a,b,c positive integer(2 votes) - Help! My math teacher gave me something like this for our project: -3^1007829071(2 votes)
- 2^90 mod 13 = 12 mod 13

2^90 mod 13 = 12

How does 12 mod 13 become 12?(1 vote)- 12/13 = 0 with remainder 12, thus 12 mod 13 = 12(3 votes)

- A^B mod C = ( (A mod C)^B ) mod C

is there any proof like in the previous parts?(1 vote)- A^B just means the product from multiplying B "A"s together e.g. A^3 = A * A * A

From the multiplication property we have:

(A * A * A ....) mod C = (A mod C * A mod C * A modC ...) mod C

A^B mod C = ((A modC)^B) mod C(2 votes)

- how can i optimize this algorithm so that it works with fractional exponents? (since you can't convert non-whole numbers to binary)(1 vote)
- How do you go from this step:

2^90 mod 13 = (**2^50 mod 13****2^40 mod 13*) mod 13

To this step:

2^90 mod 13 = (**4*** 3 ) mod 13 ?(1 vote) - what will be the remainder when 2^1990 is divided by 1990 ?(1 vote)
- 2^1990 mod 1990 = 1024

You can see the calculation by sticking it in here:

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/p/fast-modular-exponentiation

You can understand the calculation by looking here:

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