Cómo demostrar que [matemáticas] 4 ^ {545} + 545 ^ 4 [/ matemáticas] es un número compuesto

Answer 1

Ese es un caso especial de un problema encantador que escuché de mi amigo Raveh Gill-More, hace un buen número de años.

El problema general, no es sorprendente, es este:

Muestre que [math] 4 ^ n + n ^ 4 [/ math] es siempre compuesto, para cualquier número entero [math] n> 1 [/ math] .

Inicialmente abordé esto de la forma en que lo haría la mayoría: veamos si podemos detectar pequeños factores primos.

En primer lugar, ¿qué pasa con la paridad? Bueno, [matemática] 4 ^ n [/ matemática] es siempre par, y [matemática] n ^ 4 [/ matemática] tiene la misma paridad que [matemática] n [/ matemática]. Entonces, si [matemática] n [/ matemática] es par, el número entero es par y, por lo tanto, compuesto (es claramente mayor que [matemática] 2 [/ matemática]).

Eso es progreso: ahora solo debemos preocuparnos por los valores impares de [math] n [/ math].

A continuación, verificamos la divisibilidad entre [matemáticas] 3 [/ matemáticas]. El número [matemática] 4 ^ n [/ matemática] es siempre [matemática] 1 [/ matemática] módulo [matemática] 3 [/ matemática], mientras que usted puede verificar que [matemática] n ^ 4 [/ matemática] sea [ matemática] 0 [/ matemática] o [matemática] 1 [/ matemática] módulo [matemática] 3 [/ matemática]. Por lo tanto, su suma nunca es divisible por [matemáticas] 3 [/ matemáticas]. Ay. Todo lo contrario de lo que queríamos.

¿Qué pasa con la divisibilidad entre [matemáticas] 5 [/ matemáticas]? Por un momento, esto parece muy prometedor: [matemáticas] 4 ^ n \ equiv (-1) ^ n \ pmod {5} [/ matemáticas], y dado que solo nos interesan las [matemáticas] n [/ matemáticas] esto es simplemente [matemática] -1 [/ matemática] mod [matemática] 5 [/ matemática]. Por otro lado, [matemática] n ^ 4 [/ matemática] es casi siempre [matemática] 1 [/ matemática] mod [matemática] 5 [/ matemática], según el pequeño teorema de Fermat, así que … hemos terminado, no lo somos t nosotros?

Pues casi . Si [math] n [/ math] no es divisible por [math] 5 [/ math] entonces [math] n ^ 4 [/ math] de hecho deja un resto de [math] 1 [/ math] mod [math ] 5 [/ math], y esto cancela muy bien el [math] -1 [/ math] que obtuvimos del término [math] 4 ^ n [/ math]. Si [matemática] n> 1 [/ matemática], este factor de [matemática] 5 [/ matemática] es un factor genuino y no el número entero.

Pero, ¿qué sucede si [math] n [/ math] es divisible por [math] 5 [/ math]? Y además de eso, ¿extraño? Entonces parece que estamos jodidos. De hecho, la expresión [matemáticas] 4 ^ n + n ^ 4 [/ matemáticas] resultará ser compuesta, pero las razones no son tan triviales como tener los factores simples [matemáticas] 2 [/ matemáticas] o [matemáticas ] 5 [/ matemáticas].

---

Ahora es tentador concentrarse en los casos restantes, es decir, asumir que [matemáticas] n [/ matemáticas] tiene la forma [matemáticas] 5 (2m + 1) [/ matemáticas]. He perdido mucho tiempo en esto y no llegué a ninguna parte.

De hecho, la divisibilidad por [math] 5 [/ math] es una pista falsa. De hecho, utilizaremos el hecho de que [math] n [/ math] es extraño, pero eso es todo.

---

De lo que sí debemos darnos cuenta es que [matemáticas] 4 ^ n + n ^ 4 [/ matemáticas] es una suma de cuadrados. Esto plantea dos problemas psicológicos: primero, no parece una suma de cuadrados, y segundo, probablemente no nos molestaríamos en verificar si es una suma de cuadrados, ya que ¿cómo demonios nos ayudará a demostrar que es compuesto? La suma general de cuadrados [matemática] x ^ 2 + y ^ 2 [/ matemática] no tiene en cuenta los racionales, por lo que no hay una forma obvia de demostrar que las sumas de cuadrados son compuestas.

Aún así, esta es la observación en la que se basa la prueba, por lo que debemos suponer que tarde o temprano te habrías molestado en mirar.

