Olympiad Maths Prep

Library /

Algebra Difficulty 6.5 National olympiad Prove it Austria

Let f:Z>0Zf: \mathbb{Z}_{>0} \to \mathbb{Z} be a function with the following properties:
(i) f(1)=0f(1) = 0,
(ii) f(p)=1f(p) = 1 for all prime numbers pp,
(iii) f(xy)=yf(x)+xf(y)f(xy) = y f(x) + x f(y) for all x,yx, y in Z>0\mathbb{Z}_{>0}.
Determine the smallest integer n2015n \ge 2015 that satisfies f(n)=nf(n) = n.

Solutions — 2

Solution 1

We claim that
f(q1qs)=q1qs(1q1++1qs)(1) f(q_1 \cdots q_s) = q_1 \cdots q_s \left( \frac{1}{q_1} + \cdots + \frac{1}{q_s} \right) \quad (1)
holds for (not necessarily distinct) prime numbers q1,,qsq_1, \dots, q_s.
We prove the claim by induction on ss. For s=0s=0, the claim reduces to f(1)=0f(1) = 0, which is true by assumption.
If (1) holds for some ss, then
f(q1qsqs+1)=f((q1qs)qs+1)=qs+1f(q1qs)+q1qsf(qs+1)=q1qs+1(1q1++1qs)+q1qs=q1qs+1(1q1++1qs+1qs+1). \begin{aligned} f(q_1 \cdots q_s q_{s+1}) &= f((q_1 \cdots q_s)q_{s+1}) = q_{s+1} f(q_1 \cdots q_s) + q_1 \cdots q_s f(q_{s+1}) \\ &= q_1 \cdots q_{s+1} \left( \frac{1}{q_1} + \cdots + \frac{1}{q_s} \right) + q_1 \cdots q_s \\ &= q_1 \cdots q_{s+1} \left( \frac{1}{q_1} + \cdots + \frac{1}{q_s} + \frac{1}{q_{s+1}} \right). \end{aligned}

2. It is easily verified that the function given by (1) fulfills the given functional equation.

3. Let p1,,prp_1, \dots, p_r be distinct primes and α1,,αr\alpha_1, \dots, \alpha_r be positive integers. Then collecting equal primes in (1) leads to
f(p1α1prαr)=p1α1prαrj=1rαjpj. f(p_1^{\alpha_1} \cdots p_r^{\alpha_r}) = p_1^{\alpha_1} \cdots p_r^{\alpha_r} \sum_{j=1}^{r} \frac{\alpha_j}{p_j}.

4. We now determine all n2015n \ge 2015 with f(n)=nf(n) = n. We write n=p1α1prαrn = p_1^{\alpha_1} \cdots p_r^{\alpha_r}. Then
α1p1++αrpr=1.(2) \frac{\alpha_1}{p_1} + \cdots + \frac{\alpha_r}{p_r} = 1. \quad (2)
We write
α1p1++αr1pr1=ap1pr1 \frac{\alpha_1}{p_1} + \cdots + \frac{\alpha_{r-1}}{p_{r-1}} = \frac{a}{p_1 \cdots p_{r-1}}
for some non-negative integer aa. Then
ap1pr1+αrpr=1    apr+αrp1pr1=p1pr. \frac{a}{p_1 \cdots p_{r-1}} + \frac{\alpha_r}{p_r} = 1 \iff a p_r + \alpha_r p_1 \cdots p_{r-1} = p_1 \cdots p_r.
As prp_r is coprime to p1pr1p_1 \cdots p_{r-1}, we conclude that prαrp_r \mid \alpha_r. As (2) implies αrpr\alpha_r \le p_r, we conclude that r=1r=1 and αr=pr\alpha_r = p_r.
Thus f(n)=nf(n) = n holds if and only if n=prn = p^r for some prime number pp. We have
22=4<33=27<2015<55=3125, 2^2 = 4 < 3^3 = 27 < 2015 < 5^5 = 3125,
so the smallest such nn is 31253125.

Solution 2

1. We claim that
f(q1qs)=q1qs(1q1++1qs) f(q_1 \cdots q_s) = q_1 \cdots q_s \left( \frac{1}{q_1} + \cdots + \frac{1}{q_s} \right)
holds for (not necessarily distinct) prime numbers q1,,qsq_1, \dots, q_s.
We prove the claim by induction on ss. For s=0s=0, the claim reduces to f(1)=0f(1) = 0, which is true by assumption.
If (4) holds for some ss, then
f(q1qsqs+1)=f((q1qs)qs+1)=qs+1f(q1qs)+q1qsf(qs+1)=q1qs+1(1q1++1qs)+q1qs=q1qs+1(1q1++1qs+1qs+1). \begin{aligned} f(q_1 \cdots q_s q_{s+1}) &= f((q_1 \cdots q_s)q_{s+1}) = q_{s+1} f(q_1 \cdots q_s) + q_1 \cdots q_s f(q_{s+1}) \\ &= q_1 \cdots q_{s+1} \left( \frac{1}{q_1} + \cdots + \frac{1}{q_s} \right) + q_1 \cdots q_s \\ &= q_1 \cdots q_{s+1} \left( \frac{1}{q_1} + \cdots + \frac{1}{q_s} + \frac{1}{q_{s+1}} \right). \end{aligned}

2. It is easily verified that the function given by (4) fulfills the given functional equation.

3. Let p1,,prp_1, \dots, p_r be distinct primes and α1,,αr\alpha_1, \dots, \alpha_r be positive integers. Then collecting equal primes in (4) leads to
f(p1α1prαr)=p1α1prαrj=1rαjpj. f(p_1^{\alpha_1} \cdots p_r^{\alpha_r}) = p_1^{\alpha_1} \cdots p_r^{\alpha_r} \sum_{j=1}^r \frac{\alpha_j}{p_j}.

4. We now determine all n2015n \ge 2015 with f(n)=nf(n) = n. We write n=p1α1prαrn = p_1^{\alpha_1} \cdots p_r^{\alpha_r}. Then
α1p1++αrpr=1. \frac{\alpha_1}{p_1} + \cdots + \frac{\alpha_r}{p_r} = 1.
We write
α1p1++αr1pr1=ap1pr1 \frac{\alpha_1}{p_1} + \cdots + \frac{\alpha_{r-1}}{p_{r-1}} = \frac{a}{p_1 \cdots p_{r-1}}
for some non-negative integer aa. Then
ap1pr1+αrpr=1    apr+αrp1pr1=p1pr. \frac{a}{p_1 \cdots p_{r-1}} + \frac{\alpha_r}{p_r} = 1 \iff a p_r + \alpha_r p_1 \cdots p_{r-1} = p_1 \cdots p_r.
As prp_r is coprime to p1pr1p_1 \cdots p_{r-1}, we conclude that prαrp_r \mid \alpha_r. As (5) implies αrpr\alpha_r \le p_r, we conclude that r=1r=1 and αr=pr\alpha_r = p_r.
Thus f(n)=nf(n) = n holds if and only if n=pαn = p^\alpha for some prime number pp. We have
22=4<33=27<2015<55=3125, 2^2 = 4 < 3^3 = 27 < 2015 < 5^5 = 3125,
so the smallest such nn is 31253125.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.