Skip to main content
OlympiadHQ

Browse · MathNet

Print

BMO 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 .
Final answer
all even positive integers

Techniques

Quadratic residuesPrime numbersGreatest common divisors (gcd)