Prove using strong induction that congruence modulus some number is a valid partition for the naturals. A valid partition of the naturals will assign all natural numbers to one or more subsets. For our example for congruence mod 3, {0, 3, 6..) will be in one subset, {1,4,7,..) another, and so forth