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?

Thanks in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.