Browse · MathNet
PrintMathematica competitions in Croatia
Croatia number theory
Problem
Let be an odd positive integer greater than . Let denote the least positive integer such that is a perfect square and denote the least positive integer such that is a perfect square. Prove that is a prime number if and only if and . (V.I. Bernik, I.K. Zhuk, O.V. Melnikov, Collection of Problems in Math. Olympiads)
Solution
If is a prime number, then so it is obvious that . For we have: , so In each case, adding these two equations gives us . If (i.e. since is prime), then it would be , i.e. . This is not possible since there are no perfect squares between and . We will prove that there does not exist an odd composite number such that and . Assume on the contrary that such exists. We can write in the form with different prime numbers. Clearly, and we have Hence , so , i.e. Let denote the smallest number greater than such that is divisible by (such exists since is divisible by ). Clearly , and it is easy to see that . Now we can write in the form , where for some , and is the product of all for . Since is a composite number it follows that . By the Chinese remainder theorem there exists a unique , , such that Now look at the number . We have: so . Therefore, both and are candidates for . Clearly, one of them is less than , so , which is a contradiction.
Techniques
Chinese remainder theoremPrime numbers