Complete Residue System modulo m (Fall 2021 AMC 12A #25)
Fall 2021 AMC 12A #25 Problem: Let m\geq 5 be an odd integer, and let D(m) denote the number of quadruples (a_1, a_2, a_3, a_4) of distinct integers with 1\leq a_i \leq m for all i such that m divides a_1+a_2+a_3+a_4. There is a polynomial q(x) = c_3x^3+c_2x^2+c_1x+c_0 such that D(m) = q(m) for all odd integers m\geq 5. What is c_1? Solution: First, we must find a way to account for the number of ordered quadruples (a_1, a_2, a_3, a_4) such that m divides a_1+a_2+a_3+a_4. We know that there are (m)(m-1)(m-2)(m-3) total ordered quadruples since all elements must be distinct. First we can list out the sums of m quadruples of the form (a_1+n, a_2+n, a_3+n, a_4+n) where n takes on the values from 0 to m-1 and all elements of the quadruple are modulo m. This means that the m quadruples have the same difference between consecutive elements modulo m. If we let the sum S = a_1+a_2+a_3+a_4, we have $(a_1, a_2, a_3, a_4) \Rightarr...