¿Existe una buena prueba de que $123456789098765432111$ ¿es primordial?

Question

El matemático Charles Weibel se pregunta en su página de inicio la siguiente "pregunta divertida": ¿Cómo puedes demostrar que 123456789098765432111 es un número primo? (Observa el hecho

$$12345678987654321 = 111111111 \times 111111111$$

que, por supuesto, es bien conocido).

Por "prueba", supongo que se refiere a algo más humanamente esclarecedor que preguntar a un programa informático. No tengo ni idea de lo que tiene en mente. ¿Alguien tiene una idea?

Answer 1

No estoy seguro de que esto sea humanamente esclarecedor, pero creo que es humanamente comprobable. El siguiente es un certificado de Pratt, asumiendo la primalidad de los primos $\leq 100$ :

123456789098765432111, 7, 123456789098765432111-1 = 2*5*63493*322997*601991891
  63493, 2, 63493-1 = 2*2*3*11*13*37
  322997, 2, 322997-1 = 2*2*80749
    80749, 2, 80749-1 = 2*2*3*3*2243
      2243, 2, 2243-1 = 2*19*59
  601991891, 2, 601991891-1 = 2*5*191*315179
    191, 19, 191-1 = 2*5*19
      315179, 2, 315179-1 = 2*59*2671
        2671, 7, 2671-1 = 2*3*5*89

Answer 2

Más diversión con los números

El número 12345678987654321=111111111x111111111 se menciona en el PO. Y, lo creas o no, $1234567898765432111$ ¡¡¡es un número primo también!!!

Hay que creerlo. Lo siguiente $maxima$ La salida lo demostrará utilizando El certificado de primalidad de Pratt .

(%i1) m:1234567898765432111;a:29;power_mod(a,m-1,m);factor(m-1); makelist(power_mod(a,(m-1)/p,m),p,map(first,ifactors(m-1))); (%o1) 1234567898765432111 (%o2) 29 (%o3) 1 (%o4) 2*5*11*11223344534231201 (%o5) [1234567898765432110, 972745681039223016, 1223153431857342200, 1089307852892054661]

• %i1 es la línea de entrada.
• %o1 es la salida que muestra el modul $m$ , el número que comprobamos si es primo.
• %o2 es una línea de salida que muestra el número $a$ exponemos.
• %o3 es la salida de $a^{m-1} \pmod{m}$ . Debe ser $1$ si $m$ es un primo. Pero podría ser $1$ incluso si $M$ es compuesto.
• %o4 es la factorización de $m-1$ y
• %o5 son los números $a^{\frac{m-1}{p}}$ para todos los factores primos de $m-1$

Los factores $2$ , $5$ y $11$ son primos pero no es obvio que $11223344534231201$ es un número primo. Así que añadimos una prueba de que $11223344534231201$ también es un primo:

(%i1) m:11223344534231201;a:3;power_mod(a,m-1,m);factor(m-1); makelist(power_mod(a,(m-1)/p,m),p,map(first,ifactors(m-1))); (%o1) 11223344534231201 (%o2) 3 (%o3) 1 (%o4) 2^5*5^2*7*73*101*109^2*137*167 (%o5) [11223344534231200, 7251767246727978,1687389182360412, 5679768249246961, 2181793601204580, 9078160829860754, 8735272021960592, 1320423471360269]

Porque es fácil comprobar que $2,5,7,73,109,137,167$ son primos estamos acabados.

( ambos $a=29$ y $a=3$ puede ser sustituido por el número más grande pero más divertido $1111111$ en los certificados)

Pero, ¿cómo funciona este certificado de primalidad?

Lo siguiente es bien conocido:

• todas las clases de residuos $a$ que son relativamente primordiales para el módulo $m$ constituyen un grupo multiplicativo $\pmod{m}$
• Si $a^{m-1} \pmod{m}$ no es igual a $1$ entonces $m$ no puede ser un primo porque esto contradice El pequeño teorema de Fermat .
• $\text{ord}_{m-1}(a)$ es la menor potencia $e$ tal que $a^{e} \equiv 1 \pmod{m}$ es un divisor de cada $e$ . Especialmente de $\phi(m)$ .
• si $a^{m-1} \equiv 1 \pmod{m}$ entonces $\text{ord}_{m-1}(a)$ es un divisor de $m-1$ . Si es un divisor propio de $m-1$ debe ser un divisor de $\frac{m-1}{p}$ para un primer $p$ dividiendo $m$ . Entonces $a^\frac{m-1}{p} \equiv 1 \pmod{m}$ para tal $p$
• todas las clases de residuos $a,a^2,...,a^{\text{ord}(a)}$ son diferentes entre sí

Así que si $\text{ord}(a)=m-1$ y $\phi(m)=m-1$ y por lo tanto $m$ es un primo.

@ronno anotaría este certificado como

1234567898765432111,29,1234567898765432111-1=2*5*11*11223344534231201
  11223344534231201,3,11223344534231201-1=2^5*5^2*7*73*101*109^2*137*167
    167,...
    137,...
    109,...
    101,...