Multiplication in modular arithmetic is compatible with congruence. If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n). Therefore, large factors can be reduced before multiplication. Modular exponentiation extends this principle to powers: a^k mod n can be calculated by repeatedly reducing intermediate products. For very large exponents, repeated squaring provides an efficient method. This method expresses an exponent as a sum of powers of two and repeatedly squares the base modulo n. For example, 3^4 mod 7 can be calculated by observing that 3^2 = 9 ≡ 2 (mod 7), so 3^4 ≡ 2^2 = 4 (mod 7). Modular exponentiation is particularly important in public-key cryptography and algorithms involving large integers.
Multiplication and Exponentiation Modulo n
Modular multiplication and exponentiation calculate products and powers while reducing intermediate or final results modulo a fixed positive integer.
(ab) mod n = ((a mod n)(b mod n)) mod n; a^k mod n can be computed using repeated squaring
Explanation
Variables
A
The base or first factor.
B
The second factor.
K
A nonnegative integer exponent.
N
The positive modulus.
Example or application
Problem
Calculate 5^4 mod 13.
Solution
First, 5^2 = 25 ≡ 12 (mod 13). Then 5^4 ≡ 12^2 = 144 ≡ 1 (mod 13), because 144 = 11 × 13 + 1.
Answer
5^4 mod 13 = 1
Text
The modular multiplication rule allows each factor to be replaced by its residue. Modular exponentiation applies repeated multiplication and reduction, with repeated squaring making large powers computationally manageable.
Key Points
Multiplication preserves congruence.
Each factor can be reduced modulo n before multiplication.
Exponentiation modulo n is repeated modular multiplication.
Repeated squaring efficiently calculates powers with large exponents.
Intermediate values can be reduced to prevent unnecessary growth.
Modular exponentiation is a central operation in several cryptographic algorithms.
Applications
RSA public-key cryptography.
Diffie–Hellman key exchange.
Digital signature algorithms.
Efficient computation with very large integers.
Number-theoretic algorithms and computational mathematics.
Learning Outcomes
Calculate products modulo n.
Evaluate small powers modulo n.
Explain the repeated-squaring method.
Recognize why modular exponentiation is useful for large computations.
Practice Questions
Calculate (12 × 17) mod 5.
Find 4^3 mod 7.
Calculate 7^4 mod 10.
Use repeated squaring to evaluate 3^8 mod 11.
Explain why modular reduction can be performed after each multiplication.
Related Concepts
Modular Addition
Congruence Relations
Repeated Squaring
Modular Inverses
Fermat's Little Theorem
Common Mistakes
Multiplying large numbers without reducing intermediate results when a simpler calculation is possible.
Confusing exponentiation with multiplication by the exponent.
Reducing the exponent modulo n without a theorem that justifies doing so.
Making arithmetic errors when reducing squared values.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Kenneth H. Rosen, Elementary Number Theory and Its Applications
- Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography
Suggest a correction or source · More in Arithmetic & Number Theory