MathDB

USAMO Inequality chain for getting started on the contest

Source: USAMO 2006, Problem 1, proposed by Kiran Kedlaya

April 20, 2006

USA(J)MOUSAMOinequalitiesfloor functionmodular arithmeticpigeonhole principleHi

Problem Statement

Let

p

be a prime number and let

\left \{\frac{sm}{p} \right\} < \left \{\frac{sn}{p} \right \} < \frac{s}{p}

be an integer with

0 < s < p.

Prove that there exist integers

m

and

n

with

0 < m < n < p

and

\left \{\frac{sm}{p} \right\} < \left \{\frac{sn}{p} \right \} < \frac{s}{p}

if and only if

s

is not a divisor of

p-1

. Note: For

x

a real number, let

\lfloor x \rfloor

denote the greatest integer less than or equal to

x

, and let

\{x\} = x - \lfloor x \rfloor

denote the fractional part of x.

Back to Problems View on AoPS