Browse · MathNet
PrintCroatian Mathematical Olympiad
Croatia number theory
Problem
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.
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.
Final answer
1
Techniques
Fermat / Euler / Wilson theoremsMultiplicative orderGreatest common divisors (gcd)Prime numbers