Assume the positive integers $\mathbb{N}$ are partitioned as $$\mathbb{N} = \cup_{i = 1}^n (a_i + b_i \mathbb{N})$$ where $a_i, b_i \in \mathbb{N}$. Prove that all such partitions are obtained by the following algorithm: partition $\mathbb{N}$ into a finite number of a.p.'s with equal steps, then partition one of these a.p.'s into a further union of a.p.'s with equal steps, then take one of the remaining a.p.'s (either with the first or second obtained step) and partition further into a.p.'s with equal steps etc.

A similar question has already been asked [1], but not about the structure. This question is posed as Problem 1.5., p. 6, in Mathematical Coloring Book, and is claimed to be equivalent to Problem 1.4. on the same page, however after some checking I couldn't see this. I imagine this is well studied.

An attempt at proving the claim: using generating functions as in [1], one has $$\frac{1}{1-x} = \sum_{i = 1}^k \frac{x^{a_i}}{1 - x^{b_i}}$$ Let $B = \max\{b_i\}$ and $S = \{i \mid b_i = B\}$. Then $|S| \geq 2$ and since the $B$-th cyclotomic polynomial $\Phi_B$ is irreducible, we must have $$\Phi_B(x) Q(x) = \sum_{i \in S} x^{a_i}$$ with $Q(x) \in \mathbb{Z}[x]$, where $a_i$ are taken modulo $B$. The claim would be to prove that $a_i$'s for $i \in S$ form themselves a finite disjoint union of arithmetic progressions (modulo $B$) and by induction on the number of steps in the algorithm above to prove the claim. This leads to studying vanishing sums of roots of unity as in e.g. article below, but I haven't succeeded in finding such a claim.

*Mann, Henry B.*, **On linear relations between roots of unity**, Mathematika, Lond. 12, 107-117 (1965). ZBL0138.03102.