1
$\begingroup$

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.

$\endgroup$

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.