Find every integer x with x = 2 mod 3, x = 3 mod 5 and x = 2 mod 7, give the smallest positive one, and count how many lie strictly below 10^6.

Find every integer x with x = 2 mod 3, x = 3 mod 5 and x = 2 mod 7, give the smallest positive one, and count how many lie strictly below 10^6.

Approach: Combine two congruences at a time into a single one on the product modulus, then count the arithmetic progression that results inside the stated range.

23. The moduli 3, 5 and 7 are pairwise coprime, so the Chinese remainder theorem gives a unique residue class modulo 105. Combining the first two, x = 2 mod 3 and x = 3 mod 5 means x = 3 + 5k with 3 + 5k = 2 mod 3, that is 2k = 2 mod 3, so k = 1 mod 3 and x = 8 mod 15. Combining with x = 2 mod 7, write x = 8 + 15m and require 8 + 15m = 2 mod 7, so 1 + m = 2 and m = 1 mod 7, giving x = 23 mod 105. Checking, 23 leaves 2, 3 and 2 on division by 3, 5 and 7. The solutions form the arithmetic progression 23 + 105 t for integer t, and counting solutions strictly below 10^6 needs 23 + 105 t < 1000000, so t <= 9523 and t >= 0 for positive values, giving 9524 of them.

Follow-up: If the moduli were 4, 6 and 9, when does a solution still exist, and what replaces the product as the period?

Key concepts: chinese remainder theorem, coprime moduli, arithmetic progression, counting solutions.