Download Hacia una nueva caracterización de los números primos. Autores

Hacia una nueva caracterización de los números primos.
Autores: Dr.Eberto Rodobaldo Morgado Morales
Dpto. de Matemáticas.
MSc. Francisco Arturo Ruiz Martínez
Dpto. de Física
Universidad Central “Marta Abreu” de Las Villas
Resumen.
En el presente trabajo se prueba un teorema de
caracterización para la primalidad de un número natural impar. Se
da una condición, necesaria y suficiente, para que un número
natural impar sea primo. Del propio teorema se deriva un algoritmo
sencillo que sirve para determinar la primalidad o no de un número
impar dado.
Abstract.
In the present work a characterization theorem for the
primality of an odd natural number is proved. A necessary and
sufficient condition for an odd natural number to be prime is given .
From the proper theorem a simple algorithm for the determination of
the primality of a given odd number is derived.
Introducción.
Un número primo es, por definición, un número natural,
diferente de 1, que solamente es divisible por 1 y por sí mismo.
El único primo que es par es el número 2, siendo todos los demás
impares, es decir, números de la forma p=2k+1, donde k es otro
natural. Por sus aplicaciones en la Criptología es importante poder
disponer de algoritmos eficientes que permitan determinar si un
número impar grande es o no primo. Demostraremos un teorema
que da, a nuestro juicio, una nueva caracterización de los números
primos, de la cual pudiera derivarse la implementación de un buen
algoritmo para determinar la primalidad.
Desarrollo:
Teorema: El número natural impar p=2k+1 es primo si, y
solamente si, él pertenece a todos los intervalos abiertos de la
forma
Ix=
x(n x + 1) xn x
,
para todo x {k+1,k+2,…2k-1}, siendo
nx
(n x 1)
nx=
p
p
, la parte entera, por defecto, de la fracción
x
p
p
x
.
Demostración:
Si p es primo, para todo x {1,2,…p-2}, la fracción
p
p
x
no es
un número entero y, por consiguiente, es un número racional
estrictamente comprendido entre dos enteros consecutivos, nx y
nx+1. Es decir,
p
nx<
p
x
< nx+1
De la desigualdad de la izquierda resulta, si nx 1,lo cual
equivale a x>
p<
1
p
= k + , que
2
2
xn x
x(n x + 1)
y, de la parte derecha,
< p. Por consiguiente,
(n x 1)
nx
p pertenece al intervalo abierto Ix, si x {k+1,k+2,…2k-1}.
Recíprocamente, si p no es primo existe algún valor de x, x>k,
para el cual el número
entera nx=
p
p
x
p
p
. De nx=
x
es un entero, luego, es igual a su parte
p
p
x
se obtiene que p =
significa que p no pertenece al intervalo abierto Ix=
xn x
y esto
(n x 1)
x(n x + 1) xn x
,
,
nx
(n x 1)
pues es igual a su mínima cota superior derecha, no incluida en Ix.
Con esto culmina la demostración.
Ejemplos: A continuación ilustraremos con dos ejemplos pequeños
las posibles aplicaciones del teorema.
Inicialmente, analicemos el número impar p=63= 2(31)+1
Los valores de x son los del conjunto
{32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48
49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61}, de los cuales
los 11 primeros determinan los intervalos abiertos:
3
2
I32 =32] ,2 [ =]48,64[,
con n32= 2
I33=
I34=
I35=
I36=
I37=
I38=
con n33= 2
con n34= 2
con n35= 2
con n36=2
con n37=2
con n38=2
=]49.5, 66[ ,
=]51,68[,
=]52.5,70[ ,
= ]54,72[ ,
=]55.5,74[ ,
=]57,76[ ,
I39=
I40=
I41=
=]58.5,78[ ,
=]60,80[ ,
=]61.5, 82[,
con n39=2
con n40=2
con n41=2
4 3
[ =]56,63[ ,
3 2
I42=42] ,
con n42=3
De estos, los primeros 10 contienen al número 63, pero el último
no, pues 63 es su cota superior mínima.Esto significa que 63 es
divisible por 63-42= 21. Luego, no es un número primo.
Hagamos ahora el mismo proceso con el número 61=2(30)+1.
Los valores de x son los del conjunto
{31,32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,} los cuales
determinan los intervalos abiertos:
3
2
I31 =31] ,2 [ =]46.5, 62[,
I32= ]48, 64[ ,
I33= ]49.5, 66[,
I34= ]51,68[ ,
I35= ]52.5,70[ ,
I36= ]54,72[ ,
I37= ]55.5,74[ ,
I38= ]57,76[ ,
I39= ]58.5,78[ ,
I40= ]60, 80[,
con n31= 2
con n32= 2
con n33= 2
con n34= 2
con n35=2
con n36=2
con n37=2
con n38=2
con n39=2
con n40=2
4 3
[ =]54.66, 61.5[ ,
3 2
I41=41] ,
I42 = ]56,63[ ,
I43= ]57.33, 64.5[ ,
I44= ]58.66, 66[,
I45= ]60,67.5[ ,
I46= 46]
con n42= 3
con n43= 3
con n44= 3
con n45= 3
5 4
, [ = ]57.5 ,61.33[ ,
4 3
I47= ]58.75, 62.66[ ,
I48= ]60, 64[ ,
I49= 49]
con n41=3
con n47=4
con n48=4
6 5
, [ = ]58.8, 61.25[ ,
5 4
I50= ]60, 62.5[
7 6
6 5
con n46=4
,
con n49=5
con n50=5
I51= 51] , [ = ]59.5, 61.2[
,
I52= ]60.76, 62.4[ ,
con n52=6
con n51=6
8 7
[ =]60.57, 61.83[,
7 6
9 8
54] , [ =]60.75, 61.71[ ,
8 7
11 10
55] , [ =]60.5, 61.11[
10 9
13 12
56] , [ =]60.66, 61.09[ ,
12 11
16 15
57] , [ = ]60.8, 61.07[ ,
15 14
21 20
58] , [ =]60.9 ,61.05[ ,
20 19
31 30
59] , [ =]60.96 ,61.03[
30 29
I53 =53] ,
con n53=7
I54=
con n54= 8
I55=
I56=
I57=
I58=
I59=
,
con n55=10
con n56=12
con n57=15
con n58=20
,
con n59=30
Se aprecia que para todos los valores admisibles de x el número 61
pertenece al intervalo abierto Ix. Esto significa que el número 61 sí
es un número primo.
Observaciones:
1) Ocurre a veces que, para diferentes valores de x, el valor nx
es el mismo. Esto significa que la función que a cada x asigna
nx no es inyectiva. De hecho, para todos los valores de x entre
1 y k el valor de nx es igual a 1 . Es, además, una función
monótona creciente, pues a medida que x aumenta los nx se
repiten o aumentan.
2) Los valores de nx no barren todos los valores del conjunto de
los números entre 1 y k, pues se producen saltos. Esto significa
que, vista como una función del conjunto de los números entre
1 y p-2, donde varía la x, en el conjunto de los números entre
1 y k, donde varía nx, no es una función sobreyectiva.
3) Cuando a x y a x+1 les corresponde el mismo valor nx =nx+1,
para obtener el intervalo Ix+1 no es necesario multiplicar,sino
solamente sumarle a los extremos del intervalo Ix los extremos
del intervalo básico ]
n x +1 n x
,
[.
nx nx 1
4) El incremento del valor de nx se realiza cuando al sumar la
fracción
n x +1
nx
con el número x
n x +1
, extremo izquierdo del
nx
intervalo Ix se obtiene un número que excede al número p, lo
cual no es admisible. En ese caso, se incrementa el valor de nx
, poniendo n x+1 = n x +1 y se obtiene el nuevo intervalo Ix+1
mediante la multiplicación del número x+1 por los extremos del
nuevo intervalo básico ]
n x +1 + 1 n x +1
,
[. Si el extremo
n x +1 n x +1 1
izquierdo vuelve a ser mayor que p se incrementa de nuevo el
valor de n x+1 , y así sucesivamente.