[matemáticas] n ^ 4 [/ matemáticas] es una cuarta potencia, por lo que definitivamente es un cuadrado. Pero mira: también lo es [matemáticas] 4 ^ n [/ matemáticas].

[matemáticas] 4 ^ n = (2 ^ 2) ^ n = 2 ^ {2n} = (2 ^ n) ^ 2 [/ matemáticas].

Sí, es un cuadrado. ¿Pero qué hacemos con esa información? No podemos factorizar una suma de cuadrados, pero podemos escribir

[matemáticas] x ^ 2 + y ^ 2 = (x + y) ^ 2-2xy [/ matemáticas]

(Si no puede factorizarlo, escriba su factorización deseada y luego corríjala)

En nuestro caso, esto dice

[matemáticas] 4 ^ n + n ^ 4 = (2 ^ n + n ^ 2) ^ 2-2 \ cdot 2 ^ nn ^ 2 [/ matemáticas]

Y ahora viene el salto mágico final: cuando [math] n [/ math] es impar, ¡esta es una diferencia de cuadrados!

Usted ve, [matemáticas] n ^ 2 [/ matemáticas] es siempre un cuadrado, y [matemáticas] 2 \ cdot 2 ^ n = 2 ^ {n + 1} [/ matemáticas] es, afortunadamente y milagrosamente, un cuadrado precisamente cuando [matemáticas ] n [/ math] es extraño! Escribiendo [matemáticas] n + 1 = 2k [/ matemáticas], es solo el cuadrado de [matemáticas] 2 ^ k [/ matemáticas]. El producto de los cuadrados es un cuadrado, y una diferencia de cuadrados es mucho mejor que una suma de cuadrados: factoriza.

[matemáticas] A ^ 2-B ^ 2 = (AB) (A + B) [/ matemáticas]

Lo que para nosotros significa

[matemáticas] 4 ^ n + n ^ 4 = (2 ^ n + n ^ 2-2 ^ kn) (2 ^ n + n ^ 2 + 2 ^ kn) [/ matemáticas]

Esta es una factorización genuina ya que ninguno de los términos en este producto podría ser [matemática] \ pm 1 [/ matemática], lo cual debe verificar (deberá usar [matemática] n> 1 [/ matemática]). Entonces nuestros factores de expresión originales, y por lo tanto, son compuestos. QED

---

Nota: la factorización mágica también se puede observar si está familiarizado con una buena identidad atribuida a Sophie Germain:

[matemáticas] a ^ 4 + 4b ^ 4 = (a ^ 2 + 2b ^ 2-2ab) (a ^ 2 + 2b ^ 2 + 2ab) [/ matemáticas].

El método que presenté evita la necesidad de recordar esta identidad, aunque sí requiere que tome el salto de fe de escribir la suma de los cuadrados como el cuadrado de la suma menos un término de corrección, que por supuesto es solo una forma de demostrar a Sophie La identidad de Germain.

Answer 2

[matemáticas] (4 ^ 545 + 545 ^ 4) = (545 ^ 4 + 4 * (4 ^ 544)) = a ^ 4 + 4 * b ^ 4 [/ matemáticas], donde [matemáticas] a = 545 / [ matemáticas] y [matemáticas] b = 544/4 = 136 [/ matemáticas].

La famosa identidad de Sophie Germain dice que no. de la forma [matemáticas] (a ^ 4 + 4 * b ^ 4) [/ matemáticas] nunca es primo para los números naturales. a y B. Esto es porque-

[matemáticas] (a ^ 4 + 4 * b ^ 4) = (a ^ 2) ^ 2 + ((2 * b) ^ 2) ^ 2 + 2 * (a ^ 2) * ((2 ^ b) ^ 2) – 4 * a ^ 2 * b ^ 2 [/ matemáticas]

[matemáticas] = (a ^ 2 + 2 * b ^ 2) ^ 2 – (2 * a * b) ^ 2 = (a ^ 2 + 2ab + 2b ^ 2) * (a ^ 2 – 2ab + 2b ^ 2 )[/matemáticas].

Entonces, ves que el número se puede factorizar y, por lo tanto, no es primo.

Answer 3

[matemáticas] 4 ^ {545} + 545 ^ 4 [/ matemáticas]

[matemáticas] = 4.4 ^ {544} + 545 ^ 4 [/ matemáticas]

[matemáticas] = 4. (4 ^ {136}) ^ 4 + 545 ^ 4 [/ matemáticas]

Sabemos que [matemática] a ^ 4 + 4b ^ 4 [/ matemática] está compuesta por Sophie Germain Identity.

