What is the remainder when 650 is divided by 215?

Concept: For a number written in the form (kd + 1)n, dividing by d always leaves remainder 1. This follows from the Binomial Theorem: every term in the expansion of (kd + 1)n contains a factor of d except the last term, 1n = 1.

1. Write 650 as a power of 216, since 216 = 63: 650 = 648 × 62 = (63)16 × 36 = 21616 × 36.

2. Note that 216 = 215 + 1, so 216 is of the form (kd + 1) with k = 1 and d = 215.

3. By the Concept above, 21616 leaves remainder 1 when divided by 215, i.e., 21616 = 215m + 1 for some integer m.

4. Substitute this back: 650 = 21616 × 36 = (215m + 1) × 36 = 215 × 36m + 36.

5. The term 215 × 36m is exactly divisible by 215, so the remainder is 36.

Cross-check: Verify using the Chinese Remainder Theorem with 215 = 5 × 43. Since 6 ≡ 1 (mod 5), 650 ≡ 1 (mod 5). Since 43 is prime, Fermat's Little Theorem gives 642 ≡ 1 (mod 43), so 650 ≡ 68 (mod 43); computing 62 = 36, 64 = 1296 ≡ 6 (mod 43), 68 = 62 = 36 (mod 43). The unique value modulo 215 satisfying ≡ 36 (mod 43) and ≡ 1 (mod 5) is 36 itself (since 36 mod 5 = 1), confirming the remainder is 36.