The value of the expression 13^99 (mod 17) in the range 0 to 16 is ________.

GATE 2016 · Discrete Mathematics · Modular Arithmetic · medium

Answer: 13^99 ≡ 4 (mod 17)

1. Apply Fermat's Little Theorem: p = 17, a = 13. So 13^16 ≡ 1 (mod 17).
2. Reduce the exponent: 99 = 6*16 + 3. So 13^99 ≡ (1)^6 * 13^3 ≡ 13^3 (mod 17).
3. Compute 13^2 mod 17: 169 = 9*17 + 16, so 13^2 ≡ 16 ≡ -1 (mod 17).
4. Compute 13^3 mod 17: 13^3 ≡ (-1) * 13 ≡ -13 ≡ 17-13 ≡ 4 (mod 17).