Finitely many arithmetic progressions

Question

A few years ago, somebody told me a lovely problem. I suspect there may be more to it (which I would be interested in learning), and would very much like to find a reference, it makes me uncomfortable to use it in class without being able to point to its source.

The problem is as follows. I'll post the solution I know, which is the reason I like it, as an answer, to give a bit of a chance to people who read it and want to think about it without being spoiled.

Assume the natural numbers are partitioned into finitely many arithmetic progressions. Then two of these progressions must have the same common difference.

Answer 1

You're probably thinking of the proof, via generating functions, due to D J Newman. I don't have a reference to the first appearance in print, but it's in his book, A Problem Seminar, problem 90, on page 18, with solution on page 100.

I suppose that when you state the problem you must require finitely many but at least two arithmetic progressions.

Answer 2

This was one of my favourite problems in high school. My proof went like this: if you look at the problem modulo n where n is the least common multiple of the differences of the arithmetic progressions then you can rephrase the problem as follows: if the vertices of a regular n-gon are partitioned into regular k-gons centered at the origin then two of them will have the same size. To prove this arrange the regular n-gon to have vertices at the nth roots of unity in the complex plane and assign the monic polynomial to every individual k-gon whose roots are exactly the vertices of the polygon. This way you will get the expression $x^n-1=(x^{k_1}-\zeta_1)(x^{k_2}-\zeta_2)\cdots$. Multiplying out the RHS we see that if $k_1$ is the least of the $k_i$'s then the only way to cancel the term of $x^{k_1}$ from the RHS is to have another $k_i=k_1$ proving the claim.

Answer 3

Assign to each progression $A_i=(a_i+kb_i\mid k\in{\mathbb N})$, $1\le i\le n$, its generating series, $f_i(x)=\sum_{k=0}^\infty x^{a_i+kb_i}$. Then $f_i(x)=x^{a_i}/(1-x^{b_i})$. Note the series converges for $|x|<1$.

Now, since the $A_i$ partition ${\mathbb N}$, we have $\sum_{i=1}^n f_i(x)=1/(1-x)$. If all the $b_i$ are different, let $b$ be the largest, and fix a primitive $b$-th root of unity $\zeta$. Now let $x\to\zeta$ to reach a contradiction.

This shows that the largest of the common differences must appear at least twice.

Answer 4

Chapter one of the Mathematical Coloring Book discuss this problem. There you will found some of its history. Apparently it was conjecture by Erdös in 1950 and proved (but not published) a few months later by Donald Newman and Leon Misrky.

Answer 5

This is "the same" as the generating function proof, but it doesn't use generating functions explicitly. Take the largest common difference in any of the sequences, say n, and pick $\zeta$ a primitive n-th root of unity. To each positive integer $m$, associate the complex number $\zeta^m$. Note that in any arithmetic sequence with common difference less than n, the sum over its entries of $\zeta^m$ stays bounded, while for an arithmetic sequence of common difference n, it grows unboundedly. Since the sum over all integers stays bounded, there has to be a second sequence of common difference n to balance out the first one.