Maths Olympiad Prep

Library / /120 of 128

Algebra Difficulty 7.2 National Olympiad, round 2 Prove it Philippines

Problem:
Denote by Q+\mathbb{Q}^{+} the set of positive rational numbers. A function f:Q+Qf: \mathbb{Q}^{+} \rightarrow \mathbb{Q} satisfies
- f(p)=1f(p)=1 for all primes pp, and
- f(ab)=af(b)+bf(a)f(a b)=a f(b)+b f(a) for all a,bQ+a, b \in \mathbb{Q}^{+}.
For which positive integers nn does the equation nf(c)=cn f(c)=c have at least one solution cc in Q+\mathbb{Q}^{+}?

Solution

Solution:
We claim that either nn is the product of distinct primes, or n=1n=1.

Define g(x)=fxg(x)=\frac{f}{x}. The equation we are trying to solve becomes g(c)=1ng(c)=\frac{1}{n}.

The definition of the function becomes g(p)=1pg(p)=\frac{1}{p} for all primes pp, and
g(ab)=g(a)+g(b) g(a b)=g(a)+g(b)
Substituting a=1a=1 in the above yields g(1)=0g(1)=0. Letting b=1ab=\frac{1}{a} in (1) and using g(1)=0g(1)=0 gives g(a)=g(1a)g(a)=-g\left(\frac{1}{a}\right) for all aa in Q+\mathbb{Q}^{+}.

An easy induction then proves that
g(an)=ng(a) g\left(a^{n}\right)=n g(a)
for positive integers nn and aa in Q+\mathbb{Q}^{+}.

This gives
g(pe)=ep g\left(p^{e}\right)=\frac{e}{p}
for prime pp and positive integers ee.

These facts, combined, give us the general formula for g(p1e1pkekq1f1qf)g\left(\frac{p_{1}^{e_{1}} \cdots p_{k}^{e_{k}}}{q_{1}^{f_{1}} \cdots q_{\ell}^{f_{\ell}}}\right) in terms of the prime factorizations of pp and qq :
g(p1e1pkekq1f1qf)=e1p1++ekpkf1q1fq=mp1pkq1q g\left(\frac{p_{1}^{e_{1}} \cdots p_{k}^{e_{k}}}{q_{1}^{f_{1}} \cdots q_{\ell}^{f_{\ell}}}\right)=\frac{e_{1}}{p_{1}}+\cdots+\frac{e_{k}}{p_{k}}-\frac{f_{1}}{q_{1}}-\cdots-\frac{f_{\ell}}{q_{\ell}}=\frac{m}{p_{1} \cdots p_{k} q_{1} \cdots q_{\ell}}
for some integer mm. Observe that the denominator is a product of distinct primes. Thus, if g(c)=1ng(c)=\frac{1}{n} for some cc, then either nn is the product of distinct primes, or n=1n=1.

It remains to prove that all such nn have such a solution cc.

When n=1n=1, taking c=ppc=p^{p} for some prime pp works by (3).

We now prove that if g(c)=1ng(c)=\frac{1}{n} for some cQ+c \in \mathbb{Q}^{+} and positive integer nn, then there exists dQ+d \in \mathbb{Q}^{+} such that g(d)=1npg(d)=\frac{1}{n p}, for any prime pp relatively prime to nn. This finishes the problem by induction.

Let xx and yy be integers whose values will be determined later. Observe that, by (2), g(cx)=xg(c)g\left(c^{x}\right)=x g(c). By (3), we get g(py)=ypg\left(p^{y}\right)=\frac{y}{p}. Finally, using (1) on cxc^{x} and pyp^{y} gives
g(cxpy)=xn+yp=px+nynp g\left(c^{x} p^{y}\right)=\frac{x}{n}+\frac{y}{p}=\frac{p x+n y}{n p}
It remains to choose integers xx and yy such that px+ny=1p x+n y=1. But by Bézout's identity, as the greatest common divisor of pp and nn is 1, there do exist such integers. Taking d=cxpyd=c^{x} p^{y} then gives g(d)=1npg(d)=\frac{1}{n p}, finishing the problem.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.