Maths Olympiad Prep

Library / /37 of 62

, 2020

Number theory Difficulty 5.5 AIME, harder Prove it United States

Problem:

Let N>1\mathbb{N}_{>1} denote the set of positive integers greater than 11. Let f:N>1N>1f: \mathbb{N}_{>1} \rightarrow \mathbb{N}_{>1} be a function such that f(mn)=f(m)f(n)f(m n) = f(m) f(n) for all m,nN>1m, n \in \mathbb{N}_{>1}. If f(101!)=101!f(101!) = 101!, compute the number of possible values of f(20202021)f(2020 \cdot 2021).

Solution

Solution:

For a prime pp and positive integer nn, we let vp(n)v_{p}(n) denote the largest nonnegative integer kk such that pknp^{k} \mid n. Note that ff is determined by its action on primes. Since f(101!)=101!f(101!) = 101!, by counting prime factors, ff must permute the set of prime factors of 101!101!; moreover, if pp and qq are prime factors of 101!101! and f(p)=qf(p) = q, we must have vp(101!)=vq(101!)v_{p}(101!) = v_{q}(101!). This clearly gives f(2)=2f(2) = 2, f(5)=5f(5) = 5, so it suffices to find the number of possible values for f(4347101)f(43 \cdot 47 \cdot 101). (We can factor 2021=45222=43472021 = 45^{2} - 2^{2} = 43 \cdot 47.)

There are 44 primes with vp(101!)=2v_{p}(101!) = 2 (namely, 37,41,43,4737, 41, 43, 47), so there are 66 possible values for f(4347)f(43 \cdot 47). Moreover, there are 1111 primes with vp(101!)=1v_{p}(101!) = 1 (namely, 53,59,61,67,71,73,79,83,89,97,10153, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101). Hence there are 6666 possible values altogether.

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.