Maths Olympiad Prep

Library / /6 of 8

Algebra Difficulty 8.6 Shortlist Prove it Netherlands

Find all functions f:Z>0Z>0f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0} such that, for all positive integers mm, nn, and aa, the following holds:
1.
f(f(m)f(n))=mn;f(f(m)f(n)) = mn;
2.
f(2024a+1)=2024a+1.f(2024a + 1) = 2024a + 1.

Solution

We first show that f(f(m))=mf(f(m)) = m for all mm.
We start by substituting n=1n = 1. This yields f(f(m)f(1))=mf(f(m)f(1)) = m. Then on the one hand ff is injective, since if f(m)=f(n)f(m) = f(n) then it immediately follows that m=f(f(m)f(1))=f(f(n)f(1))=nm = f(f(m)f(1)) = f(f(n)f(1)) = n. On the other hand, ff is surjective, since for every mm there is an aa such that f(a)=mf(a) = m, namely a=f(m)f(1)a = f(m)f(1). Hence ff is bijective. Now we substitute m=nm = n, which yields f(f(m)2)=m2=f(f(m2)f(1))f(f(m)^2) = m^2 = f(f(m^2)f(1)). Because of the injectivity of ff, it follows
f(m)2=f(m2)f(1). f(m)^2 = f(m^2)f(1).
Now choose m1m_1 for which f(m1)=1f(m_1) = 1. (It follows from our proof of the surjectivity of ff that we can choose m1=f(1)2m_1 = f(1)^2 for this, but that is not important.) If we substitute m=m1m = m_1 in the above we obtain 1=f(m12)f(1)1 = f(m_1^2)f(1). In particular, f(1)f(1) is a divisor of 11, and since it must be a natural number we conclude that f(1)=1f(1) = 1.
Substituting n=1n = 1, now yields f(f(m))=mf(f(m)) = m.
Now we can substitute f(m)f(m) and f(n)f(n) for mm and nn respectively, so that we obtain the more classical equation
f(mn)=f(f(f(m))f(f(n)))=f(m)f(n). f(mn) = f(f(f(m))f(f(n))) = f(m)f(n).
It follows that ff is determined by the values f(p)f(p) with pp prime.
Let pp be a prime number, and let mm and nn be natural numbers such that f(p)=mnf(p) = mn. Then it follows that f(m)f(n)=f(mn)=f(f(p))=pf(m)f(n) = f(mn) = f(f(p)) = p. Since f(m)f(m) and f(n)f(n) are natural numbers, it must hold that f(m)=1f(m) = 1 or f(n)=1f(n) = 1. Because of injectivity, the only mm for which f(m)=1f(m) = 1 is the number m=1m = 1. So either m=1m = 1 or n=1n = 1. We conclude that f(p)f(p) is a prime number.
Now suppose that p2024p \nmid 2024 holds. In particular, we have gcd(p,2024)=1\gcd(p, 2024) = 1, so pp has a multiplicative inverse modulo 20242024. Let bb be a natural number in the residue class of this inverse, i.e. bp1(mod2024)bp \equiv 1 \pmod{2024}. Since bpp>1bp \ge p > 1, it follows from the second equation that f(bp)=bpf(bp) = bp, but also that f(bp+2024p)=bp+2024pf(bp+2024p) = bp+2024p. However, it follows from the previous paragraph that f(bp)=f(b)f(p)f(bp) = f(b)f(p) and f((b+2024)p)=f(b+2024)f(p)f((b+2024)p) = f(b+2024)f(p). Therefore f(p)f(p) is a divisor of both bpbp and bp+2024pbp+2024p. Now we calculate
gcd(bp,bp+2024p)=gcd(bp,2024p)=gcd(b,2024)p=p, \gcd(bp, bp + 2024p) = \gcd(bp, 2024p) = \gcd(b, 2024)p = p,
since bb is the multiplicative inverse of pp modulo 20242024. Because of injectivity, we know that f(p)1f(p) \ne 1, so f(p)pf(p) \mid p implies that f(p)=pf(p) = p.
Suppose for a prime divisor pp of 20242024 that f(p)=qf(p) = q, with qpq \ne p a different prime number. Then it follows that f(q)=f(f(p))=pf(q) = f(f(p)) = p. So all prime numbers not mapped to themselves by ff form pairs (p,q)(p, q) with f(p)=qf(p) = q and f(q)=pf(q) = p. Since 2024=2311232024 = 2^3 \cdot 11 \cdot 23, we have four possible cases:
* f(p)=pf(p) = p for all primes pp. So ff is the identity,
* f(2)=11f(2) = 11, f(11)=2f(11) = 2 and f(p)=pf(p) = p for all p2,11p \nmid 2, 11,
* f(2)=23f(2) = 23, f(23)=2f(23) = 2 and f(p)=pf(p) = p for all p2,23p \nmid 2, 23,
* f(11)=23f(11) = 23, f(23)=11f(23) = 11 and f(p)=pf(p) = p for all p11,23p \nmid 11, 23.
It is easy to check that all four of these cases actually lead to a function that satisfies the given conditions. \square

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.