Baltic Way 2018 · Problem 17
Number Theory
Prove that for any positive integers such that , the following inequality holds:
When you’re ready
Review material becomes available with the next Daily.
Review
Topics
Orders and residues
Solutions
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 .
Contest context
Results from Baltic Way 2018
11 teams
- Mean score
- 4.5 / 5
- Scores of 4 or 5
- 10 / 11
- Estonia
- 5 / 5
Score distribution
01
10
20
30
40
510
All team scores
| Team | Score |
|---|---|
| Germany | 5 / 5 |
| St. Petersburg | 5 / 5 |
| Denmark | 5 / 5 |
| Estonia | 5 / 5 |
| Sweden | 5 / 5 |
| Norway | 5 / 5 |
| Lithuania | 5 / 5 |
| Finland | 5 / 5 |
| Latvia | 5 / 5 |
| Poland | 5 / 5 |
| Iceland | 0 / 5 |