2021 AIME I Problem 14

Attempt Problem 14 of the 2021 AIME I below, then check your answer against the professionally curated solution 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 problems are used with official legal permission of the Mathematical Association of America (MAA).

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.

Answer: 125
Concepts:sum of factorsmultiplicative orderleast common multiplemodular arithmetic
Difficulty rating: 3270
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++pN0p + p^2 + \cdots + p^N \equiv 0 (mod4347),\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. \begin{aligned} n &= \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) \\ &= 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47. \end{aligned}

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

← Problem 13#13
Full Exam

Problem 14 in Other Years