# Partitioning a progression

Let $P$ be a $Z_N$ progression of length $R$.Prove that we can partition $P$ into at most $4 \sqrt R$ genuine arithmetic progressions. (Genuine arithmetic progression means arithmetic progression in $\mathbb {N}$).

In order to prove this I assume that the progression $P$ is $a+ jq$ with $1 \leq j \leq R$. By Dirichlet's theorem, there exists $l \leq \sqrt R , b\in \mathbb {N}$ such that $|\frac { l}{N} - \frac {b}{q}|\leq \frac {R^{-\frac { 1}{2}} } {q}$.we can divide $P$ into sub-progressions of $j$ ( mod $l$ ).

How can I continue?

Is there any hint how to prove the statement?