2 improved formatting

There must be an easier proof but here is a nice approach which can indeed lead to deeper results (feel free to edit for math display, I tried): Techniques with characteristic polynomials and roots of unity can be very powerful. I like the way that the appropriate lemmas are explained in my paper with Ethan Coven "Tiling the Integers with Translates of One Finite Set" http://arxiv.org/abs/math/9802122 or Journal of Algebra v 212 (1988) p 161-174. One does not need their full generality for this problem but perhaps for deeper results.

I'll sketch this result which implies what was asked for: Suppose that A and B are sets of size #A and #B so that A+B is a complete set of residues mod N=#A#B. Let p be a prime dividing N. Then exactly one of the sets has its members equally distributed mod p.

digression: Lemma 3.2 from the paper above (not needed here) shows that at least one of the following is true:

1) No member of A-A is relatively prime to #B

2) No member of B-B is relatively prime to #A end of digression

Consider the corresponding polynomials $A(x)=\sum_{a \in A}x^a$ and $B(x)=\sum_{b \in B}x^b$. Then

i) A(1)=#A and B(1)=#B

ii) A(x)B(x) is a sum of N distinct powers of x, one from each residue class.

iii) $A(x)B(x)=(x^N-1)Q(x)+\frac{x^N-1}{x-1}$ for some polynomial Q(x).

iv) Every irreducible polynomial dividing $\frac{x^N-1}{x-1}$ divides at least one of $A(x)$ and $B(x)$

As an example consider A={0,9,13,16,29,32} B={0,10,12,22,24,34} with A+B a complete set of residues mod N=36.

$$\frac{x^36-1}{x-1}=(x+1)(x^2+x+1)(x^2+1)(x^2-x+1)(x^4+x^2+1)(x^4-x^2+1)(x^18-x^9+1)$$$\frac{x^{36}-1}{x-1}=(x+1)(x^2+x+1)(x^2+1)(x^2-x+1)(x^4+x^2+1)(x^4-x^2+1)(x^{18}-x^9+1)$$ evaluated at x=1 this becomes 36=2 * 3 * 2 * 1 * 3 * 1 In general the irreducible polynomial divisors of \frac{x^N-1}{x-1} are the cyclotomic polynomials corresponding to the divisors of N. Evaluated at x=1 each is either 1 (composite divisor) or a prime p (prime power divisor) and the primes have product N. Since A(1)B(1)=N and A(x)B(x) is divisible by all the prime power cyclotomic divisors of \frac{x^N-1}{x-1} and these evaluated at 1 also have product N, each divides just one of A(x) or B(x) and all other polynomial divisors evaluate to 1 at 1. In particular: for each prime divisor of N, only one of A(X), B(x) divides by \frac{x^p-1}{x-1} and only that one has corresponding set equidistributed mod p. In our example A is a complete set of residues mod 6 so A(x) divides by (1+x) and by (1+x+x^2). Since A(1)=6 , A(x) can't have either of (1+x^2) and (1+x^2+x^4) as factors. But they do divide A(x)B(x) and hence they divide B(x). This means that neither (1+x) nor (1+x+x^2) can divide B(x), again since B(1)=6. Hence, B is not equidistributed mod 2 (or mod 3) and certainly not mod 6. By the way, B(x)=(X^10+1)(x^24+x^12+1) B(x)=(x^{10}+1)(x^{24}+x^{12}+1) and A(x)=(x^13+1)(x^32+x^16+1) A(x)=(x^{13}+1)(x^{32}+x^{16}+1) (mod x^36-1)x^{36}-1) 1 There must be an easier proof but here is a nice approach which can indeed lead to deeper results (feel free to edit for math display, I tried): Techniques with characteristic polynomials and roots of unity can be very powerful. I like the way that the appropriate lemmas are explained in my paper with Ethan Coven "Tiling the Integers with Translates of One Finite Set" http://arxiv.org/abs/math/9802122 or Journal of Algebra v 212 (1988) p 161-174. One does not need their full generality for this problem but perhaps for deeper results. I'll sketch this result which implies what was asked for: Suppose that A and B are sets of size #A and #B so that A+B is a complete set of residues mod N=#A#B. Let p be a prime dividing N. Then exactly one of the sets has its members equally distributed mod p. digression: Lemma 3.2 from the paper above (not needed here) shows that at least one of the following is true: 1) No member of A-A is relatively prime to #B 2) No member of B-B is relatively prime to #A end of digression Consider the corresponding polynomials A(x)=\sum_{a \in A}x^a and B(x)=\sum_{b \in B}x^b. Then i) A(1)=#A and B(1)=#B ii) A(x)B(x) is a sum of N distinct powers of x, one from each residue class. iii) A(x)B(x)=(x^N-1)Q(x)+\frac{x^N-1}{x-1} for some polynomial Q(x). iv) Every irreducible polynomial dividing \frac{x^N-1}{x-1} divides at least one of A(x) and B(x) As an example consider A={0,9,13,16,29,32} B={0,10,12,22,24,34} with A+B a complete set of residues mod N=36. $$\frac{x^36-1}{x-1}=(x+1)(x^2+x+1)(x^2+1)(x^2-x+1)(x^4+x^2+1)(x^4-x^2+1)(x^18-x^9+1)$$ evaluated at$x=1$this becomes 36=2 * 3 * 2 * 1 * 3 * 1 In general the irreducible polynomial divisors of$\frac{x^N-1}{x-1}$are the cyclotomic polynomials corresponding to the divisors of N. Evaluated at x=1 each is either 1 (composite divisor) or a prime p (prime power divisor) and the primes have product N. Since A(1)B(1)=N and A(x)B(x) is divisible by all the prime power cyclotomic divisors of$\frac{x^N-1}{x-1}$and these evaluated at 1 also have product N, each divides just one of A(x) or B(x) and all other polynomial divisors evaluate to 1 at 1. In particular: for each prime divisor of N, only one of A(X), B(x) divides by$\frac{x^p-1}{x-1}$and only that one has corresponding set equidistributed mod p. In our example A is a complete set of residues mod 6 so A(x) divides by (1+x) and by (1+x+x^2). Since A(1)=6 , A(x) can't have either of (1+x^2) and (1+x^2+x^4) as factors. But they do divide A(x)B(x) and hence they divide B(x). This means that neither (1+x) nor (1+x+x^2) can divide B(x), again since B(1)=6. Hence, B is not equidistributed mod 2 (or mod 3) and certainly not mod 6. By the way,$B(x)=(X^10+1)(x^24+x^12+1)$and$A(x)=(x^13+1)(x^32+x^16+1)$(mod$x^36-1\$)