Effective Computation of Large Exponents Modulo a Number
Q1 (Easy):
Compute 3^20 mod 11
Hint:
Use Fermat’s Little Theorem: for prime p, a^(p-1) ≡ 1 (mod p).
Solution:
11 is prime, so 3^10 ≡ 1 (mod 11).
20 = 2×10, so 3^20 ≡ (3^10)^2 ≡ 1^2 ≡ 1 (mod 11).
Answer: 1
Test Cases:
3^1 mod 11 = 3
3^5 = 243 ⇒ 243 mod 11 = 1
3^20 mod 11 = 1
Q2 (Easy):
Compute 7^13 mod 13
Hint:
If p is prime and gcd(a,p)=1, then a^(p-1) ≡ 1 (mod p).
Solution:
13 is prime, so 7^12 ≡ 1 (mod 13).
7^13 = 7^12×7 ≡ 1×7 ≡ 7 (mod 13).
Answer: 7
Test Cases:
7^1 mod 13 = 7
7^12 mod 13 = 1
7^13 mod 13 = 7
Q3 (Medium):
Compute 2^1000 mod 1009
Hint:
If modulus p is prime, use Fermat to reduce exponents or find modular inverses.
Solution:
1009 is prime, so 2^1008 ≡ 1 (mod 1009).
1000 = 1008 − 8.
So 2^1000 ≡ 2^(1008−8) ≡ 2^1008 × 2^(−8) ≡ 1 × (2^8)^(−1).
2^8 = 256.
Inverse of 256 mod 1009 is 942.
Therefore, 2^1000 mod 1009 = 942.
Answer: 942
Test Cases:
2^1 mod 1009 = 2
2^1008 mod 1009 = 1
2^1000 mod 1009 = 942
Q4 (Medium):
Compute 123456789^98765 mod 97
Hint:
Reduce both base and exponent using Fermat’s theorem.
Solution:
123456789 mod 97 = 39.
So problem is 39^98765 mod 97.
Since 97 is prime, 39^96 ≡ 1 (mod 97).
98765 mod 96 = 77.
So 39^98765 ≡ 39^77 (mod 97).
By fast modular exponentiation, result is 38.
Answer: 38
Test Cases:
123456789^1 mod 97 = 39
39^96 mod 97 = 1
123456789^98765 mod 97 = 38