Teoremas

Ilse Mireya Alejo Gutiérrez
A01151349 
Teorema de Euler/Fermat 
Este teorema afirma que si “x” y “y” son enteros coprimos entonces “y” entonces: 
φ​
(y)​
x​
≡ ​
​
1 mod y

 
La función ​
φ​de Euler indica la cantidad de primos que existen entre 1 y “y”, por ejemplo: 
 
 
“y” 

Coprimos con “y” entre 1 y 
“y” 

Función ​
φ​
(y) 

1 

1 

1 

2 

1 

1 

3 

1,2 

2 

4 

1,3 

2 

5 1,2,3,4 

4 

 
La función  ​
φ​
(y) es multiplicativa si “a” y “y” son coprimos: 
 
 ​
φ​
(a*y) = ​
φ​
(a) *  ​
φ​
(y)  
 
 El teorema de Euler es congruente, es decir “x” y “y” son congruentes respecto a un mod “n” 
cuando éste divide a “x ­ y”, la resolución de problemas de congruencia es una de sus 
aplicaciones. 
 
Algoritmo Extendido de Euclides 
 Es el método más rápido y práctico para calcular el máximo común divisor que además lo 
expresa como una combinación lineal, éste es una modificación del algoritmo de Euclides. Es 
decir: 
 
mcd(a,b) = as + bt 
 
Para obtener el resultado hacemos lo siguiente:  
1.Se sigue el mismo proceso que en el algoritmo tradicional de Euclides, sin embargo 
en lugar de tener q = a/b y el residuo = r, se tiene a= b1 + r. 
2. Tenemos r = a/bq 
3.Sustituimos la ecuación 2 en la 1 y se sigue hasta llegar a la primera ecuación. 

 
El algoritmo funciona de la peor manera cuando se tienen dos números de la secuencia de 
Fibonacci. 
 El pseudocódigo del algoritmo tradicional es el siguiente:  
 
function mcd(a,b) { 
if b = 0 { 
return a  
} else { 
return mcd(b, a mod b) 
} 
} 
 
Teorema TRC 
 Se utiliza debido a que el procesamiento de llaves asimétricas es muy lento en comparación 
con el de las simétricas. El teorema encuentra un número “n” que divido entre otros números 
“x,y,z” de ciertos residuos “a,b,c” y expresa lo siguiente: “n1…. nk” son enteros positivos coprimos, entonces para una secuencia de números enteros “a1...ak” existe otro entero “x” 
que puede resolver x ​
≡ ​
​
a1 (mod n1). 
 ...