Given prime number $p$. $a_1,a_2 \cdots a_k$ ($k \geq 3$) are integers not divible by $p$ and have different residuals when divided by $p$. Let \[ S_n= \{ 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$. Prove that $|S|< \frac{2p}{k+1}$.
Problem
Source: China TST 2005
Tags: number theory unsolved, number theory
ywl
05.07.2009 18:54
Can anyone help? I've been stuck on this problem
math154
22.09.2011 00:26
See this.
CANBANKAN
18.05.2023 20:13
CTST 23/3 and ISL 19 N6
. Solution: Note that $\{ \frac{na_j}{p} \} < \{ \frac{na_{j+1}}{p}\} \iff \{ \frac{na_j}{p} \} + \{ \frac{n(a_{j+1}-a_j)}{p} \} = \{ \frac{na_{j+1}}{p}\}$ Therefore, if $x_1=a_1, x_j=a_j-a_{j-1}$ for $j=2,\cdots,k$ and $x_{k+1}=p-a_k$ then $$\sum_{j=1}^{k+1} \{\frac{na_j}{p}\} = 1$$ Consider the sum $\sum_{s\in S} \sum_{j=1}^{k+1} \{\frac{sa_j}{p}\}$. On one hand it is equal to $|S|$. On the other hand, it is $\sum_{j=1}^{k+1} \sum_{s\in S} \{\frac{sa_j}{p}\} \ge (k+1) \frac{|S| (|S|+1)}{2p}$. Hence $|S|+1 \le \frac{2p}{k+1}$, as desired.