domingo, 30 de octubre de 2011

Al complicar se simplifica

El uso conjunto de las operaciones de sumar y multiplicar en los temas de Teoría de Números da lugar a resultados aparentemente paradójicos. Los conceptos de divisor y múltiplo, de número primo, compuesto, abundante o deficiente se basan en la operación de multiplicar, pero nos empeñamos en sumarlos. A veces lo que logramos con esto es que al complicar una situación lo que logramos es una estructura menos compleja.

Un ejemplo claro es el de sumar números compuestos de varios divisores y que el resultado resulte ser un número primo. Así, 60=22*3*5 y 931=72*19 y sin embargo su suma 991 es un número primo. La operación de sumar ha significado una pérdida de complejidad.

Otro ejemplo: En una entrada anterior (http://hojaynumeros.blogspot.com/2011/06/un-par-de-abundantes.html) vimos que todo número par mayor que 46 es suma de dos abundantes. Esta operación también puede suponer una pérdida de complejidad. Así, 18 y 40, ambos abundantes, con su suma producen el número 58, que es deficiente.

Estudiaremos con detenimiento otro ejemplo: La función sigma (http://hojaynumeros.blogspot.com/2011/03/la-familia-de-las-sigmas-2.html) suma todos los divisores de un número. Es una operación que requiere varios pasos y bastantes operaciones. ¿Podrá producir resultados primos o semiprimos?

Podríamos intentar una búsqueda simple con hoja de cálculo: recorreríamos todos los números en un cierto rango, calculando su sigma y viendo si es prima o semiprima. El resultado sería el siguiente (para números menores que 1000):
Número N
Sigma
Tipo
Factores de N
Factores de Sigma(N)
3
4
Semiprimo
 3
 2 2
4
7
Primo
 2 2
 7
5
6
Semiprimo
 5
 2 3
8
15
Semiprimo
 2 2 2
 3 5
9
13
Primo
 3 3
 13
13
14
Semiprimo
 13
 2 7
16
31
Primo
 2 2 2 2
 31
18
39
Semiprimo
 2 3 3
 3 13
25
31
Primo
 5 5
 31
36
91
Semiprimo
 2 2 3 3
 7 13
37
38
Semiprimo
 37
 2 19
49
57
Semiprimo
 7 7
 3 19
50
93
Semiprimo
 2 5 5
 3 31
61
62
Semiprimo
 61
 2 31
64
127
Primo
 2 2 2 2 2 2
 127
73
74
Semiprimo
 73
 2 37
81
121
Semiprimo
 3 3 3 3
 11 11
100
217
Semiprimo
 2 2 5 5
 7 31
121
133
Semiprimo
 11 11
 7 19
144
403
Semiprimo
 2 2 2 2 3 3
 13 31
157
158
Semiprimo
 157
 2 79
169
183
Semiprimo
 13 13
 3 61
193
194
Semiprimo
 193
 2 97
225
403
Semiprimo
 3 3 5 5
 13 31
256
511
Semiprimo
 2 2 2 2 2 2 2 2
 7 73
277
278
Semiprimo
 277
 2 139
289
307
Primo
 17 17
 307
313
314
Semiprimo
 313
 2 157
361
381
Semiprimo
 19 19
 3 127
397
398
Semiprimo
 397
 2 199
400
961
Semiprimo
 2 2 2 2 5 5
 31 31
421
422
Semiprimo
 421
 2 211
457
458
Semiprimo
 457
 2 229
529
553
Semiprimo
 23 23
 7 79
541
542
Semiprimo
 541
 2 271
576
1651
Semiprimo
 2 2 2 2 2 2 3 3
 13 127
578
921
Semiprimo
 2 17 17
 3 307
613
614
Semiprimo
 613
 2 307
625
781
Semiprimo
 5 5 5 5
 11 71
661
662
Semiprimo
 661
 2 331
673
674
Semiprimo
 673
 2 337
729
1093
Primo
 3 3 3 3 3 3
 1093
733
734
Semiprimo
 733
 2 367
757
758
Semiprimo
 757
 2 379
841
871
Semiprimo
 29 29
 13 67
877
878
Semiprimo
 877
 2 439
961
993
Semiprimo
 31 31
 3 331
997
998
Semiprimo
 997
 2 499

Se ve que en algunos casos, como el del 576, la pérdida de complejidad es notable.

Concretemos un poco, y supongamos que N es semiprimo: N=p*q con p y q ambos primos. ¿Cuándo su sigma resultaría ser prima o semiprima?

Podemos razonar que p ha de ser igual a q: si son ambos iguales a 2, se cumple, porque 4=2*2 y sigma(4)=1+2+4=7 que es primo. En caso contrario, uno de ellos, supongamos que sea p, ha de ser impar, con lo que sigma(N)=(1+p)(1+q)=2h(1+q), con al menos tres factores, por lo que no puede ser primo ni semiprimo. En resumen: N ha de tener la forma de N=p2 con p primo. Puedes comprobarlo en la tabla anterior, pues todos los valores de N que presentan dos factores son cuadrados de primos (aunque no están todos)

Número N
Sigma
Factores de sigma
4
7
 7
9
13
 13
25
31
 31
49
57
 3 19
121
133
 7 19
169
183
 3 61
289
307
 307
361
381
 3 127
529
553
 7 79
841
871
 13 67
961
993
 3 331


En efecto, no están todos los cuadrados de primos, y además, los factores que aparecen en sigma(N) son el 3 y números primos del tipo 6m+1. ¿Por qué? Aclararemos algo a continuación. Repasaremos con ello la teoría de los restos cuadráticos:

Para este tipo de números sigma(N)=1+p+p2. Como el caso de p=2 está resuelto, podemos suponer que p>2 y por tanto impar, N será impar y sigma(N) también. Por tanto, si poseen divisores h, estos serán mayores que 2. Llamemos k a un posible divisor de sigma(N). Al ser primo impar, podremos aplicar la teoría de los restos cuadráticos (ver Parra Restos cuadráticos y Ley de reciprocidad cuadrática http://hojamat.es/parra/restocuad.pdf)

(NOTA: Por razones tipográficas usamos el signo = en las congruencias).

Si k es un divisor, se ha de cumplir que 1+p+p2=0 (mod k). Si multiplicamos por 4 quedará:

4+4p+4p2=(2p+1)2+3=0 (Mod k)   (1)

Esta congruencia puede darse en dos situaciones:

(a) Que sea k=3. Con ello se cumpliría (1) siempre que 2p+1=0 (mod 3), 2p=2 (mod 3), p=1 (mod 3) (se puede dividir entre 2 porque es primo con k), es decir que p ha de ser de la forma 3m+1. Esta es condición necesaria para que k=3, pero no suficiente.

(b) Que k no sea 3. En ese caso el número -3 ha de ser resto cuadrático respecto  a k (Ver Parra http://hojamat.es/parra/restocuad.pdf). Para que esto se cumpla, k ha de tener la forma k=6m+1. Esto completa el razonamiento: k ha de ser 3 o del tipo 6m+1, como puedes comprobar en la tabla anterior.

Una vez determinada la naturaleza de los factores (que sean el 3 u otro primo de la forma 6m+1), debemos tener en cuenta que sigma(N) puede tener un sólo factor y por tanto ser primo, o bien dos, pasando a ser semiprimo.

(A) Sigma(N) es primo

Para el caso de sigma prima puedes consultar  https://oeis.org/A023194. Es interesante que leas algunos comentarios, pero ten en cuenta que aquí solo hemos estudiado el caso en el que N era el cuadrado de un primo. Por tanto, nuestra secuencia de estos primos

2, 3, 5, 17, 41, 59, 71, 89, 101, 131, 167, 173, 293, 383, 677, 701, 743, 761, 773, 827, 839, 857, 911, 1091, 1097, 1163, 1181, 1193, 1217…

es una subsecuencia de https://oeis.org/A055638 y coincide con https://oeis.org/A053182 en la que figura un comentario de nuestro amigo Claudio Meller.

Todos sus elementos, salvo los primeros 2 y 3, son números primos de la forma 6m-1.

(A) Sigma(N) es semiprimo

En este caso los resultados son:

Primo p
Sigma(p*p)
Factores de Sigma
7
57
3 19
11
133
7 19
13
183
3 61
19
381
3 127
23
553
7 79
29
871
13 67
31
993
3 331
43
1893
3 631
47
2257
37 61
53
2863
7 409
73
5403
3 1801
83
6973
19 367
97
9507
3 3169
103
10713
3 3571
113
12883
13 991
127
16257
3 5419
157
24807
3 8269
179
32221
7 4603
197
39007
19 2053
199
39801
3 13267
223
49953
3 16651
227
51757
73 709


Como se ve, los factores primos de Sigma sólo pueden ser el 3 o los del tipo 6m+1