Maths Olympiad Prep

Library / Philippine Mathematical Olympiad /107 of 114

Philippine Mathematical Olympiad

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,b∈Q+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(p1e1⋯pkekq1f1⋯qℓfℓ)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(p1e1⋯pkekq1f1⋯qℓfℓ)=e1p1+⋯+ekpk−f1q1−⋯−fℓqℓ=mp1⋯pkq1⋯qℓ 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 c∈Q+c \in \mathbb{Q}^{+} and positive integer nn, then there exists d∈Q+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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