Problem:
Let p be a prime number and let s be an integer with 0<s<p. Prove that there exist integers m and n with 0<m<n<p and
{psm​}<{psn​}<ps​
if and only if s is not a divisor of p−1.
(For x a real number, let ⌊x⌋ denote the greatest integer less than or equal to x, and let {x}=x−⌊x⌋ denote the fractional part of x.)
Solution:
First Solution. First suppose that s is a divisor of p−1; write d=(p−1)/s. As x varies among 1,2,…,p−1,{sx/p} takes the values 1/p,2/p,…,(p−1)/p once each in some order. The possible values with {sx/p}<s/p are precisely 1/p,…,(s−1)/p. From the fact that {sd/p}=(p−1)/p, we realize that the values {sx/p}=(p−1)/p,(p− 2)/p,…,(p−s+1)/p occur for
x=d,2d,…,(s−1)d
(which are all between 0 and p ), and so the values {sx/p}=1/p,2/p,…,(s−1)/p occur for
x=p−d,p−2d,…,p−(s−1)d
respectively. From this it is clear that m and n cannot exist as requested.
Conversely, suppose that s is not a divisor of p−1. Put m=⌈p/s⌉; then m is the smallest positive integer such that {ms/p}<s/p, and in fact {ms/p}=(ms−p)/p. However, we
cannot have {ms/p}=(s−1)/p or else we would have (m−1)s=p−1, contradicting our hypothesis that s does not divide p−1. Hence the unique n∈{1,…,p−1} for which {nx/p}=(s−1)/p has the desired properties (since the fact that {nx/p}<s/p forces n≥m, but mî€ =n).
Second Solution. We prove the contrapositive statement:
Let p be a prime number and let s be an integer with 0<s<p. Prove that the following statements are equivalent:
(a) s is a divisor of p−1;
(b) if integers m and n are such that 0<m<p,0<n<p, and
{psm​}<{psn​}<ps​
then 0<n<m<p.
Since p is prime and 0<s<p,s is relatively prime to p and
S={s,2s,…,(p−1)s,ps}
is a set of complete residues classes modulo p. In particular,
(1) there is an unique integer d with 0<d<p such that sd≡−1(modp); and
(2) for every k with 0<k<p, there exists a unique pair of integers (mk​,ak​) with 0<mk​<p such that mk​s+ak​p=k.
Now we consider the equations
m1​s+a1​p=1,m2​s+a2​p=2,…,ms​s+as​p=s
Hence
{pmk​s​}=pk​
for 1≤k≤s.
Statement (b) holds if and only 0<ms​<ms−1​<⋯<m1​<p. For 1≤k≤s−1, mk​s−mk+1​s=(ak+1​−ak​)p−1, or (mk​−mk+1​)s≡−1(modp). Since 0<mk+1​< mk​<p, by (1), we have mk​−mk+1​=d. We conclude that (b) holds if and only if ms​,ms−1​,…,m1​ form an arithmetic progression with common difference −d. Clearly ms​=1, so m1​=1+(s−1)d=jp−d+1 for some j. Then j=1 because m1​ and d are both positive and less than p, so sd=p−1. This proves (a).
Conversely, if (a) holds, then sd=p−1 and mk​≡−dsmk​≡−dk(modp). Hence mk​=p−dk for 1≤k≤s. Thus ms​,ms−1​,…,m1​ form an arithmetic progression with common difference −d. Hence (b) holds.
This problem was proposed by Kiran Kedlaya.
The problems on this page are the property of the MAA's American Mathematics Competitions