Find all positive integers such that
is an integer.
Solution
Since , it follows that , hence .
Note that must be odd (otherwise the even would divide the odd , which is impossible).
Let be the smallest prime factor of the odd . Obviously , hence by Fermat's little theorem we have . We also have .
Let be the order of modulo . Then and . Since and , it must be , i.e. .
Considering and , it follows that , which contradicts the assumption about the existence of prime factor of . Hence , i.e. , and that is indeed the only solution.
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.