2017 Indonesia MO Problems/Problem 6
Problem
Find the number of positive integers not greater than 2017 such that divides for some positive integer .
Solution
Let where is relatively prime to
Since for all greater than or equal to 1, we have When the value is congruent to modulo By using similar steps, we can also show that if the value is congruent to modulo
Taking the equation modulo and using Fermat's Little Theorem, we have In order for that to be a multiple of then As long as is relatively prime to we can find a where
We have shown that we can find a if is a power of 2, power of 5, or a number relatively prime to 20 that is not a multiple of 17. By the Chinese Remainder Theorem, that means we can find a value for all numbers that are not a multiple of 17. There are numbers less than that meet the criteria.
See Also
2017 Indonesia MO (Problems) | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 7 |
All Indonesia MO Problems and Solutions |