TEORÍA DE NÚMEROS

TEORÍA DE NÚMEROS

Teoría de números en el aprendizaje de la programación. Este

conocimiento permite comprender los aspectos que hacen al
proceso computacional tales como las capacidades de la
maquina, el tamaño máximo de números que se pueden tratar y
como trabajar con números mas
grandes.
 VARIABLES DEL LENGUAJE JAVA

 El lenguaje de programación Java tiene varios tipos de variables

enteras que se muestran en el cuadro .
 Para evaluar el tiempo de proceso de las operaciones de suma,
multiplicación y división construimos un programa que repita
muchas veces una operación, midiendo el tiempo de ejecución.
Esto permite determinar cuánto tiempo consumen los diferentes
tipos de variables y escoger la más adecuada para mejorar el
tiempo de proceso.
 El programa siguiente nos permite medir el tiempo que toma la
operación de multiplicar realizando 10.000.000 de operaciones
de multiplicación para una variable entera.
Código de ejemplo en Netbeans (java):
Respuesta al ejecutar:

Una vez procesado este programa construimos el cuadro 3.2 para

comparar el tiempo de proceso para cada tipo de variable. Se puede
observar que una operación de división demora mucho más que una
operación de multiplicación. También se observa que las operaciones de
tipo long demoran casi el doble de tiempo que las operaciones enteras
CALCULO DEL MÁXIMO COMÚN DIVISOR

Para realizar una primera

aproximación a la solución del
problema probaremos todos
los números hallando el
máximo numero que divida a
ambos.
 Mcd(int a, int b) {
OPERACION
int mcd() {
int i;
for (i=b; i>1;i--){
if (((a%i==0) && (b%i==0))) {
break;
}
}
return (i);
}
}
ANALISIS Se puede apreciar que primero a >
b cuando hallamos el primer divisor
este ya es máximo porque
comenzamos en b y vamos
restando de uno en uno. En el peor
caso cuando el máximo común
divisor es 1 el algoritmo realiza el
máximo número de operaciones.
Para calcular el O(n) requerimos
resolver
DIVISIBILIDAD

Todo entero a, es divisible por el divisor

trivial 1. Los divisores no triviales se
denominan factores. Cuando un
número tiene como ´único divisor el
número 1 y a si mismo se denomina
número primo.
TEOREMAS  T 1:Para cualquier entero a y un número positivo n
existen enteros k y r tal que 0 ≤ r < n y a = qn + r.
 T 2:Si a, b son números enteros, diferentes de cero
el mcd(a, b) es el elemento mas pequeño del
conjunto {ax + by} donde x, y ∈ Z. Demostración.
Sea q = ba/scy sea s el entero más pequeño de la
combinación lineal de a y b. Entonces
a mod s = a − qs
= a − q(ax + by)
= a(1 − qx) + b(qy)
T 3:(Teorema de Euclides) Para cualesquiera dos
enteros no negativos a, b
APLICANDO EUCLIDES
public class Euclides {
int a, b;
Euclides(int a, int b) {
if (a > b) {
this.a = a;
this.b = b;
}
else {
this.b = b;
this.a = a;}
}
int mcd() {
int r = b;
while (b > 0) {
r = a % b;
a = b;
b = r; }
return (a);
}
}
ALGORITMOS EXTENDIDO DE EUCLIDES
void eMcd (int a, int b){
int x, yAnt, r, aIni, bIni, sr,q;
aIni = a;
bIni = b;
x = 1;
yAnt = 0;
while (b != 0) {
r = a % b; q=a/b;
a = b;
b = r;
sr = x - yAnt*q;
x = yAnt;
yAnt = sr;
}
System.out.print("mcd= "+a);
System.out.print(" x= "+x);
System.out.println(" y= "+((a-x*aIni)/bIni));
}
 1.4. MÍNIMO COMÚN MÚLTIPLO
El mínimo común múltiplo (mcm) de dos números es el numero
más pequeño que es divisible por ambos números. Por ejemplo
el mínimo común múltiplo entre 9 y 6 es 18. Este número se
expresa como sigue:
mcm(a,b) = min{k,k > 0 y a|k y b|k} sin embargo es posible
probar que
mcd(a,b)mcm(a,b) = ab

mcd(9,6) es 3 y que 3x18 = 54 = 9x6

1.5. ARITMÉTICA MODULAR

 La aritmética modular es una de las aplicaciones más

importantes de la teoría de números. Está representada por la
función mod . La función módulo representa el resto de la
división. Por ejemplo a modo b significa que queremos hallar el
resto de a b que representamos como a modo b = a−b(a / b)
 1.5.1. PROPIEDADES

