2019 AIME I Problema 14

Intenta el Problema 14 del 2019 AIME I a continuación y luego compara tu respuesta con la solución preparada profesionalmente de LIVE by Po-Shen Loh. También puedes intentar el examen cronometrado completo, ver todas las soluciones del 2019 AIME I, o revisar la clave de respuestas.

Todos los problemas se usan con el permiso legal oficial de la Mathematical Association of America (MAA).

14.

Halle el menor factor primo impar de 20198+1.2019^8 + 1.

Find the least odd prime factor of 20198+1.2019^8 + 1.

Respuesta: 97
Conceptos:orden multiplicativoexponenciación modular
Nivel de dificultad: 2990
Solución:

Suponga que un primo impar pp divide a 20198+1.2019^8 + 1. Entonces 201981(modp),2019^8 \equiv -1 \pmod{p}, así que 20191612019^{16} \equiv 1 mientras que 20198≢1:2019^8 \not\equiv 1: el orden multiplicativo de 20192019 módulo pp es exactamente 16.16. Como el orden divide a p1,p - 1, necesitamos p1(mod16),p \equiv 1 \pmod{16}, y los menores primos de ese tipo son 1717 y 97.97.

Módulo 17:17: 201913,2019 \equiv 13, y 132=1691,13^2 = 169 \equiv -1, así que 20198(1)4=12019^8 \equiv (-1)^4 = 1 y 20198+120.2019^8 + 1 \equiv 2 \neq 0. Módulo 97:97: 201918,2019 \equiv -18, y elevando al cuadrado repetidamente, 2019232433,20194332=108922,20198222=4841(mod97). \begin{aligned} 2019^2 &\equiv 324 \equiv 33, \\ 2019^4 &\equiv 33^2 = 1089 \\ &\equiv 22, \\ 2019^8 &\equiv 22^2 = 484 \\ &\equiv -1 \pmod{97}. \end{aligned}

Así que 9797 divide a 20198+1,2019^8 + 1, y es el menor factor primo impar: 97.97.

Suppose an odd prime pp divides 20198+1.2019^8 + 1. Then 201981(modp),2019^8 \equiv -1 \pmod{p}, so 20191612019^{16} \equiv 1 while 20198≢1:2019^8 \not\equiv 1: the multiplicative order of 20192019 modulo pp is exactly 16.16. Since the order divides p1,p - 1, we need p1(mod16),p \equiv 1 \pmod{16}, and the smallest such primes are 1717 and 97.97.

Modulo 17:17: 201913,2019 \equiv 13, and 132=1691,13^2 = 169 \equiv -1, so 20198(1)4=12019^8 \equiv (-1)^4 = 1 and 20198+120.2019^8 + 1 \equiv 2 \neq 0. Modulo 97:97: 201918,2019 \equiv -18, and squaring repeatedly, 2019232433,20194332=108922,20198222=4841(mod97). \begin{aligned} 2019^2 &\equiv 324 \equiv 33, \\ 2019^4 &\equiv 33^2 = 1089 \\ &\equiv 22, \\ 2019^8 &\equiv 22^2 = 484 \\ &\equiv -1 \pmod{97}. \end{aligned}

So 9797 divides 20198+1,2019^8 + 1, and it is the least odd prime factor: 97.97.

← Problema 13#13
Examen completo

El Problema 14 en otros años