Maths Olympiad Prep

Library / /8 of 97

Algebra Difficulty 7.2 National olympiad, round 2 Find the answer

Find all functions f:Z+Z+f: \mathbb{Z}^+\rightarrow \mathbb{Z}^+ such that for all positive integers m,nm,n with mnm\ge n, f(mφ(n3))=f(m)φ(n3).f(m\varphi(n^3)) = f(m)\cdot \varphi(n^3).
Here φ(n)\varphi(n) denotes the number of positive integers coprime to nn and not exceeding nn.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let f:Z+Z+ f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+ be a function such that for all positive integers m m and n n with mn m \ge n , the following holds:
f(mφ(n3))=f(m)φ(n3), f(m \varphi(n^3)) = f(m) \cdot \varphi(n^3),
where φ(n) \varphi(n) denotes the Euler's totient function, which counts the number of positive integers up to n n that are coprime to n n .

We start by examining the implications of the given functional equation for specific values of n n .

1. **Case n=2 n = 2 :**
f(4m)=4f(m). f(4m) = 4f(m).

2. **Case n=22=4 n = 2^2 = 4 :**
f(32m)=32f(m). f(32m) = 32f(m).
Since f(32m)=4f(8m)=16f(2m)=32f(m) f(32m) = 4f(8m) = 16f(2m) = 32f(m) , it follows that f(2m)=2f(m) f(2m) = 2f(m) .

3. **Case n=3 n = 3 :**
f(18m)=18f(m)    f(9m)=9f(m). f(18m) = 18f(m) \implies f(9m) = 9f(m).

4. **Case n=32=9 n = 3^2 = 9 :**
f(m235)=235f(m)    f(m35)=35f(m). f(m \cdot 2 \cdot 3^5) = 2 \cdot 3^5 \cdot f(m) \implies f(m \cdot 3^5) = 3^5 \cdot f(m).
Since f(9m)=9f(m) f(9m) = 9f(m) , it follows that f(3m)=3f(m) f(3m) = 3f(m) .

By induction, we can generalize that for any prime p p and positive integer m m :
f(mpk)=pkf(m). f(mp^k) = p^k f(m).

Using this pattern, we assume f(m)=km f(m) = km for some constant kZ+ k \in \mathbb{Z}^+ . We verify this by substituting back into the original functional equation:
f(mφ(n3))=k(mφ(n3))=kmφ(n3)=f(m)φ(n3). f(m \varphi(n^3)) = k(m \varphi(n^3)) = k m \varphi(n^3) = f(m) \cdot \varphi(n^3).

Thus, the function f f that satisfies the given condition is:
f(m)=km for any positive integer constant k. f(m) = km \text{ for any positive integer constant } k.

The answer is: \boxed{f(m) = km \text{ for any positive integer constant } k.}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.