En este caso [matemáticas] a = 545 [/ matemáticas] y [matemáticas] b = (4 ^ {136}) [/ matemáticas]

Entonces, el número dado es compuesto.

Answer 4

Podemos responder esta pregunta usando la identidad de Sophie Germain.

[matemáticas] a ^ 4 + 4b ^ 4 = (a ^ 2 + 2ab + 2b ^ 2) (a ^ 2-2ab + 2b ^ 2) [/ matemáticas]

Podemos ver que [matemáticas] 545 ^ 4 [/ matemáticas] puede jugar el papel de [matemáticas] a ^ 4 [/ matemáticas] y también podemos ver que [matemáticas] 4 ^ {545} = 4 \ cdot 4 ^ { 544} = 4 \ cdot (4 ^ \ frac {544} {4}) ^ 4 = 4 \ cdot (4 ^ {136}) ^ 4 [/ math].

Esto significa que si establecemos [matemáticas] a = 545, b = 4 ^ {136} [/ matemáticas] y usamos la identidad, obtenemos una factorización de la expresión dada.

[matemáticas] 545 ^ 4 + 4 \ cdot (4 ^ {136}) ^ 4 = (545 ^ 2 + 2 \ cdot545 \ cdot4 ^ {136} +2 \ cdot (4 ^ {136}) ^ 2) (545 ^ 2-2 \ cdot545 \ cdot4 ^ {136} +2 \ cdot (4 ^ {136}) ^ 2) [/ math], y como estos números muy grandes son enteros positivos mayores que uno, [math] 4 ^ { 545} + 545 ^ 4 [/ math] debe ser compuesto.

Answer 5

Para demostrar que [matemáticas] 4 ^ (545) + 545 ^ 4 [/ matemáticas] es un número compuesto, podemos demostrar que N ^ 4 + 4 ^ N es siempre un número compuesto, mientras que N es un entero positivo mayor que 1.

[matemáticas] N ^ 4 + 4 ^ N = (N ^ 2 + 2 ^ N) ^ 2-2N ^ 2 * 2 ^ N = (N ^ 2 + 2 ^ N) ^ 2-N ^ 2 * 2 ^ ( N + 1) = (*) [/ matemáticas]

Si N es un número par [matemática] N ^ 4 + 4 ^ N [/ matemática] obviamente no es primo.

Si N es un número impar, podemos representarlo como N = 2k + 1, mientras que k es un número natural.

