Sum of residue systems is complete iff they are both complete

elementary-number-theorymodular arithmeticnumber theoryreduced-residue-system

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!

Best Answer

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.

Related Question