4
$\begingroup$

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

  • 0
    This appeared on China TST 2005, but I didn't find any solutions for it...2011-08-14

1 Answers 1

4

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