Number theoryDifficulty 6.5National olympiadProve it
Let p≥5 be a prime number. For a positive integer k we denote by R(k) the remainder of k when divided by p. Determine all positive integers a
for every m=1,2,…,p−1. (Bulgaria) Alexander Ivanov
Solution
The required integers are p−1 along with all the numbers of the form ⌊p/q⌋,q=2,…,p−1. In other words, these are p−1, along with the numbers 1,2,…,⌊p⌋, and also the (distinct) numbers ⌊p/q⌋,q=2,…,⌊p−21⌋.
We begin by showing that these numbers satisfy the conditions in the statement. It is readily checked that p−1 satisfies the required inequalities, since m+R(m(p−1))=m+(p−m)=p>p−1 for all m=1,…,p−1.
Now, consider any number a of the form a=⌊p/q⌋, where q is an integer greater than 1 but less than p; then p=aq+r with 0≤r<a. Thus, a satisfies the required condition. If m≤q, then ma≤qa=p−r<p, so R(ma)=ma and m+R(ma)=m+ma=m(a+1)≤q(a+1)=p+q−r<p. If m>q, then ma≥(q+1)a=p+a−r>p, so R(ma)=ma−p=ma−(aq+r)=ma−aq−r=a(m−q)−r and m+R(ma)=m+a(m−q)−r=m+am−aq−r=m(a+1)−aq−r=m(a+1)−p+r>p.
Finally, we show that if an integer a∈(0,p−1) satisfies the required condition then a is indeed of the form a=⌊p/q⌋ for some integer q∈(0,p). This is clear for a=1, so we may (and will) assume that a≥2.
Write p=aq+r with q,r∈Z and 0≤r<a; since a≥2 we have q<p/2. Choose m=q+1<p; we have R(ma)=R(aq+a)=R(p+(a−r))=a−r, so
a<m+R(ma)=q+1+a−r,
which yields r<q+1. Moreover, if r=q, then p=q(a+1) which is impossible by 1<a+1<p. Thus r<q, and we have
0≤qp−a=qr<1,
which proves a=⌊p/q⌋.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.