Ahora, [matemáticas] (*) = (N ^ 2 + 2 ^ N) ^ 2-N ^ 2 * 2 ^ (2k + 2) = [(N ^ 2 + 2 ^ N) + N * 2 ^ (k +1)] * [(N ^ 2 + 2 ^ N) -N * 2 ^ (k + 1) [/ matemática]

Y desde aquí es entendible que si N es un número entero mayor que 1, este número es compuesto; entonces 4 ^ 545 + 545 ^ 4 es un número compuesto.

Answer 6

Esta pregunta fue respondida maravillosamente por Alon Amit .

Espero que no se enoje si cito su respuesta.

Muestre que [math] 4n + n ^ 4 [/ math] siempre es compuesto, para cualquier número entero [math] n> 1 [/ math] . Inicialmente abordé esto de la manera en que la mayoría lo haría: veamos si podemos detectar pequeños factores primos. En primer lugar, ¿qué pasa con la paridad? Bueno, [math] 4n [/ math] es siempre par, y [math] n ^ 4 [/ math] tiene la misma paridad que [math] n [/ math]. Entonces, si [matemática] n [/ matemática] es par, el número entero es par y por lo tanto compuesto (es claramente mayor que [matemática] 2 [/ matemática]). Eso es progreso: ahora solo debemos preocuparnos por impar valores de [math] n [/ math]. A continuación verificamos la divisibilidad entre [math] 3 [/ math]. El número [matemática] 4n [/ matemática] es siempre [matemática] 1 [/ matemática] módulo [matemática] 3 [/ matemática], mientras que usted puede verificar que [matemática] n ^ 4 [/ matemática] sea [matemática] 0 [/ matemáticas] o [matemáticas] 1 [/ matemáticas] módulo [matemáticas] 3 [/ matemáticas]. Por lo tanto, su suma nunca es divisible por [matemáticas] 3 [/ matemáticas]. Ay. Todo lo contrario de lo que queríamos. ¿Qué pasa con la divisibilidad por [matemáticas] 5 [/ matemáticas]? Por un momento, esto parece muy prometedor: [matemática] 4n≡ (−1) n (mod5) [/ matemática], y dado que solo nos interesan las [matemáticas] n [/ matemática] esto es simplemente [matemática] −1 [ / matemáticas] mod 5 [matemáticas] 5 [/ matemáticas]. Por otro lado, [matemática] n ^ 4 [/ matemática] es casi siempre [matemática] 1 [/ matemática] mod [matemática] 5 [/ matemática], según el pequeño teorema de Fermat, así que … hemos terminado, no lo somos t nosotros? Bueno, casi . Si n [matemática] n [/ matemática] no es divisible por [matemática] 5 [/ matemática] entonces [matemática] n ^ 4 [/ matemática] de hecho deja un resto de [matemática] 1 [/ matemática] mod [ matemáticas] 5 [/ matemáticas], y esto cancela muy bien el [matemáticas] -1 [/ matemáticas] que obtuvimos del término [matemáticas] 4n [/ matemáticas]. [matemática] n> 1 [/ matemática], este factor de [matemática] 5 [/ matemática] es un factor genuino y no el número entero. Pero, ¿qué sucede si [matemática] n [/ matemática] es divisible por [matemática] 5 [/matemáticas]? Y además de eso, ¿extraño? Entonces parece que estamos jodidos. De hecho, la expresión [matemáticas] 4n + n ^ 4 [/ matemáticas] resultará ser compuesta, pero las razones no son tan triviales como tener los factores simples [matemáticas] 2 [/ matemáticas] o [matemáticas] 5 [/ matemática. Ahora es tentador centrarse en los casos restantes, es decir, asumir que n [matemática] n [/ matemática] tiene la forma [matemática] 5 (2m + 1) [/ matemática]. De hecho, la divisibilidad entre 5 [matemáticas] 5 [/ matemáticas] es una pista falsa. De hecho, utilizaremos el hecho de que [math] n [/ math] es extraño, pero eso es todo. De lo que sí debemos darnos cuenta es que [matemáticas] 4n + n ^ 4 [/ matemáticas] es una suma de cuadrados. Esto plantea dos problemas psicológicos: primero, no parece una suma de cuadrados, y segundo, probablemente no nos molestaríamos en verificar si es una suma de cuadrados, ya que ¿cómo demonios nos ayudará a demostrar que es compuesto? La suma general de los cuadrados [matemática] x ^ 2 + y ^ 2 [/ matemática] no tiene en cuenta los fundamentos, por lo que no hay una manera obvia de demostrar que las sumas de cuadrados son compuestas. Aún así, esta es la observación que depende de la prueba encendido, así que debemos suponer que tarde o temprano te habrías molestado en mirar. [matemáticas] n ^ 4 [/ matemáticas] es una cuarta potencia, por lo que definitivamente es un cuadrado. Pero mira: también lo es [matemáticas] 4n [/ matemáticas]. [Matemáticas] 4n = (2 ^ 2) ^ n = 2 ^ {2n} = (2n) ^ 2 [/ matemáticas]. Sí, es un cuadrado. ¿Pero qué hacemos con esa información? No podemos factorizar una suma de cuadrados, pero podemos escribir [matemática] x ^ 2 + y ^ 2 = (x + y) ^ 2−2xy [/ matemática] (Si no puede factorizarla, escriba su factorización de deseo y luego corregirlo!) En nuestro caso, esto dice [matemáticas] 4n + n ^ 4 = (2n + n ^ 2) ^ 2−2⋅2 ^ n * n ^ 2 [/ matemáticas] Y ahora viene el salto mágico final: cuando [matemática] n [/ matemática] es impar, ¡esta es una diferencia de cuadrados! Ya ves, [matemática] n ^ 2 [/ matemática] siempre es un cuadrado, y [matemática] 2⋅2n = 2n ¡+1 [/ math] es afortunada y milagrosamente un cuadrado precisamente cuando n [math] n [/ math] es impar! Escribiendo n + 1 = 2k [matemáticas] n + 1 = 2k [/ matemáticas], es solo el cuadrado de [matemáticas] 2k [/ matemáticas]. El producto de los cuadrados es un cuadrado, y una diferencia de cuadrados es mucho mejor que una suma de cuadrados: factoriza. [matemáticas] A ^ 2 − B ^ 2 = (A − B) (A + B) [/ matemáticas] Lo que para nosotros significa [matemáticas] 4n + n ^ 4 = (2n + n ^ 2−2kn) (2n + n ^ 2 + 2kn) [/ math]. Esta es una factorización genuina ya que ninguno de los términos en este producto podría ser [math] ± 1 [/ math], que debes verificar (deberás usar [math] n > 1 [/ matemáticas]). Entonces nuestros factores de expresión originales, y por lo tanto, son compuestos. La factorización mágica también se puede observar si está familiarizado con una buena identidad atribuida a Sophie Germain: [matemáticas] a ^ 4 + 4b ^ 4 = (a ^ 2 + 2b ^ 2−2ab) (a ^ 2 + 2b ^ 2 + 2ab) [/ matemáticas].

Answer 7

[actualización: la respuesta de D. Salgado es mejor que la mía! – reescribir esto como 4 * x ^ 4 + y ^ 4 da una forma natural de factorizarlo.]

De hecho, comprobar su factorización y descubrir que sus factores primos más pequeños son 73 y 9677 (gracias a Wolfram Alpha) me hace preguntarme si hay muchas esperanzas de encontrar un truco de factorización simple para este.

Quiero decir, ahora que * sé * los factores que puedo aplicar ingeniería inversa:

2 ^ 9 = 528 que tiene el resto de 1 cuando divides por 73

entonces 4 ^ (545) = 2 ^ (1090) = (2 ^ 9) ^ (121) * 2, lo que significa que tendrá el resto de 2 cuando dividas b entre 73

y 545 tiene el resto 34 cuando divide por 73, entonces 545 ^ 4 tiene el mismo resto que 34 ^ 4 = (34 ^ 2) ^ 2 cuando se divide entre 73, y dado que 34 ^ 2 tiene el mismo resto que -12

este debería ser el mismo resto que 144, que es -2

entonces la suma tiene el resto 0 cuando se divide por 73. así que eso prueba que es compuesto.

Pero no hubiera sabido probar 73 sin tener en cuenta primero Wolfram Alpha.

Answer 8

¿Realmente has intentado factorizar este número? Si hubiera calculado el número e intentado dividirlo entre los primeros números primos, parecería que 73 es un divisor. Puede hacer esto en 1–2 minutos escribiendo un pequeño script de Python, por ejemplo (acabo de hacer eso para encontrar 73

Si no puede encontrar divisores pequeños, siempre puede usar una prueba de número primo de Rabin Miller y ver que el número es realmente compuesto.

No tiene sentido hacer nada más elegante para un número con un par de cientos de dígitos, los algoritmos modernos de comprobación de primalidades son realmente rápidos.

Answer 9

Es divisible por 73.

El número no es tan grande como para superar la fácil manipulación de las computadoras modernas (incluso modestas) con Python. La división de prueba por números primos pequeños revela que 73 es el factor más pequeño. Unos segundos con mi programa casero de factorización Rho-Pollard también revela 9.677 y 679.369 como factores adicionales. El resto aún es compuesto, pero estaba más allá de la capacidad de mi código de factorización de juguetes para descubrir.

Anexo: accidentalmente lo dejé funcionando, y unas horas más tarde noté que también había encontrado 9.213.479.982.293 como factor. El resto aún es compuesto.

Anexo: 322,326,610,971,024,773 también es un factor.

Answer 10

Las computadoras pueden hacer esto por usted:
http://www.wolframalpha.com/inpu …
Pero encontrar un formulario general si a + b es primo especialmente cuando a y b son coprimos es difícil.

Answer 11

En respuesta a “¿Por qué [matemáticas] 4 ^ {545} + 545 ^ 4 [/ matemáticas] es un número compuesto?”:

Por la misma razón, cualquier número es compuesto (suponiendo que lo sea): tiene factores distintos de sí mismo y 1.

Answer 12

4 ^ 545 + 545 ^ 4

= (2²) ^ 545 + (545²) ²

= (2 ^ 545) ² + (545²) ²

= {2 ^ 545 + 545²} ²-2 * 2 ^ 545 * 545²

= {2 ^ 545 + 545²} ² — 2 ^ 546 * 545²

= {2 ^ 545 + 545²} ² – {(2 ^ 273) (545)} ²

= {2 ^ 545 + 545² + 545 * (2 ^ 273)} {2 ^ 545 + 545² — 545 (2 ^ 273)}

= Un producto PRIME NUMBER 【de dos enteros (que no sea 0 y 1) es primo】

Answer 13

No estoy seguro de que obtendrá una calculadora capaz de producir el resultado a la primera potencia, 4 ^ 545. si puede, entonces debería ser lo suficientemente fácil como para probar el resultado, porque 545 = 5 × 109.

Entonces, divida la suma entre 109 y el problema se resuelve si 109 es un factor.