Maths Olympiad Prep

Library / /278 of 520

Number theory Difficulty 6.5 National olympiad Prove it

Let p5p \geq 5 be a prime number. For a positive integer kk we denote by R(k)R(k) the remainder of kk when divided by pp. Determine all positive integers aa

for every m=1,2,,p1m=1,2, \ldots, p-1.
(Bulgaria) Alexander Ivanov

Solution

The required integers are p1p-1 along with all the numbers of the form p/q,q=\lfloor p / q\rfloor, q= 2,,p12, \ldots, p-1. In other words, these are p1p-1, along with the numbers 1,2,,p1,2, \ldots,\lfloor\sqrt{p}\rfloor, and also the (distinct) numbers p/q,q=2,,p12\lfloor p / q\rfloor, q=2, \ldots,\left\lfloor\sqrt{p}-\frac{1}{2}\right\rfloor.

We begin by showing that these numbers satisfy the conditions in the statement. It is readily checked that p1p-1 satisfies the required inequalities, since m+R(m(p1))=m+(pm)=m+R(m(p-1))=m+(p-m)= p>p1p>p-1 for all m=1,,p1m=1, \ldots, p-1.

Now, consider any number aa of the form a=p/qa=\lfloor p / q\rfloor, where qq is an integer greater than 1 but less than pp; then p=aq+rp=a q+r with 0r<a0 \leq r < a. Thus, aa satisfies the required condition. If mqm \leq q, then maqa=pr<pm a \leq q a = p - r < p, so R(ma)=maR(m a) = m a and m+R(ma)=m+ma=m(a+1)q(a+1)=p+qr<pm + R(m a) = m + m a = m (a + 1) \leq q (a + 1) = p + q - r < p. If m>qm > q, then ma(q+1)a=p+ar>pm a \geq (q + 1) a = p + a - r > p, so R(ma)=map=ma(aq+r)=maaqr=a(mq)rR(m a) = m a - p = m a - (a q + r) = m a - a q - r = a (m - q) - r and m+R(ma)=m+a(mq)r=m+amaqr=m(a+1)aqr=m(a+1)p+r>pm + R(m a) = m + a (m - q) - r = m + a m - a q - r = m (a + 1) - a q - r = m (a + 1) - p + r > p.

Finally, we show that if an integer a(0,p1)a \in(0, p-1) satisfies the required condition then aa is indeed of the form a=p/qa=\lfloor p / q\rfloor for some integer q(0,p)q \in(0, p). This is clear for a=1a=1, so we may (and will) assume that a2a \geq 2.

Write p=aq+rp=a q+r with q,rZq, r \in \mathbb{Z} and 0r<a0 \leq r < a; since a2a \geq 2 we have q<p/2q < p / 2. Choose m=q+1<pm=q+1<p; we have R(ma)=R(aq+a)=R(p+(ar))=arR(m a)=R(a q+a)=R(p+(a-r))=a-r, so

a<m+R(ma)=q+1+ar, a<m+R(m a)=q+1+a-r,

which yields r<q+1r<q+1. Moreover, if r=qr=q, then p=q(a+1)p=q(a+1) which is impossible by 1<a+1<p1<a+1<p. Thus r<qr<q, and we have

0pqa=rq<1, 0 \leq \frac{p}{q}-a=\frac{r}{q}<1,

which proves a=p/qa=\lfloor p / q\rfloor.

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.