Question

Para cualquier entero positivo $a,$ $\sigma(a)$ denota la suma de los divisores enteros positivos de $a.$ Sea $n$ el menor entero positivo tal que $\sigma(a^n) - 1$ es divisible entre $2021$ para todos los enteros positivos $a.$ Halle la suma de los factores primos en la factorización en primos de $n.$

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

Respuesta

Respuesta: 125

Conceptos:suma de factores orden multiplicativo mínimo común múltiplo aritmética modular

Nivel de dificultad: 3270

Pista pequeña:

Factorice $2021 = 43 \cdot 47.$ Como $\sigma$ es multiplicativa, basta con forzar $p + p^2 + \cdots + p^{en} \equiv 0$ módulo $43$ y $47$ para todo primo $p$ y todo entero positivo $e$

Factor $2021 = 43 \cdot 47.$ Since $\sigma$ is multiplicative, it suffices to force $p + p^2 + \cdots + p^{en} \equiv 0$ modulo $43$ and $47$ for every prime $p$ and every positive integer $e$

Pista grande:

Los primos $p \equiv 1 \pmod q$ fuerzan que $q$ divida a $n,$ mientras que los primos que son raíces primitivas módulo $q$ fuerzan que $q - 1$ divida a $n;$ tome el mínimo común múltiplo

Primes $p \equiv 1 \pmod q$ force $q$ to divide $n,$ while primes that are primitive roots mod $q$ force $q - 1$ to divide $n;$ take the least common multiple

Solución:

Observe que $2021 = 43 \cdot 47.$ Si $a = \prod p_i^{e_i},$ entonces $\sigma(a^n) = \prod \sigma(p_i^{e_i n}),$ así que basta (y es necesario, tomando $a$ primo) que $\sigma(p^N) \equiv 1,$ es decir $p + p^2 + \cdots + p^N \equiv 0$ $\pmod{43 \cdot 47},$ para todo primo $p$ y todo múltiplo $N$ de $n.$

Fije $q \in \{43, 47\}.$ Si $q$ divide a $p$ la suma es $0.$ Si $p \equiv 1 \pmod q$ la suma es $\equiv N,$ así que elegir un primo así (Dirichlet) fuerza que $q$ divida a $n.$ En caso contrario la suma es $p \cdot \frac{p^N - 1}{p - 1}$ con $p - 1$ invertible, así que necesitamos $p^N \equiv 1 \pmod q;$ elegir $p$ como raíz primitiva módulo $q$ fuerza que $q - 1$ divida a $n.$ Recíprocamente, si $q(q-1)$ divide a $n$ entonces para todo múltiplo $N$ de $n$ y todo primo $p,$ la suma se anula módulo $q$ en los tres casos. Por lo tanto el menor $n$ es $\begin{aligned} n &= \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) \\ &= 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47. \end{aligned}$

La suma de los factores primos es $2 + 3 + 7 + 23 + 43 + 47 = 125.$

Note $2021 = 43 \cdot 47.$ If $a = \prod p_i^{e_i},$ then $\sigma(a^n) = \prod \sigma(p_i^{e_i n}),$ so it suffices (and is necessary, taking $a$ prime) that $\sigma(p^N) \equiv 1,$ i.e. $p + p^2 + \cdots + p^N \equiv 0$ $\pmod{43 \cdot 47},$ for every prime $p$ and every multiple $N$ of $n.$

Fix $q \in \{43, 47\}.$ If $q$ divides $p$ the sum is $0.$ If $p \equiv 1 \pmod q$ the sum is $\equiv N,$ so choosing such a prime (Dirichlet) forces $q$ to divide $n.$ Otherwise the sum is $p \cdot \frac{p^N - 1}{p - 1}$ with $p - 1$ invertible, so we need $p^N \equiv 1 \pmod q;$ choosing $p$ to be a primitive root mod $q$ forces $q - 1$ to divide $n.$ Conversely, if $q(q-1)$ divides $n$ then for every multiple $N$ of $n$ and every prime $p,$ the sum vanishes mod $q$ in all three cases. Hence the least $n$ is $\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.$

2021 AIME I Problema 14

Respuesta: 125

Nivel de dificultad: 3270

Pista pequeña:

Pista grande:

Solución:

El Problema 14 en otros años