Sum of residue systems is complete iff they are both complete Let $p$ and $q$ be distinct prime numbers. The integers $a_1, \ldots, a_p$ and $b_1,\ldots,b_q$ are such that the sums $a_i + b_j$ form a complete residue system modulo $pq$ (that is, there is precisely one sum which is $0$ mod $pq$, precisely one which is $1$ mod $pq$, etc.). Prove that $a_1,\ldots,a_p$ form a complete residue system mod $p$ and $b_1,\ldots,b_q$ form a complete residue system mod $q$.
Any idea on how to approach this? Any help appreciated!
 A: Here's an idea.
Suppose $\{a_i+b_j\}_{i,j}$ forms a complete residue system mod $pq$. Then $$0 = \sum_{k=0}^{pq-1} k = \sum_{i,j} (a_i+b_j) = q(a_1+\dots+a_p)+p(b_1+\dots+b_q) \pmod{pq}.$$ This implies $$a_1+\dots+a_p \equiv 0 \pmod{p}$$ and $$b_1+\dots+b_q \equiv 0 \pmod{q}.$$ Using these, and that $$\sum_{i,j} (a_i+b_j)^2 = q(a_1^2+\dots+a_p^2)+p(b_1^2+\dots+b_q^2)+2(a_1+\dots+a_p)(b_1+\dots+b_q),$$ we obtain $$a_1^2+\dots+a_p^2 \equiv 0 \pmod{p}$$ and $$b_1^2+\dots+b_q^2 \equiv 0 \pmod{q}.$$ We can continue like this to get higher and higher moments (it stops at $p-1$ for $a_i$'s and $q-1$ for $b_i$'s, I think). I wonder if this implies $\{a_i\}_i$ is a complete residue system or is all $0$s. Same with $\{b_j\}_j$.
A: Let's assume $p<q$. You can only conclude that the the $a_i$'s form  a complete system of residues modulo $p$. Let's note  that $\displaystyle \sum_{k=0}^{pq-1} k^t\equiv 0 \pmod{p}$ if and only if $p-1\nmid t$ and $\displaystyle \sum_{k=0}^{pq-1} k^t\equiv -q\pmod{p}$ for $p-1|t$. Same goes for switching $p$ and $q$.
Inductively one can show that $\displaystyle \sum_{i=1}^{p} a_i^{n}\equiv 0 \pmod{p}$ for $n\leq p-2$;this formalizes mathworkers post . More precisely if we denote with $\displaystyle A_n=\sum_{i=1}^p a_i^n$ and $\displaystyle B_n=\sum_{i=1}^q b_i^n$ we have
$$\sum_{i,j} (a_i+b_j)^n=\sum_{k=1}^{n-1} A_k B_{n-k} \dbinom{n}{k}+qA_n+pB_n$$
Now for $n=p-1$ we have $\displaystyle \sum_{k=0}^{pq-1} k^t\equiv -q \pmod{pq}$ and thus $A_{p-1}\equiv -1\pmod{p}$. Now Fermat's little theorem gives $a_i^{p-1} \equiv \{0,1\} \pmod{p}$ and thus we must have one number divisible by $p$ and $p-1$ coprime with $p$ amongst the $a_i$. Wlog $p|a_1$.
Now considering the polynomial $\displaystyle f(X)=\prod_{i=2}^{p} (X-a_i)$ in $\mathbb{F}_p[X]$ we can show that all the coefficients are zero; these are symmetric sums in the $a_i$ and using Newton's relations between power sums and symmetric sums. Thus $f(X)=X^{p-1}-a$ and since $a_{i}^{p-1}\equiv 1 \pmod{p}$ we have $a=1$. Since $\displaystyle X^{p-1}-1=\prod_{j=1}^{p-1} (X-j) $ in $\mathbb{F}_p[X]$ we have shown that $\{a_i\}_{i=1}^p$ form a complete system of residues modulo $p$.
Note that the same strategy guarantees that $q|B_n$ for $n<q-1$ using the same recurrence relation. By the same argument as above one gets that $\{b_i\}$ form a complete system of residues mod $q$ also.
