Problema de factoraje con solución elegante.

Question

El problema es encontrar un primer factor de $N = 8^9 - 9^8.$

Tenemos $N = 91171007 = 257 \cdot 354751$ por fuerza bruta. La observación de que $257 = 2^8 + 1$ nos lleva a un cruce de caminos:

1. No es una solución elegante basándose en esta observación.

2. La persona que propuso este problema fue el trolling.

Con suerte, la última hipótesis es falsa, y uno de nosotros puede sacar la solución.

Algunas ideas para considerar:

Sophie Germain de la identidad

Generalizando el problema de la factorización $8x^8 - y^8.$

La elección de $n$ para que el factoring $2^{3n} x^{9-n} - y^8$ es manejable.

Buscar similares, la generalización obtenida arrastrando uno o más de los números primos de $8^9$ o $9^8$

Tenemos $2^8 + 1 = 4 \cdot 8^2 + 1^2;$ trate de la ingeniería inversa?

Edit: La solución debe parecer natural para quien no sabe a priori que $257$ es un factor. Sirous el enfoque de la falla esta prueba.

Answer 1

$$N=8^9-9^8$$

⇒ $$N+9^8=8^9$$

⇒ $$N+9^8+8=8^9+8=8(8^8+1)$$

$$8^8+1=(2^3)^8+1=(2^8)^3+1=(2^8+1)(2^{16}-2^8+1)$$

Por lo tanto:

$N+9^8+8= 257 m$

Podemos ver que $9^8+8=43046729=257\times 167497$

Que es N también debe ser divisible por 257. Pero si queremos seguir calculando,

$9^8+8=(8+1)^8+8=2(8^8+1)+28\times 8^6+56\times8^5+70\times8^4+56\times8^3+28\times8^2+8^2-1+8$

$8^8+1 ≡0 \mod 257$

$8^6 ≡-4\mod 257$ ⇒ $28\times 8^6 ≡-112\mod 257$

Del mismo modo podemos encontrar el resto de los términos cuando se divide por 257, la suma de los restos debe ser cero.