What is the remainder when 1693730 is divided by 31?

Concept: Fermat's Little Theorem states that if p is a prime number and a is not divisible by p, then ap-1 is congruent to 1 modulo p. This lets the remainder of a very large power be found by reducing the exponent using p - 1, instead of computing the power directly.

Application:

1. Reduce the base modulo 31: 16937 = 31 x 546 + 11, so 16937 is congruent to 11 (mod 31).

2. 31 is prime and 11 is not divisible by 31, so Fermat's Little Theorem applies with p = 31.

3. The exponent 30 is exactly p - 1 = 30, so the theorem applies directly: 1130 is congruent to 1 (mod 31).

4. Therefore, 1693730 is congruent to 1130 is congruent to 1 (mod 31).

Cross-check (repeated squaring, independent of the Fermat shortcut):

1. 112 = 121, and 121 mod 31 = 28, which is congruent to -3 (mod 31).

2. 114 = (112)2 is congruent to (-3)2 = 9 (mod 31).

3. 116 = 114 x 112 is congruent to 9 x (-3) = -27, which is congruent to 4 (mod 31).

4. 1130 = (116)5 is congruent to 45 (mod 31).

5. 42 = 16, 44 = 162 = 256, which is congruent to 8 (mod 31), so 45 = 44 x 4 is congruent to 8 x 4 = 32, which is congruent to 1 (mod 31).

Both methods agree: the remainder is 1, matching the option "1".