¿Cómo fueron los factores de $\frac{521^{521}-1}{520}$ ¿encontrado?

Question

En factordb, me encontré con esta factorización :

CF  1413 (show)     (521^521-1)/520<1413> = 8794442339...49<706> · 6489962533...29<707>

¿Cómo se han encontrado estos factores?

Los factores deberían ser algebraicos o aurifeuillanos, pero no tengo ni idea de cómo. ¿Alguna idea?

Answer 1

Creo que hay una manera de generar los factores polinómicos recíprocos $\Phi_n(nx^2)$ o $\Phi_{2n}(nx^2)$ para la primera $n$ en función de la congruencia $\pmod 4$ . Los primeros son $1$ mientras que las segundas son $3$ $\pmod 4$ . Dado el campo de $n$ -raíces de la unidad, sea $r$ sea cualquier primitiva $n$ -raíz de la unidad, y $f$ es el primer factor de $\Phi_n(nx^2)$ o $\Phi_{2n}(nx^2)$ . Entonces hay un polinomio $t$ en términos de $r$ tal que el polinomio mínimo de $t$ es $f$ . Es posible (pero puede requerir una gran cantidad de cálculos), generar este polinomio mínimo para grandes primos $n$ .

Por ejemplo, tome $n=5$ y

$\Phi_5(5x^2)=(25x^4 - 25x^3 + 15x^2 - 5x + 1)(25x^4 + 25x^3 + 15x^2 + 5x + 1)$

El recíproco del primer factor es $x^4 - 5x^3 + 15x^2 - 25x + 25$ .

Si $r$ es una primitiva $5$ raíz de la unidad, entonces el polinomio mínimo de $r^3-r^2-r+1$ es $x^4 - 5x^3 + 15x^2 - 25x + 25$ . Cuando $r$ es un $10$ raíz de la unidad, el polinomio mínimo $r^3-r^2-r+1$ es $x^4 - 5x^3 + 5x^2 + 5x + 5$ . (Pensé que esto generaría el segundo factor pero supongo que no). Los cálculos se realizaron con PARI/GP:

(14:20) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(5)))
%76 = x^4 - 5*x^3 + 15*x^2 - 25*x + 25
(14:20) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(10)))
%77 = x^4 - 5*x^3 + 5*x^2 + 5*x + 5
(14:20) gp >

También traté $r$ como $n$ -raíz de la unidad para otro primo $n$ tomando el polinomio mínimo de $r^3-r^2-r+1$ y obtuvimos polinomios similares. No sé si estos polinomios tienen alguna relación con los factores aurifeuillanos de $\Phi_n(nx^2)$ o $\Phi_{2n}(nx^2)$ o podría utilizarse para resolver la factorización de $(n^n+-1)/(n+-1)$ :

(14:22) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(5)))
%78 = x^4 - 5*x^3 + 15*x^2 - 25*x + 25
(14:22) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(7)))
%79 = x^6 - 7*x^5 + 21*x^4 - 35*x^3 + 49*x^2 - 49*x + 49
(14:22) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(11)))
%80 = x^10 - 11*x^9 + 55*x^8 - 165*x^7 + 341*x^6 - 506*x^5 + 484*x^4 - 242*x^3 + 121*x^2 + 121
(14:22) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(13)))
%81 = x^12 - 13*x^11 + 78*x^10 - 286*x^9 + 715*x^8 - 1300*x^7 + 1833*x^6 - 2028*x^5 + 1521*x^4 - 507*x^3 + 169*x^2 + 169*x + 169
(14:22) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(17)))
%82 = x^16 - 17*x^15 + 136*x^14 - 680*x^13 + 2380*x^12 - 6188*x^11 + 12393*x^10 - 19516*x^9 + 24310*x^8 - 24276*x^7 + 20808*x^6 - 16473*x^5 + 10404*x^4 - 2312*x^3 + 1156*x^2 + 1156*x + 289
(14:22) gp > minpoly(Mod(x^3-x^2-x+1,polcyclo(19)))
%83 = x^18 - 19*x^17 + 171*x^16 - 969*x^15 + 3876*x^14 - 11628*x^13 + 27132*x^12 - 50426*x^11 + 75905*x^10 - 93176*x^9 + 92416*x^8 - 73644*x^7 + 50901*x^6 - 35739*x^5 + 23104*x^4 - 4332*x^3 + 3249*x^2 + 2166*x + 361

¿Alguna pista más de esto?

Answer 2

Esa fórmula, $$\frac{n^n - 1}{n - 1},$$ me resulta muy familiar. Tal vez tenga algo que ver con mi pregunta (con una recompensa que pronto expirará) sobre los pseudoprimes recíprocos.

Has pedido "alguna idea". La primera idea que suelo decir a la gente es que lo busque en la OEIS. Pero antes he realizado la consulta (n^n - 1)/(n - 1) en factordb, con un ligero temor de que el servidor pueda explotar al tener que dividir por 0 (por $n = 1$ ).

De esa consulta de factordb, obtuve suficientes números para hacer una búsqueda en OEIS y obtener un solo resultado: http://oeis.org/A023037

Para $n \geq 1$ , $a(n)$ es el número cuya base $n$ es una cadena de $n$ los. Por ejemplo, 11111 en base 5 es $a(5) = 781$ . - Melvin Peralta, 23 de mayo de 2016

Por supuesto. $a(n)$ es una base $n$ repunit. Y las repunidades son casi siempre compuestas. Si $b$ es la base de la numeración y $n = b$ entonces $$\frac{b^n - 1}{n - 1} = \sum_{i = 0}^{n - 1} b^i,$$ y... oops, lo siento, eso no fue tan fructífero como esperaba.

Bien, sabemos que esta base $n$ repunit es divisible por cualquier factor de $n^n - 1$ que son coprimos a $n - 1$ . Entonces, para 521, vemos que $520 = 2^3 \times 5 \times 13$ .

Y entonces podemos confirmar que $521^{521} \equiv 1 \pmod 5$ , $521^{521} \equiv 1 \pmod 8$ y $521^{521} \equiv 1 \pmod{13}$ ... lo siento, otro callejón sin salida.

Entonces, ¿cuándo es esta base $n$ ¿repunit prime? Claramente $n$ debe ser primordial. Aumenté mi consulta de factordb a $n = 200$ y obtuve 2, 3, 19, 31, lo que temía que me diera demasiados resultados en la OEIS. Sólo me dio cuatro, y el primero fue http://oeis.org/A088790

El siguiente primo es el 7547. Sin embargo, esto no disminuye mi asombro por el descubrimiento de los dos factores de la repunidad de base 521. Debe haber algo algebraico. Tal vez algo de lo que he dicho te ayude, o tal vez sólo te he dado un montón de pistas falsas.