What is the remainder when 29¹⁵⁶ is divided by 17?

29 ≡ 12 (mod 17). Since 17 is prime, Fermat's little theorem gives 12¹⁶ ≡ 1 (mod 17). Write 156 = 16×9 + 12, so 29¹⁵⁶ ≡ 12¹² (mod 17). Build up: 12² = 144 ≡ 8; 12⁴ ≡ 8² = 64 ≡ 13; 12⁸ ≡ 13² = 169 ≡ −1; so 12¹² = 12⁸ × 12⁴ ≡ (−1) × 13 ≡ −13 ≡ 4 (mod 17). Remainder = 4. Shortcut: reduce the base mod the modulus first, then use Fermat to cut the exponent down to size before repeated squaring.