Suma --- (x + y) modo m = (x modo m + y modo m) modo m. Por ejemplo (8 + 7) modo 3 = 15 modo 3 = 0 y por la
propiedad de la suma (8 modo 3 + 7 modo 3) modo 3
Resta --- La resta es solo la suma con valores negativos por los que (x − y) modo m = (x modo m−y modo m) modo m.
Multiplicación --- La multiplicación xy modo m = (x modo m)(y modo m) modo m. Esto se da debido a que la
multiplicaciones simplemente una suma repetida.
División --- No existe el inverso de la multiplicación como la conocemos por ejemplo veamos dx modo m = dy modo
m se puede pensar que podemos simplificar d obteniendo x modo m = y modo m, que no se cumple en todos los
casos.
Veamos un ejemplo 6·2 modo 3 = 6·1 modo 3 = 0 si simplificamos el 6 tenemos 2 modo 3 = 1 6= 1 modo 3 = 2. Solo es
posible realizar estas simplificaciones cuando el mcd(d,m) = 1.
 El ejemplo que se presenta es Hallar el último digito del número 2100 .
Para esto no es necesario hallar el valor del exponente y luego
obtener el último dígito se puede resolver como sigue:
 23 modo 10 = 8
 26 modo 10 = (8·8) modo 10 = 4
 212 modo 10 = (4·4) modo 10 = 6
 224 modo 10 = (6·6) modo 10 = 6
 248 modo 10 = (6·6) modo 10 = 6
 296 modo 10 = (6·6) modo 10 = 6
 2100 modo 10 = 296 ·23 ·21 modo 10 = 6· 8· 2 modo 10 = 6
1.5.2. CONGRUENCIAS
Se dice que a es congruente b módulo m cuando (a − b)/m = km.
Se escribe a ≡ b mod m
Esto equivale a que a,b son múltiplos de m Algunas propiedades de las congruencias son:
Propiedad reflexiva a ≡ a
Propiedad simétrica a ≡ b ⇒ b ≡ a
Propiedad transitiva a ≡ b ≡ c ⇒ a ≡ c
Suma a ≡ b y c ≡ d ⇒ (a + c) ≡ (b + d) modo m
Multiplicación a ≡ b y c ≡ d ⇒ (ac) ≡ (bd) modo m con b,c enteros
Potencias a ≡ b ⇒ an ≡ bn modo m
Si se quiere conocer si 2n−1 es múltiplo de 3. Es decir que (2n−1) modo 3 = 0. Podemos aplicar la
propiedad de la potencia y escribir 2 ≡ −1 modo 3 de donde 2n ≡ (−1)n modo 3. Por lo tanto es
múltiplo de 3 cuando n es par.
1.5.3. INVERSO MULTIPLICATIVO

Consideremos que mcd(a,n) = 1 entonces existen enteros b y c

tales que ba + cn = 1. Esto se puede escribir como ba ≡ 1 modo n.
De aqu´ı b se denomina inverso multiplicativo de a.
1.5.4. SOLUCIÓN DE ECUACIONES
 La ecuación de congruencia de primer orden está definida
como: ax ≡ b( modo m) Estas ecuaciones tienen solución solo si
mcd(a,m)|b Para resolver este tipo de ecuación se sigue la
siguiente estrategia.
 ax−b = km ax = b + km
 buscamos un k tal que a|(b + km)
 hallamos x
Ejercicio 2.0. Resolver 6x ≡ 5(mod/3). como mcd(6,3) = 3 no es divisor de 5,no se tiene una solución.
2. Resolver 4x ≡ 10(mod/6)
4x = 10 + k6
4x = 10 + 6 con k = 1
x=4
si reemplazamos el valor de x encontrado tenemos:
4·4 ≡ 6( mod 6)
TEORÍA DE NÚMEROS
PRIMOS
Ha tenido un desarrollo muy intenso con las aplicaciones de
criptografía( técnica de escribir con procedimientos). en esta
sección le dedicamos un especial interés debido a las
complejidades que lleva este cuando se trabaja con
números grandes.
SE DEFINE LOS NPS:

Como primo el numero entero positivo que es divisible solamente

por 1 o por si mismo. Los primeros números primos son 2; 3; 5; 7; 11; 19….
Como se ve el único numero primo par es el numero 2. El numero 1 no
es parte de los números primos, sin embargo, algunos autores amplían la
dentición para incluirlo.
GENERACIÓN PRIMOS
Es posible probar la primalidad de un numero n en un tiempo proporcional
a O(√n) con el siguiente código de divisiones sucesivas

