Skip to main content
OlympiadHQ

Browse · MathNet

Print

Baltic Way shortlist

Baltic Way number theory

Problem

Prove, that for any , such that , following inequality holds:
Solution
We can assume that and are coprime, and since both sides of first inequality are positive, we can change it to . The same way we can change second inequality: To see this one holds, we will prove stronger one: Indeed, dividing this inequality by we get , and since we already know that we only have to see, that can't be equal to . Since we know that the only reminders of squares (mod 11) are 0, 1, 3, 4, 5 and 9, can't be divisible by 11, and therefore .

Techniques

Quadratic residuesLinear and quadratic inequalities