The value of 3^33 mod 5 is _____.

GATE 2019 · Discrete Mathematics · Modular Arithmetic · medium

Answer: 3^33 mod 5 = 3

1. Apply Fermat's Little Theorem: 3^4 ≡ 1 (mod 5). Verify: 3^4 = 81 = 16*5 + 1.
2. Reduce the exponent mod 4: 33 = 8*4 + 1. So 3^33 ≡ (1)^8 * 3^1 ≡ 3 (mod 5).