j=2;
While (j * j <= n) {
if ((i%j) == 0)
Break; //no primo
J++;
}

,876,,876
El problema que representa este método es la cantidad
de divisiones que hay que realizar. Como ya vimos el
tiempo que toma una división es mucho mayor al de la
suma. Para convertir estas divisiones en suma de números,
la forma mas fácil es a través del método denominado la
criba de Eratóstenes.
LA CRIBA DE ERATÓSTENES
Se construye a partir de los múltiplos de los números como sigue
 Se marcan los múltiplos de 2.
 Luego los de 3, 5, 7… (sucesivamente)

 Una vez completado el marcado los no marcados son los números primos.
CÓDIGO CRIBA DE ERATÓSTENES
PRIMALIDAD

 Un algoritmo de prueba de primalidad (o test verdadero de primalidad)

es un algoritmo determinista que, dado un número de entrada n,
verifica la hipótesis de un teorema cuya conclusión es que n es primo.
Una prueba de primalidad es la verificación computacional de dicho
teorema.
 PRUEBA DE PRIMALIDAD

 La prueba de primalidad es simple para números primos

pequeños. Se puede hacer por divisiones sucesivas, aun cuando,
es mejor utilizar una criba con números recalculados. Las
dificultades en el calculo de números primos radica cuando los
números a tratar son grandes.

 Otros métodos para determinar la primalidad de los mismos.

Analizamos algunos métodos sin ahondar en las demostraciones
que están ampliamente desarrolladas en la teoría de números y
el área de criptógrafa.
 EJEMPLOS DE APLICACIÓN

Los números feos son números cuyos únicos factores primos son 2, 3,
o 5. La secuencia:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 …

Muestra los primeros 11 números feos. Por convención se incluye el 1.

Esto equivale a encontrar los números que se pueden formar por
2𝑎 3𝑏 5𝑐

Ejemplo: escriba un programa que encuentre e imprima el número

feo 1500.
Si analizamos que el resultado es 859963392 significa que hemos tenido que
procesar 859; 963; 392 veces la rutina de hallar los factores. Por este motivo
es más conveniente adoptar una estrategia diferente. Construyamos los
números feos.
 Cuyo resultado sera:

Analizando este programa vemos que solo tuvimos que generar

13 ∗ 19 ∗ 30 = 7410 operaciones de potencia ordenar e imprimir
obteniendo un ahorro significativo en el tiempo de proceso.
 TEOREMA DE FERMAT
 Este teorema indica que todo número primo cumple la relación:
 𝑎𝑝−1 ≡ 1 mod p ∀a ≤ p
 Por lo que parece suficiente realizar este cálculo para determinar la primalidad.
 Desafortunadamente solo sirve para conocer si un número es compuesto dado que para
algunos números primos no se cumple. Estos números se denominan números de
CarMichael. Veamos por ejemplo el número compuesto 561:
 2561−1 mod 561 = 1
 Algunos números que no cumplen este teorema son el 561, 1105, 1729. Estos números se
denominan pseudo primos.

Para determinar si un número es compuesto podemos comenzar un algoritmo con
a = 2 y el momento que no se cumpla el teorema podemos decir que el número es
compuesto. En otros casos se indica que el número es probablemente primo.
La utilidad de este método se ve en el tratamiento de números grandes donde la
facilidad de la exponenciación modulo es mucho más eficiente que la división
PRUEBA DE MILLER – RABIN
ESTA PRUEBA PROVEE UN ALGORITMO PROBABILÍSTICO EFICIENTE
APROVECHANDO ALGUNAS CARACTERÍSTICAS DE LAS CONGRUENCIAS.

DADO UN ENTERO N IMPAR, HAGAMOS 𝑛 = 2𝑟 𝑠 + 1 CON S IMPAR.

ESCOGEMOS UN NÚMERO ENTERO ALEATORIAMENTE Y SEA ESTE 1 ≤ 𝑎 ≤
𝑛.
𝑠 2𝑗 S
SI 𝑎 ≡ 1 𝑚𝑜𝑑 (𝑛) Ó 𝑎 ≡ −1 𝑚𝑜𝑑 (𝑛) PARA ALGÚN J, QUE
ESTE EN EL RANGO 0 ≤ 𝑗 ≤ 𝑟 − 1, SE DICE QUE N PASA LA PRUEBA. UN
NÚMERO PRIMO PASA LA PRUEBA PARA TODO A.