Cómo demostrar que un número muy grande no es primo

Question

Estoy resolviendo unos problemas matemáticos para un próximo concurso de matemáticas .

Estoy atascado con un problema corto, donde tengo que demostrar que $A$ es no primo .

$$A = 100\ 000\ 000\ 000\ 000\ 000\ 001$$

$A$ no es un número binario. Es un decimal.

He intentado reescribir así:

$$ A = 1 \times 10^{20} + 1 $$

Pero qué puedo hacer con eso . No puedo utilizar GCD ya que sería un tiempo muy largo para terminarlo y, obviamente, este no es el punto de este problema.

Answer 1

Tenemos el número $10^{20}+1$ . Siempre que tengamos algo en este tipo de forma, necesitamos encontrar un factor impar del exponente. En este caso $5 \mid 20$ , por lo que podemos utilizar $5$ como factor.

Ahora, podemos decir $10^{20}+1=(10^4)^5+1$ . ¿Cómo nos ayuda esto? Bueno, si decimos que $x=10^4$ tenemos el polinomio $x^5+1$ . Este polinomio tiene $-1$ como un cero, lo que significa $(x+1) \mid (x^5+1)$ . Sustituyendo $x=10^4$ en este enunciado, obtenemos $(10^4+1) \mid ((10^4)^5+1)=(10^{20}+1)$ . Así, $10^4+1$ es un factor de $10^{20}+1$ , por lo que el número es compuesto.

Fíjate en que el factor tenía que ser impar. De lo contrario, si tenemos un factor par $n$ entonces $x^n+1$ no habría tenido $-1$ como un cero. Se trata de una técnica muy común en los concursos de matemáticas que ya he utilizado varias veces, así que me resultará muy útil.

Answer 2

$x^5+1 = (x+1)(x^4 - x^3 + x^2 - x + 1)$ (y esto funcionará para cualquier potencia impar. reemplazar $x$ con $10^4$

$10^4+1$ divide $10^{20}+1$

Answer 3

No soy muy matemático, sólo soy un ingeniero tonto. Pero tu candidato sería rápidamente factorizado en una calculadora HP-50g, una tecnología de hace diez años. Lo sé porque una de las primeras cosas que probé fue factorizar un google-1 (un sinfín) y un google+1. Lo hizo en un par de segundos. No he probado esto en la HP-Prime, la última generación de HP, pero debería funcionar.

En realidad, me gusta mucho la respuesta de Mushtak de arriba.