Determine the smallest positive integer for which there exist a prime number and a positive integer such that
Solution
If , our equation becomes , whose smallest solution in is .
Now let . Since and are coprime and , either or must be a square, and it is obviously not the latter; hence is a square. Assume that . Then
is a square, so either or is a square, but the former is (mod ), so the latter is the square: . Then , so both and are powers of and they must be and , but then , a contradiction. In conclusion, is the answer.
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.