Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.