Given a prime number $p$. Let $a_1,a_2 \cdots a_k$ ($k \geq 3$) be integers not divisible by $p$ and having different residuals when divided by $p$. Let $$ S= \{ n \mid 1 \leq n \leq p-1, (na_1)_p < \cdots < (na_k)_p \} $$ Here $(b)_p$ denotes the residual when integer $b$ is divided by $p$. How can one prove that $|S|< \frac{2p}{k+1}$?
Prove that $|S|< \frac{2p}{k+1}$
4
$\begingroup$
number-theory
-
1What is $S$? I can only see $S_n$ in the question. – 2011-08-14
-
0I did a little editing. Why do you believe $|S|\lt2p/(k+1)$? Is this an exercise from some book? The more information you give, the more likely someone can answer. – 2011-08-14
-
0This appeared on China TST 2005, but I didn't find any solutions for it... – 2011-08-14