Browse · MathNet
PrintBMO Short List
number theory
Problem
Determine all positive integers such that is a positive integer for some positive integers and .
Solution
The required numbers are all even positive integers alone. Indeed, if is even, then let and , to check that .
Suppose now that such and exist for some positive odd integer . Notice that we may and will assume . Note also that . If is odd, then is divisible by , and hence so is . Since is odd, is therefore divisible by , which is impossible. Thus, must be even. Then , so has a prime factor . Then is divisible by , and it follows that so are both and , since . On the other hand, since and are both divisible by , so is . Consequently, , and are all divisible by , contradicting the assumption .
Suppose now that such and exist for some positive odd integer . Notice that we may and will assume . Note also that . If is odd, then is divisible by , and hence so is . Since is odd, is therefore divisible by , which is impossible. Thus, must be even. Then , so has a prime factor . Then is divisible by , and it follows that so are both and , since . On the other hand, since and are both divisible by , so is . Consequently, , and are all divisible by , contradicting the assumption .
Final answer
all even positive integers
Techniques
Quadratic residuesPrime numbersGreatest common divisors (gcd)