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...