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 A^B mod C for large values of B.
Unfortunately, A^B becomes very large for even modest sized values for 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.
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
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
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)