domingo, 26 de abril de 2015

Dos demostraciones de que existen infinitos números primos

Mientras pensaba otro problema se me han ocurrido estas dos demostraciones de que existen infinitos números primos. No es que éste sea un resultado novedoso, ¿no?, pero como son medio chulas, pues las pongo aquí.

Primera demostración. Sean r1, r2, ... , rn n números impares relativamente primos entre sí. Entonces el número

N=3·(2r1·r2·...·rn-1)

tiene al menos n+1 factores impares relativamente primos entre sí. Lo que implica que existen al menos n+1 números primos, y por inducción, existen tantos primos como se quiera.

Los n+1 factores son 3 y si = 2ni-1. Es fácil ver que 3 divide a N pero no a si; también se ve que si divide a N porque para todos a y b impares

2ab-1 = (2a-1)·(2a(b-1)-2a(b-2)+2a(b-3)-...+22a-2a+1)

Falta demostrar que los si son relativamente primos entre sí; esto es un caso particular de la siguiente proposición: dos números a y b son relativamente primos entre sí si y sólo si lo son 2a-1 y 2b-1. Como

2a+b-1 = 2a(2b-1)+2a-1

tenemos que

resto ( 2a+b-1 , 2b-1 ) = resto ( 2a-1 , 2b-1 )

y

mcd(2a+b-1, 2b-1) = mcd(2a-1, 2b-1)

y por tanto se puede aplicar el algoritmo de Euclides para calcular el máximo común divisor entre 2a-1 y 2b-1 simplemente al número de unos. Finalmente, a y b son primos relativos si y solo si el algoritmo de Euclides aplicado a a y b da 1, si y solo si el algoritmo de Euclides aplicado a 2a-1 y 2b-1 da 1, si y solo si 2a-1 y 2b-1 son primso relativos. Quizás un ejemplo lo aclare; para a=7 y b=17:

mcd(7, 17)mcd(27-1, 217-1) en binario
mcd(7 ,17) = mcd(11111112, 111111111111111112 =
mcd(7 ,3+7*2) = mcd(11111112, 1112 + 11111112 · 100000010002) =
mcd(7 ,3) = mcd(11111112, 1112) =
mcd(3 ,7) = mcd(1112, 11111112) =
mcd(3 ,1+3*2) = mcd(1112, 12 + 1112 · 100102 =
mcd(3 ,1) = mcd(1112, 12) =
1 12

Segunda demostración. Sea p un número primo, y q un divisor primo de 2p-1. Entonces 2p=1 (mod q), luego p es un múltiplo del orden de 2 en N/qN. Pero p es primo y por tanto sólo tiene dos divisores; como el orden de 2 no puede ser 1, entonces el orden de 2 tiene que ser p. Pero en N/qN todos los órdenes son menores que q, por tanto p < q. De forma que si p es primo, todos los divisores primos de 2p-1 son mayores que p, y por tanto, para cada primo p existe otro primo mayor, que se puede encontrar "simplemente" factorizando 2p-1, de aquí que existan infinitos primos.