Maths Olympiad Prep

Library / /5 of 21

Number theory Difficulty 5.9 AIME, harder Prove it North Macedonia

Let the function f:NRf: N \rightarrow R be such that for every natural number n>1n > 1, there is a prime divisor pp of nn such that:
f(n)=f(np)f(p) f(n) = f\left(\frac{n}{p}\right) - f(p)
If f(22007)+f(32008)+f(52009)=2006f(2^{2007}) + f(3^{2008}) + f(5^{2009}) = 2006, compute f(20072)+f(20083)+f(20095)f(2007^2) + f(2008^3) + f(2009^5)
(adapted).

Solution

If n=pn = p is a prime number then
f(p)=f(pp)f(p)=f(1)f(p) f(p) = f\left(\frac{p}{p}\right) - f(p) = f(1) - f(p)
i.e.
f(p)=f(1)2(1) f(p) = \frac{f(1)}{2} \qquad (1)
If n=pqn = pq (pp and qq are prime numbers) then
f(n)=f(np)f(p)=f(q)f(p) or f(n)=f(nq)f(q)=f(p)f(q) f(n) = f\left(\frac{n}{p}\right) - f(p) = f(q) - f(p) \text{ or } f(n) = f\left(\frac{n}{q}\right) - f(q) = f(p) - f(q)
i.e.
f(n)=0 (because of (1)). f(n) = 0 \text{ (because of (1))}.
If nn is a product of three prime numbers
f(n)=f(np)f(p)=0f(p)=f(p)=f(1)2. f(n) = f\left(\frac{n}{p}\right) - f(p) = 0 - f(p) = -f(p) = -\frac{f(1)}{2}.
By induction on the number of prime divisors, it can be easily shown that if nn is a product of kk prime numbers, then
f(n)=(2k)f(1)2(2) f(n) = (2-k) \frac{f(1)}{2} \qquad (2)
Then, from f(22007)+f(32008)+f(52009)=2006f(2^{2007}) + f(3^{2008}) + f(5^{2009}) = 2006 and (2) we have
2006=f(22007)+f(32008)+f(52009)==220072f(1)+220082f(1)+220092f(1)=320062f(1) \begin{aligned} 2006 &= f(2^{2007}) + f(3^{2008}) + f(5^{2009}) = \\ &= \frac{2-2007}{2}f(1) + \frac{2-2008}{2}f(1) + \frac{2-2009}{2}f(1) = -\frac{3\cdot2006}{2}f(1) \end{aligned}
i.e.
f(1)=23(3) f(1) = -\frac{2}{3} \qquad (3)
Now from 2007=322232007 = 3^2 \cdot 223, 2008=232512008 = 2^3 \cdot 251, 2009=72412009 = 7^2 \cdot 41 and (3) we get
f(20072)+f(20083)+f(20095)=262f(1)+2122f(1)+2152f(1)==272f(1)=272(23)=9 \begin{aligned} f(2007^2) + f(2008^3) + f(2009^5) &= \frac{2-6}{2}f(1) + \frac{2-12}{2}f(1) + \frac{2-15}{2}f(1) = \\ &= -\frac{27}{2}f(1) = -\frac{27}{2} \cdot \left(-\frac{2}{3}\right) = 9 \end{aligned}

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 and solution reproduced as published; topic and difficulty added by this site.