Demostrar que $2019^{2018}+2020$ es divisible por al menos tres primos.

Question

Demostrar que $2019^{2018}+2020$ es divisible por al menos tres primos.

Intento utilizar la aritmética modular, pero creo que el único primo que encuentro es el 11. Esto significa que tengo que encontrar un factor más, pero no estoy muy seguro de que este enfoque sea correcto.

Se agradecería cualquier ayuda.

Answer 1

Exploración rápida con aritmética modular - ningún otro factor primo menor que $100$ . Sospecho que el siguiente después de $11$ es lo suficientemente grande como para que resulte poco práctico incluso si me tomo la molestia de escribir un programa para ello. Es hora de adoptar otro enfoque.

Edición: como el siguiente factor primo es $397$ que se encuentra más abajo - no habría sido impracticable con el programa. Implementar la exponenciación modular inteligente habría llevado algo de tiempo, pero hacer un bucle a través de cien primos no es nada una vez que tengo esa parte.

Y no, no hay nada malo en probar algo, obtener menos que el problema completo y volver con un enfoque diferente. No hay nada teóricamente malo con la aritmética modular, y sí encontramos un factor de esa manera.

¿Cuál es el nuevo enfoque? La factorización polinómica. Dividir que $2020$ como $2019+1$ . Eso nos da $n^{2018}+n+1$ evaluado en $n=2019$ . Ahora, suma y resta $n^2$ obtenemos $(n^{2018}-n^2)+(n^2+n+1)$ . Ambos términos son divisibles por $n^2+n+1$ ya que $2018\equiv 2\mod 3$ . Esto significa que $2019^2+2019+1=4078381$ es un factor del gran número que estamos viendo. T $n^{2016}-n^{2015}+n^{2013}-n^{2012}+\cdots+n^3-n^2+1$ lo que equivale a $673-672n^2\equiv 672n+1345\mod n^2+n+1$ . Evaluado en $n=2019$ - eso es $1358113$ que es relativamente primo de $4078381$ (algoritmo euclidiano - muy fácil de ejecutar). Hemos dividido $2019^{2018}+2019+1$ como producto de dos factores que son relativamente primos. Equivale a $88$ mod $121$ , por lo que hay exactamente un factor de $11$ allí; ya que ambos términos de la factorización polinómica son mucho mayores que $11$ uno de ellos es un producto de $11$ y al menos otro primo. El otro tiene al menos un factor primo, que no está en la lista de lo que ya hemos encontrado, y tenemos al menos tres factores primos distintos. Hecho.

Por cierto, tenía un colador por ahí, así que probé ese factor $4078381$ contra primos hasta $30000$ . Se divide como $397\cdot 10273$ y ambos son de primera. Así que son tres factores primos no muy grandes los que hemos encontrado, más lo que haya en el factor grande $2019^{2016}-2019^{2015}+2019^{2013}-2019^{2012}+\cdots+2019^3-2019^2+1$ .