The value of the expression 1399 (mod 17), in the range 0 to 16, is __________ .

Concept

By Fermat's Little Theorem, if p is prime and the integer a is not divisible by p, then ap−1 ≡ 1 (mod p). Reducing a large exponent modulo (p−1) therefore collapses the power to a small, easily computable residue.

Application

1. Here p = 17 (prime) and a = 13 is not divisible by 17, so 1316 ≡ 1 (mod 17).

2. Reduce the exponent modulo 16: 99 = 16·6 + 3, so 1399 = (1316)6·133 ≡ 16·133 ≡ 133 (mod 17).

3. Compute 132 = 169 = 9·17 + 16 ≡ 16 (mod 17).

4. Then 133 = 13·132 ≡ 13·16 = 208 = 12·17 + 4 ≡ 4 (mod 17).

Cross-check

Note 16 ≡ −1 (mod 17), so 132 ≡ −1 and 133 ≡ 13·(−1) = −13 ≡ 4 (mod 17), which agrees. Hence the residue of 1399 modulo 17, in the range 0 to 16, is 4.