# Partitions of Natural Numbers [duplicate]

This is a question from Complex analysis by Stein.

The question is

Prove that it is not possible to partition $\mathbb N$ into finitely many infinite AP's with distinct common differences.(other than the trivial $a=d=1$)

Infinite AP:=$\{a,a+d,a+2d,......\}$.I have no idea as to how to approach it. Any hints are welcome. Thanks.

-

## marked as duplicate by Grigory M, Dan Rust, 6005, M Turgeon, Eric StuckyMay 11 '14 at 2:25

Are you sure you've written the question correctly? – Hurkyl May 9 '14 at 9:06
What is wrong with $\{1, 3, 5, 7, \ldots\}$ and $\{2, 4, 6, 8, \ldots\}$? – Benjamin Dickman May 9 '14 at 9:06
@Hurkyl sorry forgot to add that common difference has to be different for all the infinite AP's which make up the partition. Thanks for pointing it out – happymath May 9 '14 at 9:13
@BenjaminDickman I think the problem with your solution is that the common difference is 2 in both cases. Is that correct @happymath? – gebruiker May 9 '14 at 9:34
@Aal Right; the OP edited in the "distinct common differences" after my comment. – Benjamin Dickman May 9 '14 at 9:36

There are a couple of proofs of this, but the complex-analysis tag points to D J Newman's proof. Corresponding to each arithmetic progression $a,a+d,a+2d,\dots$ is a generating function, $$x^a+x^{a+d}+x^{a+2d}+\cdots={x^a\over1-x^d}$$ To say the arithmetic progressions partition the natural numbers is to say the generating functions add up to $1/(1-x)$. This has a pole at $x=1$, and nowhere else. Now, consider the arithmetic progression with the greatest common difference --- call that common difference, $m$. Then the generating function for that AP will have a pole at $e^{2\pi i/m}$, which can't be cancelled by any of the other generating functions. So, we have a contradiction.
Exactly one of the generating functions has a pole at $e^{2\pi i/m$. Nothing else has a pole to cancel that pole. – Gerry Myerson May 9 '14 at 10:24
This is an old chestnut solvable by generating functions. For any infinite AP $\{a,a+d,a+2d, \dots\}$ consider the power series (generating function) $z^a + z^{a+d} + z^{a+2d} + \cdots$, which can be written as a rational function by summing the geometric series. The generating function for a disjoint union is the sum of the generating functions. So your hypothesized partition of $\Bbb N$ into infinite APs will give an expression for $x+x^2+x^3+\cdots = z/(1-z)$ (the generating function for $\Bbb N$) as a sum of these other rational functions. From there you should be able to derive a contradiction (which definitely requires something like the common differences are distinct...).