Find the remainder when 54124 is divided by 17.

Concept: For a prime modulus p, Fermat's Little Theorem says that a number a coprime to p satisfies: a raised to the power (p - 1) is congruent to 1, modulo p. So the powers of a modulo p repeat in a cycle whose length (the 'cyclicity') divides p - 1. To find the remainder of a large power modulo p: reduce the base modulo p, find that cyclicity, reduce the exponent by the cyclicity, and evaluate the resulting smaller power.

Application: Reduce the base first: 54 mod 17 = 3, since 54 = 3 times 17 + 3. So the problem becomes: find the remainder when 3124 is divided by 17.

Since 17 is prime, by Fermat's Little Theorem 316 is congruent to 1 (mod 17); the cyclicity of 3 modulo 17 is therefore a divisor of 16 (1, 2, 4, 8, or 16). Check by repeated squaring, reducing mod 17 at every step:

1. 32 = 9

2. 34 = 92 = 81, which is congruent to 81 - 68 = 13 (mod 17)

3. 38 = 132 = 169, which is congruent to 169 - 153 = 16, i.e. -1 (mod 17)

4. 316 = (38)2, which is congruent to (-1)2 = 1 (mod 17)

None of 32, 34, or 38 is congruent to 1, so the cyclicity is exactly 16, not a smaller divisor.

Reduce the exponent by this cyclicity: 124 mod 16 = 12, since 124 = 7 times 16 + 12. So 3124 mod 17 equals 312 mod 17.

Using the squarings above: 312 = 38 times 34, which is congruent to (-1) times 13 = -13, i.e. 4 (mod 17).

Cross-check: Cross-check by an independent route: 312 = (34)3, which is congruent to 133 (mod 17). Since 132 is congruent to 169, i.e. 16, i.e. -1, we get 133 congruent to -13, i.e. 4 (mod 17) - the same remainder, confirming the result.

Result: So the remainder when 54124 is divided by 17 is 4.

Tip: Useful shortcut: for a prime modulus p, the cyclicity of any base coprime to p always divides p-1, so using (p-1) as a safe upper bound on the cyclicity (here 16) is a shortcut that always works, even without checking every intermediate power.