Take the 2-minute tour ×

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}$?

share|improve this question
What is $S$? I can only see $S_n$ in the question. –  user17762 Aug 14 '11 at 8:41
I 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. –  Gerry Myerson Aug 14 '11 at 8:48
This appeared on China TST 2005, but I didn't find any solutions for it... –  Amir Hossein Aug 14 '11 at 8:53

1 Answer 1

If anything is wrong or incomprehensible, feel free to comment. I'm a novice in english, so some sentence I make might have lots of grammar mistakes and fuzziness in reading it. I'll try to explain my thoughts as best as possible :D

First, we let $a_0 = 0$ and $a_{k+1} = p$, thus extending the sequence $\{a_i\}$.

We define $\{b_l\}_{l=0}^k$ to be $b_l = a_{l+1}- a_l$.

Note that for all $n \in S$,

$$\begin{align} \sum_{l=0}^k (n b_l)_p = {} & (na_1)_p + \left((na_2)_p - (na_1)_p\right) + \\ {} & \cdots + \left( (na_k)_p - \left(na_{k-1} \right)_p \right) + \left(p - (na_k)_p\right) \\ = {} & p \end{align}$$

Now we evaluate $$T = \sum_{n \in S}\sum_{l=0}^k (n b_l)_p$$ in two different ways. First way is to evaluate it straightforward using the formula above. $$T = \sum_{n \in S}\sum_{l=0}^k (n b_l)_p = \sum_{n \in S} p = p |S|$$

Second way is the following.

$$ \begin{align*} T = & \sum_{n \in S}\sum_{l=0}^k (n b_l)_p = \sum_{l=0}^k\sum_{n \in S} (n b_l)_p \geq \sum_{l = 0}^k \sum_{m = 1}^{|S|} m = \frac{(k+1)|S|(|S|+1)}{2} \end{align*} $$ Note that the inequality holds because for every $0 \leq l \leq k$ and $n_1, n_2 \in S$, if $n_1 \neq n_2$, $n_1b_l \not\equiv n_2b_l \mod p$. Therefore every $(nb_l)_p$ are different from each other and are bigger than 0 for each $l$.

Combining the results, we get $$p|S| = T \geq \frac{(k+1)|S|(|S|+1)}{2}$$ then $$\frac{2p}{k+1} \geq |S| + 1 > |S|$$

share|improve this answer

Your Answer


