2021 AIME I Problem 14

Below is the professionally curated solution for Problem 14 of the 2021 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2021 AIME I solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:sum of factorsmultiplicative orderleast common multiplemodular arithmetic

Difficulty rating: 3270

14.

For any positive integer a,a, σ(a)\sigma(a) denotes the sum of the positive integer divisors of a.a. Let nn be the least positive integer such that σ(an)1\sigma(a^n) - 1 is divisible by 20212021 for all positive integers a.a. Find the sum of the prime factors in the prime factorization of n.n.

Solution:

Note 2021=4347.2021 = 43 \cdot 47. If a=piei,a = \prod p_i^{e_i}, then σ(an)=σ(piein),\sigma(a^n) = \prod \sigma(p_i^{e_i n}), so it suffices (and is necessary, taking aa prime) that σ(pN)1,\sigma(p^N) \equiv 1, i.e. p+p2++pN0(mod4347),p + p^2 + \cdots + p^N \equiv 0 \pmod{43 \cdot 47}, for every prime pp and every multiple NN of n.n.

Fix q{43,47}.q \in \{43, 47\}. If qpq \mid p the sum is 0.0. If p1(modq)p \equiv 1 \pmod q the sum is N,\equiv N, so choosing such a prime (Dirichlet) forces qn.q \mid n. Otherwise the sum is ppN1p1p \cdot \frac{p^N - 1}{p - 1} with p1p - 1 invertible, so we need pN1(modq);p^N \equiv 1 \pmod q; choosing pp to be a primitive root mod qq forces q1n.q - 1 \mid n. Conversely, if q(q1)nq(q-1) \mid n then for every multiple NN of nn and every prime p,p, the sum vanishes mod qq in all three cases. Hence the least nn is n=lcm(4342, 4746)=237234347.n = \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) = 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47.

The sum of the prime factors is 2+3+7+23+43+47=125.2 + 3 + 7 + 23 + 43 + 47 = 125.

← Problem 13Full ExamProblem 15

Problem 14 in Other Years