Problem:
Denote by the set of positive rational numbers. A function satisfies
- for all primes , and
- for all .
For which positive integers does the equation have at least one solution in ?
Solution
Solution:
We claim that either is the product of distinct primes, or .
Define . The equation we are trying to solve becomes .
The definition of the function becomes for all primes , and
Substituting in the above yields . Letting in (1) and using gives for all in .
An easy induction then proves that
for positive integers and in .
This gives
for prime and positive integers .
These facts, combined, give us the general formula for in terms of the prime factorizations of and :
for some integer . Observe that the denominator is a product of distinct primes. Thus, if for some , then either is the product of distinct primes, or .
It remains to prove that all such have such a solution .
When , taking for some prime works by (3).
We now prove that if for some and positive integer , then there exists such that , for any prime relatively prime to . This finishes the problem by induction.
Let and be integers whose values will be determined later. Observe that, by (2), . By (3), we get . Finally, using (1) on and gives
It remains to choose integers and such that . But by Bézout's identity, as the greatest common divisor of and is 1, there do exist such integers. Taking then gives , finishing the problem.