Find the remainder when 29^18 is divided by 26. Choose the correct remainder.
-
A1
-
B29
-
C26
-
D18
-
E0
Answer
Correct Answer: 1
Explanation
Introduction / Context:This modular arithmetic question requires reducing a large power modulo 26. Using properties such as Euler’s theorem or pattern cycles helps avoid huge computations and leads quickly to the correct remainder.
Given Data / Assumptions:
- We want r = 29^18 mod 26.
- 29 mod 26 = 3, so 29^18 mod 26 = 3^18 mod 26.
- gcd(3, 26) = 1, enabling Euler’s theorem with phi(26) = 12.
Concept / Approach:Apply modular reduction of the base and exponent properties. Since 3 and 26 are coprime, 3^12 ≡ 1 (mod 26). Then reduce the exponent 18 using the cycle length 12 to simplify the computation.
Step-by-Step Solution:
Reduce base: 29 ≡ 3 (mod 26).Use cycle: 3^12 ≡ 1 (mod 26) by Euler’s theorem.Rewrite: 3^18 = 3^12 * 3^6 ≡ 1 * 3^6 (mod 26).Compute 3^3 = 27 ≡ 1 (mod 26), hence 3^6 = (3^3)^2 ≡ 1^2 ≡ 1.Therefore, 3^18 ≡ 1 (mod 26).Verification / Alternative check:Direct small-cycle check: powers of 3 mod 26 repeat with period 3 since 3^3 ≡ 1; then 3^18 = (3^3)^6 ≡ 1^6 ≡ 1.
Why Other Options Are Wrong:29 and 26 are not valid remainders under modulus 26 (26 represents zero). 18 is arbitrary. 0 would imply divisibility, which does not hold.
Common Pitfalls:Forgetting to reduce the base first or misapplying Euler’s theorem without checking coprimality.
Final Answer:1