Maths Olympiad Prep

Library / /272 of 462

Algebra Difficulty 6.0 AIME, harder Prove it Ireland

Let Z+={1,2,3,4,}\mathbb{Z}_+ = \{1, 2, 3, 4, \dots\} be the set of all positive integers. Determine all functions f:Z+Z+f : \mathbb{Z}_+ \to \mathbb{Z}_+ that satisfy

f(mn)+1=f(m)+f(n)f(mn) + 1 = f(m) + f(n) for all positive integers mm and nn;

f(2024)=1;f(2024) = 1;

f(n)=1f(n) = 1 for all positive n22(mod23)n \equiv 22 \pmod{23}.

Solution

Our main tool will be the observation that
f(mn)=1impliesf(m)=f(n)=1.(6) f(mn) = 1 \quad \text{implies} \quad f(m) = f(n) = 1. \qquad (6)
This is true because the functional equation f(mn)+1=f(m)+f(n)f(mn) + 1 = f(m) + f(n) then leads to 2=f(m)+f(n)2 = f(m) + f(n) which is only possible when both positive integers, f(m)f(m) and f(n)f(n), are equal to 1. In particular, the given f(2024)=1f(2024) = 1 and 2024=88232024 = 88 \cdot 23 imply f(23)=1f(23) = 1. The given functional equation then implies
f(23n)+1=f(n)+f(23)=f(n)+1, f(23n) + 1 = f(n) + f(23) = f(n) + 1,
hence f(23n)=f(n)f(23n) = f(n) for all positive integers nn. It follows by induction that f(23kn)=f(n)f(23^k n) = f(n) for all positive integers k,nk, n.
If nn is not divisible by 23, the linear congruence nx22(mod23)nx \equiv 22 \pmod{23} has a solution xx which can be chosen to be a positive integer. We then have f(nx)=1f(nx) = 1 and so f(n)=1f(n) = 1 by (6).
We can write each positive integer as m=23knm = 23^k n with some k0k \ge 0 and n>0n > 0 not divisible by 23. From above we now have f(m)=f(23kn)=f(n)=1f(m) = f(23^k n) = f(n) = 1. Hence, the only function that satisfies the given condition is the constant function f(m)=1f(m) = 1 for all mZ+m \in \mathbb{Z}_+. It is easy to see that this function indeed satisfies all the conditions.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.