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) \Rightarrow S$
• $(a_1+1, a_2+1, a_3+1, a_4+1) \Rightarrow S + 4*1$
• $(a_1+2, a_2+2, a_3+2, a_4+2) \Rightarrow S + 4*2$
• $...$
• $(a_1+(m-2), a_2+(m-2), a_3+(m-2), a_4+(m-2)) \Rightarrow S + 4*(m-2)$
• $(a_1+(m-1), a_2+(m-1), a_3+(m-1), a_4+(m-1)) \Rightarrow S + 4*(m-1)$,

The key insight here is that since $\gcd(4, m) = 1$ because $m$ is odd, the sums of the $m$ quadruples ($S$ to $S+4*(m-1)$) form a complete residue system. This just means that each of the $m$ sums is congruent modulo $m$ to exactly one integer of the set $\{0, 1, 2, 3, ..., m-2, m-1\}$.

So, of the $(m-1)(m-2)(m-3)$ sets of $m$ ordered quadruples, where quadruples with the same difference between consecutive elements modulo $m$ are grouped, only one quadruple in each set of $m$ ordered quadruples is congruent to $0$ mod $m$.

Thus, we have that the total number of quadruples satisfying the condition is $D(m) = \frac{1}{m}[(m)(m-1)(m-2)(m-3)] = (m-1)(m-2)(m-3) = q(m)$. So, we have that $c_1 = 1*2 + 1*3 + 2*3 = 11$ (which we can find my expanding or using by Vieta's Formulas).

Note: An alternate, but much longer way to solve this would be to find $D(m)$ for $m = 5,7,9,11$ and solve for $c_3, c_2, c_1, c_0$ with a system of equations, but there is a high likelihood of making a mistake.