Matematicas_Avanzadas_zip

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

Bloque 1/Tema_1_Aritmetica_Entera/problemas1_aritmética_entera.pdf
1 Problemas tema 1: Aritmética entera 
 
Problema 1. (Expresión de números natural en bases distintas de la decimal). 
Demostrar que, dado un natural q > 1, todo número natural n puede expresarse de 
manera única en la forma 
akq
k + ak-1q
k-1 + … + a1q + a0, 
con 0 ≤ ai < q, donde k es el único natural para el que se verifica qk ≤n < qk+1. 
Problema 2. Sea 
akak-1 … a1a0; ai ∈{0, 1} 
la expresión en base 2 (binaria) de un cierto número natural. Expresar, en base 2, 
cociente y resto de la división por 2 de dicho número. 
Problema 3. Dados a y b enteros no nulos, los podemos escribir en la forma 
� = 	±∏ ��
�	
��� , 	
 = 	±∏ ��
�	
��� , αi, βi ≥ 0 
donde los pi son todos los primos que dividen a ab. Comprobar que 
�����, 
� = 	∏ ��
���	{�	,�	}	
��� 		y �����, 
� = 	∏ ��
���	{�	,�	}
��� 
Problema 4. Para cada uno de los pares de enteros siguientes, calcular el máximo 
común divisor utilizando el algoritmo de Euclides: 
(i) 34, 21; (ii) 136, 51; (iii) 481, 325; (iv) 8711, 3206; (v) 1134, 1221; 
En cada uno de los casos, resuelve la correspondiente identidad de Bézout. 
Problema 5. El algoritmo de Euclides puede hacerse ligeramente más rápido si 
permitimos restos negativos en la forma que sigue: 
���� =	��	��	 +	�� � con − "#	$ " < 	 �� � ≤ "
#	
$ " . 
Por ejemplo, si aplicamos este método para calcular el máximo común divisor de 59 y 
49, se tiene 
mcd(59, 49) = mcd(49, 10) = mcd(10,-1) = mcd(-1, 0) = 1. 
Utilizar este algoritmo, conocido como del mínimo resto, para calcular los máximos 
comunes divisores del ejercicio anterior y resolver las correspondientes identidades de 
Bézout. 
Problema 6. Demostrar las siguientes propiedades del máximo común divisor. 
i) Si a y b son pares, �����, 
� = 2	��� ()$ ,
*
$+ 
ii) Si a es par y b es impar, �����, 
� = 	��� ()$ , 
+ 
iii) Si a y b son impares, �����, 
� = 	��� (|)�*|$ , 
+ 
Problema 7. Probar las siguientes propiedades de la sucesión de Fibonacci: 
� Dos términos consecutivos de la sucesión son coprimos, es decir, 
mcd(Fn-1,Fn) = 1 para n ≥ 1. 
� El mayor natural menor que Fn+2/Fn+1 (escrito  Fn+2/ Fn+1 ) es 1. 
� El resto de la división de Fn+1 por Fn es Fn-1 
Problema 8. Demostrar que para cualquier entero k se tiene que 3k+2 y 5k+3 son 
primos entre sí. 
Problema 9. Al aplicar el algoritmo de Euclides para calcular el mcd(a, b) se obtiene 
un resto primo p. Demostrar que mcd(a, b) =1 o mcd(a, b) = p. 
Problema 10. Sean M = 35a + 57 y N = 45a + 76, con a ∈ Z. Aplicando el resultado del 
ejercicio anterior demostrar que mcd(M, N) es 19 o es 1. 
Problema 11. Descomponer de todas las formas posibles el número racional 100/273 en 
suma de dos fracciones positivas con denominadores 21 y 13. 
Problema 12. Para cada una de las ecuaciones diofánticas siguientes, estudiar si tienen 
solución y, en su caso, calcular todas las soluciones: 
25X + 36Y = 10 ; 40X + 50Y = 3 ; 
200X - 1768Y = 8 ; 213X + 1123Y = 18 ; 
2 Problemas tema 1: Aritmética entera 
 
30X + 1107Y + 3030303Z = 25 ; 10X + 11Y + 20Z = 10 ; 
3X + 7Y + 12Z + 21T = 22 ; 2200X + 1221Y - 2332Z + 101101T = 12. 
Problema 13. Resolver el sistema de ecuaciones diofánticas lineales: 
-11X	 + 	3Y	 + 	5Z = 203X	 + 	7Y	 + 	10Z = 10;		-
2X	 + 	Y	 + 	3Z = 7
8X − 	5Y − 	3Z = 11; -
2X	 + 	Y	 + 	Z − 2T = 5
3X + 2Y − 	Z + 4T = 1 
Problema 14. Supongamos que el máximo común divisor de a y b es un primo p. 
¿Cuáles son los posibles valores del máximo común divisor de a2 y b? ¿Y del máximo 
común divisor de a3 y b? Si mcd(a, b) = p, ¿cuánto vale mcd(a3,b3)? 
Problema 15. Un turista estadounidense va a pasar unos días de vacaciones en París, 
Madrid y Cracovia y desea cambiar 810 dólares en euros y en zlotys. Sabiendo que el 
euro se cotiza a 0´90 dólares y un zloty a 0´24, ¿de cuántas formas posibles puede hacer 
el cambio si necesita para su estancia en Cracovia, al menos, 3000 zlotys? 
Problema 16. Sean dados dos números naturales no nulos a y b. ¿Es posible escribir el 
número racional 
�
9:9�),*� como suma de dos racionales de denominadores a y b? En 
caso de respuesta afirmativa, esbozar un algoritmo para el cálculo de dichos racionales. 
Problema 17. Una cierta empresa fabrica tres productos A, B y C que vende a 590, 410 
y 300 euros respectivamente. Calcular cuántas unidades de cada producto se vendieron 
en un día determinado sabiendo que: 
� La recaudación por la venta de los productos fue de 32420 euros. 
� Se vendieron más unidades de A que de B. 
� El número de unidades de C vendidas fue mayor que 83. 
Problema 18. Resolver el siguiente problema: Si un gallo cuesta siete monedas, una 
gallina cinco monedas y tres pollos una moneda, ¿de cuántas formas distintas pueden 
comprarse un total de trescientas aves (gallos, gallinas y pollos) si disponemos de 
quinientas monedas? Escribir cada una de estas formas posibles. 
Problema 19. Una compañía aérea ofrece tres tipos de billetes en sus vuelos de Madrid 
a París. Los billetes de clase preferente cuestan 150 euros, los de clase turista con 
derecho a comida 110 y el resto 67. Si, en un vuelo concreto un total de 100 pasajeros 
pagaron un total de 10766 euros, ¿cuántos billetes de cada tipo se vendieron? 
Problema 20. Probar que, para cada número natural n existen siempre n números 
compuestos consecutivos. 
Problema 21. Si mn es un cuadrado perfecto y mcd(m, n) = 1, demostrar que m y n son 
también cuadrados perfectos. 
Problema 22. (Números de Fermat) Demostrar que si 2m + 1 es primo, m es una 
potencia de 2, es decir, m = 2n para algún natural n. 
Problema 23. Un primo de Mersenne es un número primo de la forma 2n-1. Demostrar 
que si 2n-1 es primo, n ha de ser primo. 
Problema 24. Dado un entero positivo n, sea ;�<� = 	∑ �>/
 la suma de todos sus 
divisores positivos. Por ejemplo, σ(27) = 1 + 3 + 9 + 27 = 40. 
Demostrar que si mcd(m, n) = 1, σ(nm) = σ(n) σ(m) y encontrar una fórmula para 
calcular σ(n) a partir de la descomposición de n en factores primos. 
Problema 25. Un número perfecto es un entero positivo que es igual a la suma de sus 
divisores distintos de él mismo (p.e., 6 es perfecto pues 6 = 1 + 2 + 3). Demostrar que 
los números perfectos pares son exactamente los de la forma 2k-1 (2k - 1), con 2k - 1 un 
primo de Mersenne. (Indicación: Para ver que un número perfecto par tiene esa forma, 
escríbelo primero en la forma 2k-1n0 con n0 impar, demostrar que n0 es divisible por (2
k 
- 
1) y comprueba que n0 tiene que ser primo estudiando σ (n0)). 
 
 
 
Bloque 1/Tema_1_Aritmetica_Entera/tema1_aritmetica_entera.pdf
Tema 1 Aritmética entera 
 
 
 
Tema 1 
Aritmética entera 
1.1 Los números enteros 
1.1.1 Relaciones de orden 
 
Una relación en un conjunto A es un subconjunto R del producto cartesiano AxA. Se 
dice que dos elementos a,b ∈ A están relacionados, aRb, si el par (a,b) pertenece al 
subconjunto R. 
Las propiedades que puede tener una relación son: 
� reflexiva: aRa para todo a de A, 
� simétrica: aRb ⇒ bRa, 
� antisimétrica: aRb y bRa ⇒ a = b, 
� transitiva: aRb y bRc ⇒ aRc. 
Definición 1.1 Una relación que verifique las propiedades reflexiva, antisimétrica y 
transitiva se denomina relación de orden. Esta relación se suele denotar por ≤. 
 
Ejemplo 1.2 
� La relación de inclusión en P(A) para un conjunto A. 
� La relación ≤ en Z, Q o R. 
� La relación de divisibilidad en el conjunto de los enteros positivos. 
 
Las relaciones de orden sirven para establecer una prelación entre elementos de un 
conjunto. 
Un conjunto con una relación de orden en la que dos elementos cualesquiera están 
siempre relacionados se dice totalmente ordenado. Si no, se dice parcialmente 
ordenado. Z con la relación de orden habitual es un conjunto totalmente ordenados, 
para cada par de elementos siempre hay uno menor que otro. Z
+ 
con la relación de 
divisibilidad es un conjunto parcialmente ordenado, para 3 y 5, ni 3 divide a 5 ni 5 
divide a 3. 
 
En un conjunto con una relación de orden, algunos elementos reciben nombres 
especiales: 
� Mínimo: a ∈A tal que a ≤ x para todo x ∈A 
� Máximo: a ∈A tal que x ≤ a para todo x ∈A 
 
Por ejemplo, el conjunto de los números enteros positivos posee mínimo para la 
relación de orden habitual, el 1, mientras que no posee máximo. En el caso de las partes 
de un conjunto A con la inclusión como relación de orden, se tiene el que conjunto vacío 
es mínimo y el propio conjunto A es máximo. 
 
Por otro lado, en relación a un subconjunto X de A se dice que a ∈ A es: 
� Cota inferior de X: si a ≤ x para todo x ∈X 
2 Tema 1 - Aritmética entera 
 
� Cota superior de X: si x ≤ a para todo x ∈X 
Cuando se tiene una relación de orden ≤, la notación a < b significa que a ≤ b y a ≠ b. 
 
1.1.2 Principio de inducción 
Consideraremos el conjunto de los números naturales como el conjunto de los enteros positivos 
junto con el 0, lo denotaremos por N. 
 
Proposición 1.3 Supongamos que para cada natural n ≥ n0 se tiene una proposición P(n) que 
puede ser cierta o falsa. Si 
i) P(n0) es cierta y 
ii) para todo n ≥ n0, P(n) cierta ⇒ P(n + 1) es cierta. 
 Entonces, P(n) es cierta para todo n ≥ n0. 
Proposición 1.4 Supongamos que para cada natural n ≥ n0 se tiene una proposición P(n) que 
puede ser cierta o falsa. Si 
i) P(n0) es cierta y 
ii) para todo n ≥ n0, P(n) cierta para todo m con n0 ≤ m ≤ n ⇒ P(n + 1) es cierta. 
Entonces, P(n) es cierta para todo n ≥ n0. 
Ejemplo 1.5 Demostrar, utilizando el principio de inducción, la fórmula que nos da la 
suma de los n primeros números naturales. 
1 � 2 ��� � � ��� � 1	2 
Esta fórmula representa una serie de afirmaciones, una por cada número natural, y 
queremos demostrar que es cierto. 
Se verifica para 1, es cierto que 1 � 
.�� 
Supongamos que se verifica para n, esto es, 1 � 2 ��� � � 
�
�
	� 
veamos que también se verifica para n + 1, 
1 � 2 ��� � � �� � 1	 � �1 � 2 ��� �	 � �� � 1	 � 
�
�
	� � �� � 1	 � �
�
	�
��	� 
Por tanto se verifica para todo n ≥ 1 � 
1.1.3 Los números enteros 
En el conjunto de los números enteros Z hay dos operaciones internas, suma y producto 
que le dan estructura de anillo conmutativo con identidad y una relación de orden, que 
verifican las siguientes propiedades: 
Z1. (Z,+) tiene estructura de grupo conmutativo: 
� La operación suma es interna: a + b ∈Z para todo a, b ∈Z 
3 Tema 1 - Aritmética entera 
 
� Asociativa: (a + b)+ c = a + (b + c) para todo a, b, c ∈Z 
� Elemento neutro (0 es el elemento neutro): a + 0 = 0 + a = a para todo a ∈Z 
� Elemento inverso (opuesto) de a ∈Z,-a: a +(- a) = (-a)+a = 0 
Por verificar estas cuatro propiedades (Z,+) tiene estructura de grupo. 
� Conmutativa: a + b = b + a para todo a, b ∈Z 
(Z,+) tiene estructura de grupo conmutativo. 
Z2. El producto es asociativo, tiene elemento identidad y es conmutativo. 
� La operación producto es interna: a. b ∈Z para todo a, b ∈Z 
� Asociativa: (a. b). c = a. (b. c) para todo a, b, c ∈Z 
� Elemento identidad (1): a. 1= 1. a = a para todo a ∈Z 
� Conmutativo: a. b = b. a para todo a, b ∈Z 
Z3. El producto es distributivo respecto de la suma. 
a. (b + c) = a. b + a. c para todo a, b, c ∈Z 
 El hecho de que el producto sea una operación interna, asociativa y distributiva 
respecto de la suma dotan a (Z, +, .)de estructura de anillo. 
Z4. a. b = 0 ⇒ a = ó b = 0. 
 Por verifica esta propiedad junto con 1 ≠ 0 se dice que (Z, +, .) es un dominio 
de integridad. 
Z5. En el conjunto de los enteros hay una relación de orden, es decir, una relación ≤ con 
las propiedades reflexiva, antisimétrica y transitiva. 
Z6. Es un orden total, es decir, a, b ∈Z, a ≤ b o b ≤ a 
El orden es compatible con las operaciones aritméticas: 
Z7. a ≤ b y c ∈Z ⇒ a + c ≤ b + c 
Z8. a ≤ b y c ≥ 0 ⇒ a. c ≤ b. c 
y el conjunto de los enteros no negativos está bien ordenado: 
Z9. Todo subconjunto no vacío de N tiene mínimo. 
Observación 1.6 Estas propiedades pueden considerarse como los axiomas que definen 
los números enteros. 
4 Tema 1 - Aritmética entera 
 
Proposición 1.7 Todo subconjunto no vacío de Z que este acotado superiormente tiene 
un máximo. 
 
1.2 Divisibilidad 
Definición 1.8 Dados dos números enteros a y b, con b ≠0, se dice que b divide a a o 
que a es múltiplo de b o que b es divisor de a, si existe otro entero q tal que a = bq. Se 
escribe b a 
Todo número entero a distinto de 1 y -1 tiene, al menos, cuatro divisores, a saber, ±1 y 
± a. A estos divisores se les conoce como divisores triviales de a. Otras propiedades de 
la divisibilidad se recogen en la siguiente proposición: 
Proposición 1.9 En las siguientes propiedades todos los números serán enteros y |a| 
denotará el valor absoluto de a: 
1) d a ⇔ -d a ⇔ d -a, 
2) d a, a≠0 y d>0 ⇒ 1 ≤ d ≤ |a|, 
3) d 1 ⇒ d = 1 o d = -1, 
4) a b y b a ⇒ b = a o b = -a, 
5) a b y b c ⇒ a c, 
6) a b y a c ⇒ a b + c, 
7) a b y c∈Z ⇒ a bc, 
8) a b y c∈Z ⇒ ac bc, 
9) a b y c d ⇒ ac bd, 
10) ac bc y c≠ 0 ⇒ a b. 
La prueba de estas propiedades requiere el uso de la Definición 1.8 y de los axiomas 
que definen los números enteros. Se deja como ejercicio. 
Definición 1.10 Se define valor absoluto de a de la forma siguiente: 
|�| � � � �� � � 0�� �� � � 0� 
Teorema 1.11 (División euclídea) Si a y b son dos enteros, b ≠ 0, existe un único par 
de enteros q y r tales que: 
a = bq + r y 0 ≤ r < |b| 
A q y a r se les conoce, respectivamente, como cociente y resto de la división euclídea 
de a por b. 
 
Demostración. Vamos a demostrar primero la existencia de cociente y resto. 
Supongamos, primero, que b > 0 y sea S = {x ∈ Z: bx ≤ a}. 
Este conjunto S es no vacío (b > 0 ⇒ b ≥ 1 ⇒ b(-|a|) ≤ - |a| ⇒ -b|a| ≤ -|a| ≤a, por lo que 
- |a| pertenece a S), y está acotado superiormente (por ejemplo, por |a|: x ≤ bx ≤ a ≤ |a|). 
5 Tema 1 - Aritmética entera 
 
Por tanto, tiene máximo. Llamaremos q al máximo de S y r = a - bq. Por construcción, 
se tiene que a = bq + r. Veamos que r verifica lo exigido. En efecto, 
� r ≥ 0 (por pertenecer q a S) 
� r < |b| = b. Si r ≥ b, se tendría b(q+1) = bq+b ≤ bq+r = a y, en consecuencia, 
q+1 pertenecería a S contradiciendo el hecho de q es el máximo de S. 
 
Si b < 0, aplicamos el caso anterior a –b. 
Para probar la unicidad supongamos que q1, r1 y q2, r2 verifican las condiciones del 
teorema, es decir, 
a = bq1 + r1 y 0 ≤ r1 < |b| 
a = bq2 + r2 y 0 ≤ r2 < |b| 
 
y que r1 ≤ r2. Restando, se tiene b(q1- q2) = r2 - r1. Por lo tanto, |b| divide a r2 - r1, pero 
también se tiene que 0 ≤ r2 - r1 < |b|. Esto sólo es posible si r2 - r1 = 0. Por lo tanto, r2=r1 
y, en consecuencia q2 = q1. � 
 
Ejemplo 1.12 Cuatro ejemplos de división euclídea: 
i. 33 = 15. 2 + 3, q = 2, r = 3 
ii. -33 = 15. (-2) - 3 = 15. (-2) -15 + 15 – 3 = 15(-3) + 12 , q = -3, r = 12 
iii. 33 = (-15).(-2) + 3, q = -2, r = 3 
iv. -33 = (-15).2 -3 = (-15).2 – 15 + 15 – 3 = (-15).3+12, q = 3, r = 12 � 
 
 
1.3 Máximo común divisor y algoritmo de Euclides 
1.3.1 Máximo común divisor 
Definición 1.13 (Máximo común divisor) Si d a y d b decimos que d es un divisor 
común (o factor común) de a y b. 
Cualquier par de enteros a y b poseen divisores comunes positivos, por ejemplo 1. Por 
otra parte, si a y b no son los dos nulos, todos sus divisores comunes son menores o 
iguales que máx(|a|, |b|). Si a y b son dos números enteros no los dos nulos, el conjunto 
de los divisores comunes positivos a a y b es no vacío y está acotado superiormente, por 
lo que podemos asegurar que de entre todos sus divisores comunes debe existir uno que 
es el mayor de ellos.
Se le denomina máximo común divisor de a y b y se denota por 
mcd(a, b), siendo el único entero positivo d que satisface 
� d a y d b, 
� Si c a y c b, c d. 
El caso a = b = 0 debe ser excluido, cualquier entero divide a 0 y es, por tanto, un 
divisor común de a y b, por lo que, en este caso, no existe un máximo común divisor. 
Esta definición puede extenderse al máximo común divisor de cualquier conjunto finito 
de enteros (no todos nulos). 
 
 
Definición 1.14 Dos números enteros se dicen coprimos o primos entre sí, si no poseen 
factores comunes no triviales, esto es, mcd(a,b) = 1. 
 
En la siguiente proposición se recogen propiedades básicas del máximo común divisor. 
 
6 Tema 1 - Aritmética entera 
 
Proposición 1.15 En las propiedades siguientes todos los números son enteros. 
1) mcd(a, b) = mcd(b, a), 
2) mcd(a, b, c) = mcd(mcd(a, b), c) = mcd(a, mcd(b, c)), 
3) mcd(a, 0) = mcd(a, a) = |a|, 
4) mcd(a, b) = mcd(-a, b) = mcd(|a|, |b|) 
5) mcd(ca, cb) = |c| mcd(a, b), 
6) mcd(a, b) = mcd(a, b + ac) 
7) ��� � ��� ��,"	 , "�� ��,"	 # = 1 
 
La definición de máximo común divisor proporciona un algoritmo para calcular 
mcd(a,b): construir la lista de divisores de a y b y tomar el mayor de los comunes. Sin 
embargo, para grandes números, este algoritmo es inaplicable. 
En la próxima sección se va a construir un algoritmo eficiente para el cálculo del 
máximo común divisor. 
 
1.3.2 Algoritmo de Euclides 
 
Proposición 1.16 Sean a y b dos números enteros y r el resto de la división euclídea de 
a por b , se verifica: 
d a y d b ⇔ d b y d r 
 
La proposición anterior quiere decir los divisores comunes de a y b son los divisores 
comunes de b y de r, por lo que mcd(a, b) = mcd(b, r). 
 
Algoritmo 1.17 (Algoritmo de Euclides) El algoritmo de Euclides es un algoritmo 
eficiente que permite simplificar el cálculo del máximo común divisor reduciendo el 
tamaño de los enteros sin alterar su máximo común divisor. Eliminando casos triviales, 
podemos suponer que a > b > 0. 
Sean r0 = a, r1 = b. Dividiendo, se tendrá que 
r0 = q1r1 + r2 con 0 ≤ r2 < r1 = b 
Si r2 = 0, entonces d a, por lo que mcd(a, b) = b y hemos terminado. 
Si r2 ≠ 0, dividimos r1 entre r2 y escribimos 
r1 = q2r2 + r3 con 0 ≤ r3 < r2 
el proceso se puede repetir si no se obtiene resto 0. 
Dado que la sucesión de restos es decreciente y finita (b = r1 > r2 > r3 >…≥ 0), en algún 
momento habremos de encontrar un resto rn+1 igual a 0. 
Los dos últimos pasos podemos escribirlos de la forma 
rn-2 = qn-1rn-1 + rn con 0 < rn < rn-1, 
y rn-1 = qnrn + rn+1 con rn+1= 0. 
� 
 
Teorema 1.18 En el proceso anterior, rn es el máximo común divisor de a y b. 
 
Demostración. 
 
mcd(a, b) = mcd(r0, r1) = mcd(r1, r2) = …= mcd(rn-2, rn-1) = mcd(rn-1, rn) = mcd(rn, 0) = 
rn. � 
 
7 Tema 1 - Aritmética entera 
 
El algoritmo anterior puede extenderse al cálculo del máximo común divisor de más de 
dos enteros. Supongamos dados t enteros positivos a1,…, at .Supongamos que i es el 
índice de la coordenada más pequeña de (a1,…, at). En este caso se verifica que 
mcd(a1,…, at) = mcd(rem(a1, ai), …,rem(ai-1, ai), ai, rem(ai +1, ai), …, rem(at, ai), donde 
rem(a, b) representa al resto de dividir a entre b. 
 
Ejemplo 1.19 Calcular el mcd de 120, 146 y 180. 
En este caso, se tiene: 
mcd(120,146, 180) = mcd(120,26,60) = mcd(16,26,8) = mcd(0, 2, 8) = mcd(0, 2, 0) = 2. 
� 
 
1.3.3. Teorema de Lamé 
 
Denotemos por E(a, b) el número de divisiones que realiza el algoritmo de Euclides si 
la entrada es (a, b). El objetivo es encontar una buena cota superior para E(a, b). 
Sea Fn el n-ésimo número de Fibonacci, recordemos que está definido por F0 = 0, F1 =1 
y Fn = Fn-1 + Fn-2 si n ≥ 2. 
 
Lema 1.20 Sean a y b enteros tales que a > b > 0 y supongamos que E(a, b) = n. 
Entonces, a ≥ Fn+2 y b ≥ Fn+1. 
 
Demostración. Utilizaremos la notación anterior y probaremos que r0 ≥ Fn+2 y r1 ≥Fn+1 
por inducción en n. 
El enunciado es cierto para n = 1. En este caso, el algoritmo de Euclides consta de una 
única división, r0 = q0r1 y puesto que r0 > r1, los menores enteros positivos que lo 
verifican son r1 = 1 = F2 y r0 = 2 = F3. 
Supongamos ahora que el enunciado es cierto para i < n; queremos probarlo para n. 
El primer paso del algoritmo de Euclides es r0 = q1r1 + r2, y sabemos que E(r1,r2) = n -1. 
Aplicando la hipótesis de inducción a E(r1, r2) = n – 1 se tendrá que r1 ≥ Fn+1 y r2 ≥ Fn. 
Por lo tanto, r0 = q1r1 + r2 ≥ r1 + r2 ≥ Fn+2. � 
 
Lema 1.21 La sucesión de Fibonacci verifica que α 
n-1 
< Fn+1, para n > 1, siendo 
$ � 
�√&� . 
 
Demostración. Por inducción sobre n: 
Veamos que es cierto para n = 2: $ � 
�√& � � 
�' � � 2 � (' 
Veamos que es cierto para n = 3: $� � '�√& � � '�' � � 3 � (* 
(Por otra parte se verifica que α 
2
 = α + 1) 
Supongamos que es cierto que se verifica para todo j con 2 < j < n, esto es α 
j-1 
< Fj+1. 
Veamos que es cierto para n: 
α 
n-1
 = α
2
 * α 
n-3
 = (α + 1)* α 
n-3
 = α 
n-2
 + α 
n-3
 < Fn + Fn-1 = Fn+1. � 
 
Teorema de Lamé 1.22 Sean a y b dos enteros positivos con a ≥ b > 0. Entonces, el 
número de divisiones realizadas en el algoritmo de Euclides para calcular E(a, b) es 
menor o igual que 5 veces el número de cifras decimales de b. 
 
8 Tema 1 - Aritmética entera 
 
Demostración. Aplicando los dos lemas anteriores te tiene: α 
n-1 
< Fn+1 ≤ b. Además 
log10α ≈ 0´208 > 0´2 = 1/5 
Por tanto (n -1) log10α ≤ log10b, esto es, 

+
& < (n -1) log10α ≤ log10b, en 
consecuencia, n-1 <5log10b. 
Por otra parte si k es el número de cifras decimales de b se verifica que b ≤ 10
k
, por 
tanto, log10b ≤ k. 
Se concluye n-1 < 5 log10b ≤ 5 k, esto es, n < 5k +1; al ser n entero se concluye que 
n ≤5k. � 
 
El teorema anterior nos da una cota para el número de divisiones realizadas por el 
algoritmo de Euclides para el cálculo de mcd(a, b). 
 
1.4 Algoritmo extendido de Euclides y resolución de 
ecuaciones diofánticas. 
 
1.4.1. Algoritmo extendido de Euclides. Identidad de Bézout. 
 
Definición 1.23 Dados enteros a y b y su máximo común divisor d = mcd(a, b), se 
denomina identidad de Bézout a la expresión de la forma 
ax + by = d x, y ∈ Z 
 
Ejemplo 1.24 El objetivo fundamental de esta sección es el demostrar que siempre 
existen tales enteros x e y y encontrar un algoritmo para su cálculo. Pero antes, veamos 
un ejemplo. 
Aplicando el algoritmo de Euclides a a = 180 y b = 146, se tiene la siguiente sucesión 
de identidades: 
180 = 1 * 146 + 34 (1.1) 
146 = 4 * 34 + 10 (1.2) 
34 = 3 * 10 + 4 (1.3) 
10 = 2 * 4 + 2 (1.4) 
4 = 2* 2 (1.5) 
Supongamos que queremos encontrar una identidad de Bézout, es decir, encontrar 
enteros x e y tales que 180 * x + 146 * y = 2 
Para ello, podemos volver hacia atrás en las identidades anteriores, es decir, de (1.5) se 
tiene 
2 = 10 - 2 *4. 
Ahora, de (1.4) podemos despejar 4 y llegar a 
2 = 7 *10 - 2 * 34. 
De nuevo, usando (1.3) llegamos a 
2 = 7 * 146 - 30 * 34 
Finalmente, usando (1.2) se tiene 
2 = -30 *180 + 37 * 146 
 
Esta forma de proceder implicará que para resolver una identidad de Bézout, tendremos 
que aplicar el algoritmo de Euclides (tomando nota de restos y cocientes) y después 
volver hacia atrás utilizando dichos restos y cocientes. En siguiente teorema veremos 
que se pueden organizar los cálculos de manera que no sea necesario. 
 
9 Tema 1 - Aritmética entera 
 
Teorema 1.25 Para todo par de enteros a y b no los dos nulos, existen enteros x e y 
tales que se verifica la identidad de Bézout: 
ax + by = mcd(a, b) 
 
Demostración. Mediante un proceso inductivo sobe k vamos a demostrar que se existen 
xk
e yk tales que: 
axk + byk = rk (0 ≤ k ≤ n), 
siendo rk los restos que se obtienen al aplicar el algoritmo de Euclides. 
Para k = 0, basta tomar x0 = 1 e y0 = 0 y si k = 1, x1 = 0 e y1 = 1. 
Ahora supongamos que hemos encontrado xk e yk para todo índice 0 ≤ k ≤ s y queremos 
calcular xs+1 e ys+1. Se tendría: 
rs+1 = rs-1 - rsqs = axs-1 + bys-1 - qs(axs + bys) = a(xs-1 - qsxs) + b(ys-1 -qsys) 
Lo que hemos visto es que las sucesiones de enteros definidas por: 
x0 = 1, x1 = 0, xk+1 = xk-1 - qkxk 
y0 = 0, y1 = 1, yk+1 = yk-1 - qkyk 
verifican 
 axk + byk = rk (0 ≤ k ≤ n). 
 
Por tanto, particularizando en k = n se obtiene que existen xn e yn tales que: 
axn+ byn = rn = mcd(a, b) 
� 
 
 
 
Ejercicio 1.26 Probar que a y b son coprimos si, y sólo si, existen enteros x e y tales que 
ax+by = 1. 
 
Construcción 1.27: Interpretación matricial del algoritmo extendido de Euclides 
Llamamos, al igual que antes, r0 =a y r1=b. 
Consideremos las matrices 
,- � �.- .-�
/- /-�
#, 0- � 1
2- 2-�
.- .-�
/- /-�
3, para k ≥ 0 
 4- � 50 11 �6-7 , para k ≥ 1 
Recordemos que los coeficientes obtenidos en el teorema anterior verifican las 
ecuaciones: 
 x0 = 1, x1 = 0, xk+1 = xk-1 - qkxk 
y0 = 0, y1 = 1, yk+1 = yk-1 - qkyk 
Expresado en forma matricial: 
,8 � �.8 .
/8 /
# � 9, 08 � 1
28 2
.8 .
/8 /
3 � 1
� :1 00 13 ,- � �.- .-�
/- /-�
# � ,-+
4- 
0- � 1
2- 2-�
.- .-�
/- /-�
3 � 0-+
4- 
(El producto de Rk-1 por Qk (es una matriz elemental) consiste en restar a la primera 
columna de Rk-1 la segunda multiplicada por qk e intercambiar las columnas de Rk-1). 
Se verifica: 
10 Tema 1 - Aritmética entera 
 
,- � �.- .-�
/- /-�
# � ,-+
4- � ,8 4
 …4- , 
0- � 1
2- 2-�
.- .-�
/- /-�
3 � 0-+
4- � 08 4
 …4- , 
 
Por tanto det(Rk) = (-1)
k
, esto es, xk yk+1- xk+1yk = ±1; lo que implica que mcd(xk,yk) =1. 
 
El algoritmo sigue hasta que en el lugar (1,2) de una de las matrices Sk aparezca un cero. 
De este modo, si en el algoritmo extendido de Euclides se realizan n divisiones, se 
tendrá 
,
 � �.
 .
�
/
 /
�
# � ,
+
4
 y 0
 � 1
2
 0.
 .
�
/
 /
�
3 � 0
+
4
 
con lo que se tiene: 
axn+ byn = rn = mcd(a, b), axn+1+ byn+1 = rn+1 = 0, 
Además mcd(xn, yn) = mcd(xn+1, yn+1) = 1. 
En particular se tendrá, si b ≠ 0, que la fracción 
<=>?@=>? es reducida e igual a � �". Dicho de 
otra manera |.
�
| � � "�� ��,"	 e |/
�
| � ��� ��,"	 
� 
 
Ejemplo 1.28 Veamos el ejemplo 1.23 con tratamiento matricial 
08 � 1180 1461 00 1 3 
Para la construcción de las natrices Qk hay que tomar nota de los cocientes que se van 
obteniendo en el algoritmo de Euclides. 
4
 � �0 11 �1#, 0
 � 084
 � 1
180 1461 00 1 3 �
0 11 �1# � 1
146 340 11 �13 
 
4� � �0 11 �4#, 0� � 0
4� � 1
146 340 11 �13�
0 11 �4# � 1
34 101 �41�1 5 3 
 
4' � �0 11 �3#, 0' � 0�4' � 1
34 101 �41�1 5 3 �
0 11 �3# � 1
10 4�4 135 �163 
 
4* � �0 11 �2#, 0* � 0'4* � 1
10 4�4 135 �163 �
0 11 �2# � 1
4 213 �30�16 37 3 
 
4& � �0 11 �2#, 0& � 0'4& � 1
4 213 �30�16 37 3�
0 11 �2# � 1
2 0�30 7337 �903 
Hemos llegado a una matriz S cuyo término (1,2) es 0, r5= 2, x5= -30, y5 = 37, con lo 
que se tiene (-30)*180 + 37*146 = 2. � 
 
11 Tema 1 - Aritmética entera 
 
Teorema 1.29 Si abc y mcd(a, b) = 1, entonces ac. En particular, si p es primo y pab, 
entonces pa o pb. 
 
Demostración. Gracias a la identidad de Bézout sabemos que existen enteros x e y tales 
que ax + by = 1. Multiplicando por c se tiene c = cax + cby, con lo que a divide a los dos 
sumandos a la derecha y, por lo tanto, divide a c. 
� 
 
1.4.2. Ecuaciones diofánticas. 
 
Definición 1.30 Se llaman ecuaciones diofánticas a aquéllas de las que nos interesan 
las soluciones enteras. 
 
Vamos a estudiar las ecuaciones diofánticas lineales en dos variables: 
aX + bY = c a, b, c ∈ Z 
Puesto que el caso a = b = 0 no tiene ningún interés, supondremos que (a, b) ≠ (0; 0). 
 
Proposición 1.31 Dados enteros a, b, c la ecuación diofántica 
aX + bY = c 
tiene solución si, y sólo si, mcd(a, b) divide a c. En caso de que tenga solución tiene 
infinitas, dadas por 
��.
 � G "�� ��,"	 , /
 � G ��� ��,"	# , G H IJ, 
donde (x1,y1) es una solución particular cualquiera. 
 
Demostración. 
Utilizando el Algoritmo de Euclides extendido, sabemos encontrar una solución si c = 
mcd(a, b). Del mismo modo, es obvio encontrar una solución si mcd(a, b) divide a c. 
Por tanto, la ecuación diofántica tiene solución si mcd(a, b) divide a c. 
Supongamos que tiene solución la ecuación diofántica aX + bY = c, existirán x e y tales 
que ax + by = c. Por tanto, todo factor común de a y de b también lo será de c. En 
particular, el máximo común divisor de a y de b dividirá a c. 
Por tanto la ecuación diofántica aX + bY = c, a, b, c ∈ Z tiene solución si, y sólo si, 
mcd(a, b) divide a c. 
 
Sabemos cómo encontrar una solución: aplicamos el algoritmo extendido de Euclides a 
a y b, obteniendo x0 e y0 tales que ax + by = mcd(a, b). Es claro que � ��� ��,"	 .8, ��� ��,"	/8# es solución de la ecuación diofántica dada. 
 
Para encontrar más soluciones estudiaremos la ecuación diofántica aX + bY = 0 (la 
homogénea asociada) 
Una solución obvia es de la homogénea es: 
� "�� ��,"	 , � ��� ��,"	#, 
pero también lo son todas las de la forma 
�G "�� ��,"	 , �G ��� ��,"	#, con t ∈Z. 
Así pues, si (x1, y1) es solución cualesquiera de la ecuación diofántica dada, el conjunto 
K5.
 � G :�����, :	 , /
 � G ������, :	7 , con t ∈IP 
12 Tema 1 - Aritmética entera 
 
es un conjunto de infinitas soluciones. 
 
¿Hay más?. Para verlo, sea (x, y) una solución cualesquiera de la ecuación diofántica 
dada. Por tanto, 
ax1 + by1= c 
ax + by= c 
Restando se tiene a(x-x1) + b(y-y1) = 0 y, dividiendo por mcd(a, b) , �
�� ��,"	 �. � x
	 � "�� ��,"	 �/ � /
	 � 0. 
Ahora, supongamos que b ≠ 0 ( si b = 0 y a ≠0, haríamos con a el mismo argumento que 
sigue). Como 
��� 5 ������, :	 , :�����, :	7 � 1 
y 
"
�� ��,"	 divide a 
�
�� ��,"	 �. � x
	, se tiene que "�� ��,"	 divide a (x – x1), es decir, . � .
 � G "�� ��,"	, para algún t ∈ Z 
Sustituyendo se tiene /
 � / � G ��� ��,"	 
Por tanto el conjunto de soluciones de la ecuación diofántica dada siendo (x1, y1) es 
solución cualesquiera es 
K5.
 � G :�����, :	 , /
 � G ������, :	7 , con t ∈IP 
 
� 
Ejemplo 1.32 Estudiar si existe o no solución para la ecuación diofántica 
15x + 40y = 1000 
En caso afirmativo, encontrar todo el conjunto de soluciones. 
 
mcd(15, 40) = 5 y 5 es divisor de 1000, por tanto la ecuación diofántica dada tiene 
solución. 
En primer lugar procedemos a encontrar una solución de 15x + 40y = 5, 
5 = 15*3 + 40*(-1), una solución sería (3,-1). A partir de ella se encuentra una solución 
de la dada. 
1000 = 5. 200, por tanto (3.200,-1.200) = (600,-200) es una solución de la dada. 
 
El conjunto de soluciones de la dada sería: 
 x = 600 + t. 40/5 = 600 + 8t, y = -200 - t 15/5 = -200 -3t, con t ∈ Z 
� 
Ejemplo 1.33 Estudiar si existe o no solución para la ecuación diofántica 
15x + 40y = 21 
En caso afirmativo, encontrar todo el conjunto de soluciones. 
mcd(15, 40) = 5 y 5 no es divisor de 21, por tanto la ecuación diofántica dada no tiene 
solución. � 
 
Ejemplo 1.34 Dividir 1000 en dos sumandos positivos uno múltiplo de 15 y otro 
múltiplo de 40. 
 
Se trata de encontrar valores de x, y ∈ Z tales que 15x + 40y = 1000. 
En el ejemplo anterior se han encontrado el conjunto de soluciones. Ahora hay que 
imponer que esas soluciones sean positivas. 
13 Tema 1 - Aritmética entera 
 
x = 600 + 8t > 0 ⇔ 8t > -600 ⇔ t > -600/8 = -75 
y = -200 - 3t > 0 ⇔ -200 > 3t ⇔ -200/3 > t ⇔ -67 ≥ t 
Por tanto, interesan las soluciones -67 ≥ t > -75. Basta dar a t uno de esos valores, por 
ejemplo, t = -74, x = 600 + 8*(-74)
= 8, y = -200 – 3*(-74) = 22 
Vemos que 1000 = 15*8 + 40*22. � 
 
 
1.5 Números primos. Teorema fundamental de la aritmética. 
 
1.5.1. Teorema fundamental de la aritmética 
Definición 1.35 Un entero p > 1 se dice primo si sus únicos divisores positivos son los 
triviales, es decir, 1 y p. 
Los primeros primos son: 
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 
Teorema 1.36 Todo número entero mayor que 1 es producto de primos. 
 
Demostración. Por inducción sobre n 
Para n = 2 es cierto 
Supongamos que es cierto para 2 ≤ i < k, todo número entero i con 2 ≤ i < k se puede 
poner como producto de primos. 
Veamos que es cierto para k. 
Si k es primo, ya es producto de primos. 
Si k no es primo, es compuesto, por tanto existen dos enteros positivos a y b mayores 
que 1 tales que k = ab. Por tanto a, b < ab = k. 
Aplicando la hipótesis de inducción a los números a y b, ambos se pueden poner como 
producto de primos. Por tanto k = ab es producto de primos. 
Se concluye que todos número entero mayor que 1 es producto de primos. � 
En particular, todo entero no nulo es producto de uno de los números naturales ±1 y de 
números primos. Veremos más adelante que esta expresión es única. 
Teorema 1.37 Existen infinitos números primos. 
 
Demostración. Esta demostración se hará por reducción al absurdo. 
Supongamos que hay un número finito, digamos n, de números primos a los que 
denotaremos por p1, p2,…, pn. Consideremos el número 
N = p1. p2.…. pn + 1 
14 Tema 1 - Aritmética entera 
 
Por el teorema anterior sabemos que N es producto de primos. Sea p un factor primo de 
N. Este primo es uno de los p1, p2,…, pn, digamos p = pi. Entonces pi divide a N y p1 
p2,… pn. Por tanto pi divide a N - p1 p2… pn que es igual a 1, con lo que hemos llegado a 
contradicción. 
La hipótesis formulada no es cierta. Por tanto, no hay un número finito de primos. Esto 
es, existen infinitos números primos. � 
 
 
Proposición 1.38 Si p es primo y pa1 a2 …an, entonces p divide a algún ai. 
 
Demostración. Como consecuencia del teorema 1.26 se verifica que, en particular, si p 
es primo y pab, entonces pa o pb. 
Por un argumento inductivo se puede probar si p es primo y pa1 a2 …an, entonces p 
divide a algún ai. � 
 
 
Teorema 1.39 (Teorema fundamental de la aritmética) Todo entero positivo puede 
expresarse como producto de potencias no triviales de números primos � � R
S?R�ST …R-SU 
y, salvo, reordenación de los factores, esta factorización es única. 
 
Demostración La existencia se sigue de un teorema anterior y, por lo tanto, sólo queda 
probar la unicidad. 
Sea S el conjunto de enteros positivos que admiten dos factorizaciones distintas y, 
supongamos, por reducción al absurdo, que este conjunto es no vacío. Por la buena 
ordenación de N, sabemos que, en ese caso, el conjunto S admite mínimo, digamos n. Se 
tendrán dos factorizaciones distintas de n: � � R
S?R�ST …R-SU � � 6
V?6�VT …6WVX 
 
Es claro que p1 divide a 6
V?6�VT…6WVX y, por lo tanto, a alguno de los 6YVZ. Aún más, se 
tendrá que p1 divide a alguno de los qi, que implica que es igual a él. Reordenando 
podemos suponer p1 = q1. En consecuencia se tendría 
 �R
 � R
S?+
R�ST …R-SU � 6
V?+
6�VT…6WVX 
Puesto que las factorizaciones de n consideradas eran distintas, tenemos dos factores 
distintos del entero positivo 
[? � �, lo que contradice el hecho de que n sea el mínimo 
de S. � 
 
Teorema 1.40 Si n es un número entero positivo compuesto, entonces tiene un divisor 
primo menor que √� 
 
Demostración. Si n es un número compuesto, tiene un factor positivo a. Por tanto, n = 
ab, con 1 < a, b. Se verifica que � \ √� o : \ √�. 
En caso contrario, � ] √� y : ] √�, y se tendría � � �: ] √�√� � �, habríamos 
llegado a una contradicción. � 
 
15 Tema 1 - Aritmética entera 
 
1.5.2 Mínimo común múltiplo 
 
Definición 1.41 Si a y b son dos enteros, un múltiplo común de a y b es un entero c tal 
que ac, y b c. 
Si a y b son ambos no nulos, existen múltiplos comunes positivos, por ejemplo |ab|. Al 
ser N un conjunto bien ordenado existe un menor múltiplo común positivo. Se le 
denomina mínimo común múltiplo, se denota por mcm(a, b), siendo el único entero 
positivo m que satisface: 
� a m y b m, 
� Si a c y b c, m c. 
 
Teorema 1.42 Sean a y b dos enteros. Se tiene 
|ab| = mcd(a,b). mcm(a,b) 
 
Demostración. Se trata de probar que � � |�"|�� ��,"	 es el mínimo común múltiplo de a y 
b. 
� � |�"|�� ��,"	 � |�| |"|�� ��,"	 , por tanto a m � � |�"|�� ��,"	 � |:| |�|�� ��,"	, por tanto b m 
Por otro lado, supongamos que c es un entero que es múltiplo de a y b, es decir, c = au 
para algún entero u y c = bv para algún entero v. 
Se tiene, entonces que ������, :	 ^ � :�����, :	 _ 
y como 
�
�� ��,"	 y 
"
�� ��,"	 son primos entre sí, aplicando el teorema 1.26 se obtiene que �
�� ��,"	 divide v, es decir, _ � ` ��� ��,"	 para algún k. 
Finalmente, se tendrá, � � :_ � ` �"�� ��,"	 para algún k. 
Por tanto, c es múltiplo de 
|�"|
�� ��,"	. 
Como consecuencia 
|�"|
�� ��,"	 es el mínimo común múltiplo de a y b. � 
 
Bloque 1/Tema_2_Aritmetica_Modular/problemas2_aritmetica_modular.pdf
1 Tema 2 Aritmética modular 
 
Problema 1. Demostrar las siguientes propiedades de las congruencias: 
a) a ≡ b (mod n) y dn ⇒ a ≡ b (mod d) 
b) ka ≡ kb (mod n) y k ≠ 0 ⇒ � ≡ � (��� �	
�(�,
)) 
c) a ≡ b (mod n) y a ≡ b (mod m) ⇒ a ≡ b (mod mcm(m,n)) 
Problema 2. Encontrar todos los números naturales n que verifiquen 
97 ≡ 287 (mod n). 
Problema 3. Demostrar que si p es primo y a2 ≡ b2 (mod p), se tiene que p(a + b) o 
p(a - b). ¿Puede decirse lo mismo si p no es primo? 
Problema 4. Demostrar que si n ≡ 3 (mod 4), entonces n no puede ser suma de 
cuadrados de dos enteros. 
Problema 5. Estudiar la existencia de solución de las ecuaciones que siguen y, en el 
caso de que tengan solución, calcular todas las soluciones enteras. 
(a) 24X ≡ 7 (mod 40) (b) 13X ≡7 (mod 10) (c) 525X ≡237 (mod 423) 
(d) 1215X ≡560 (mod 2755) (e) 2X ≡ 1 (mod 3) (f) 234X ≡ 3 (mod 244) 
(g) 20X ≡30 (mod 4) (h) 20X ≡ 4 (mod 30) (i) 3X≡2 (mod 7) 
Problema 6. Encontrar las soluciones enteras de los sistemas siguientes: 
a) �3� + 6� ≡ 2(��� 8)5� + 3� ≡ 0(��� 8)� b) �11� + 3� ≡ 5(��� 7)3� + 7� ≡ 3(��� 7)� 
Problema 7. Estudiar la existencia de soluciones y, en su caso, resolver: 
 (a) �� ≡ 3 (��� 4)� ≡ 5 (��� 7)� ≡ 6 (��� 9)� (b) �
� ≡ 1 (��� 7)� ≡ 0 (��� 5)� ≡ 1 (��� 3)� 
(c) �� ≡ 5 (��� 8)� ≡ 1 (��� 20)� ≡ 3 (��� 7) � (d) �
� ≡ 2 (��� 5)� ≡ 4 (��� 10)� ≡ 38 (��� 47)� 
(e) 
 !"
!# � ≡ 1 (��� 3)� ≡ 0 (��� 5)� ≡ 4 (��� 7)� ≡ 5 (��� 27)� ≡ 6 (��� 1233)
� (f) $ � ≡ 2 (��� 6)� ≡ 4 (��� 8)� ≡ 2 (��� 14)� ≡ 14 (��� 15)� 
Problema 8. Estudia para qué números enteros positivos a el sistema de congruencias 
�� ≡ 1 (��� 7)� ≡ 2 (��� 54)� ≡ � (��� 189)� 
Tiene solución y resuélvelo para el menor de todos ellos. 
Problema 9. Encontrar un múltiplo de 11 que deja resto 1 dividido por 2, 3, 5 y 7. 
Problema 10. Sea n número entero positivo: 
a) Demostrar por inducción que 1 + 2 + 3 + … + n = ((()*)+ 
b) Si n es impar, demostrar que 1 + 2 + 3 + … + (n-1) ≡ 0 (mod n) 
c) ¿Es cierto el resultado del apartado (b) si n es par? 
Problema 11. Sea n número entero positivo 
a) Demostrar por inducción que s 1 , + 2, + 3 , + … + -, = .((()*)+ /+ 
b) Si n es impar o un número entero positivo divisible por 4, demostrar que 
 1
3
 + 2
3
 + 3
3
 + … + (n-1)
3
 ≡ 0 (mod n) 
c) ¿Es cierto el resultado del apartado (b) si n es par no divisible por 4? 
2 Tema 2 Aritmética modular 
 
Problema 12. Demostrar, usando únicamente congruencias, que para todo natural n, el 
número 
3
2n+5 
+ 2
4n+1
 
es múltiplo de 7. 
Problema 13. Sea n un número entero,
demostrar: 
a) Si a es par, se verifica a
2
 ≡ 0 (mod 4) 
b) Si a es impar, se verifica a
2 ≡ 1 (mod 4) 
c) Si a es impar, se verifica a
2 ≡ 1 (mod 8) 
Problema 14. Un barco pirata naufraga y doce de sus tripulantes consiguen llegar a una 
isla desierta. Su primera tarea es la de dedicarse a recoger cocos que acumulan en una 
pila para repartírselos equitativamente a la mañana siguiente. Aunque ninguno dice 
nada, todos los piratas se dan cuenta de que si se hace el reparto equitativo sobrarían 3 
cocos, así que a lo largo de la noche se levantan todos ellos y se comen 3 cocos sin que 
el resto se entere. Esa misma noche mueren dos piratas y el resto decide repartirse los 
cocos, descubriendo que esta vez sobran cinco. Explicar por qué se desencadena una 
trifulca entre los piratas sobrevivientes y encontrar el mínimo número de cocos 
recogidos por los piratas sabiendo que eran más de quinientos. 
Problema 15. Una anciana va al mercado y un caballo pisa su bolsa y rompe los huevos 
que llevaba en ella. El jinete se ofrece a repararle los daños y le pregunta a la anciana 
cuántos huevos llevaba. Ella no recuerda el número exacto, pero sí que si los sacaba de 
dos en dos, finalmente le quedaba uno en la bolsa y lo mismo le ocurría si los sacaba de 
tres en tres, de cuatro en cuatro, de cinco en cinco y de seis en seis. Sin embargo, si los 
sacaba de siete en siete, la bolsa quedaba vacía. ¿Cuál es el menor número de huevos 
que llevaba la anciana en su bolsa? 
Problema 16. Tres agricultores se dividen una cierta cantidad de arroz en partes iguales 
obteniendo cada uno una cantidad natural de kilos. Cada uno de los agricultores vende 
su propio arroz en mercados distintos que utilizan pesos de 100 kilos, 45 kilos y 31 kilos 
y sólo compran múltiplos enteros de estos pesos. ¿Cuál es la menor cantidad de arroz 
que se han divido los agricultores si regresan a casa con 60, 25 y 15 kilos de arroz 
respectivamente? 
Problema 17. 
Problema 18. Dados números naturales n y b, denotemos por (ak,…, a1, a0)b la 
representación de n en base b (n = akb
k
 +ak-1b
k-1 
+ … + a1b + a0). Demostrar que se 
verifica: 
Si d es un divisor de b y, j y k son enteros positivos con j < k, (ak, …, a1, a0)b es 
divisible por d
j
 si, y sólo si, (aj-1, …, a1, a0)b es divisible por d
j
. 
 
Problema 19. Encontrar todos los números enteros positivos x que verifican las 
siguientes condiciones: 
a) 6x ≡ 4 (mod 10) 
b) El resto de dividir x por 8 es igual a y + 5, con y ≡ (1843)138648568243871569 (mod 11) 
y 0 ≤ y < 11. 
 
Problema 20. Responder las dos preguntas siguientes: 
a) ¿Existe algún número entero b ∈ Z que verifique 14b ≡ 5 (mod 294)? 
b) Sea a un número natural tal que 0 ≤ a < 500 y tal que las tres últimas cifras 
decimales de 17a son 001. ¿Qué valor tiene a? 
 
3 Tema 2 Aritmética modular 
 
Problema 21. Un sistema de congruencias 
$� ≡ �* (��� �*)� ≡ �+ (��� �+)⋮� ≡ �� (��� -)
� 
con los módulos bi distintos y mayores que uno, se dice completo si todo número entero 
satisface, al menos, una de las congruencias. 
Demostrar que son completos los sistemas de congruencias 
a) 
 !"
!# � ≡ 0 (��� 2)� ≡ 0 (��� 3)� ≡ 1 (��� 4)� ≡ 1 (��� 6)� ≡ 11 (��� 12)
�, b) 
 !
"
!# � ≡ 1 (��� 2)� ≡ 2 (��� 4)� ≡ 1 (��� 3)� ≡ 8 (��� 12)� ≡ 4 (��� 8)� ≡ 0 (��� 24)
�, c) 
 !
"
!# � ≡ 1 (��� 2)� ≡ 0 (��� 4)� ≡ 0 (��� 3)� ≡ 2 (��� 12)� ≡ 2 (��� 8)� ≡ 22 (��� 24)
� 
Problema 22. Deducir los criterios de divisibilidad del 9, del 11, del 5 y del 8. 
Problema 23. Sean a y b enteros positivos, demostrar que: 
a) el menor resto no negativo de 2
a 
- 1 módulo 2
b 
- 1 es 2
r 
- 1, donde r es el menor resto 
no negativo de a módulo b. 
b) El máximo común divisor de 2
a 
- 1 y 2
b 
- 1 es 2
mcd(a,b) 
– 1. 
c) 2
a 
- 1 y 2
b 
- 1 son coprimos si, y sólo si, a y b son coprimos. 
 
 
Bloque 1/Tema_2_Aritmetica_Modular/tema2_aritmetica_modular.pdf
Tema 2 Aritmética modular 
1 
 
Tema 2 
Aritmética modular 
 
2.1 Relaciones de equivalencia 
Definición 2.1 Una relación que verifique las propiedades reflexiva, simétrica y 
transitiva se denomina relación de equivalencia. Dos elementos relacionados se dicen 
equivalentes. 
Ejemplo 2.2 Son ejemplos de relaciones de equivalencia: 
� Relación de paralelismo entre rectas del plano. 
� La relación de equipotencia entre conjuntos definida por: 
A y B equipotentes ⇔ existe una aplicación biyectiva f: A → B. 
� En un conjunto de personas la relación haber nacido el mismo año. 
Las relaciones de equivalencia sirven para clasificar los elementos de un conjunto. 
Definición 2.3 Sea R una relación de equivalencia sobre un conjunto y sea a ∈ A. El 
conjunto de todos los elementos relacionados con A se denomina clase de equivalencia 
de a y se denota por [a] ó ��: 
�� = [a] = {x ∈ A  x R a} 
Teorema 2.4 Sea R una relación de equivalencia sobre un conjunto y sean a y b∈ A. 
Se verifica: 
1. �� = �� ⇔ a R b 
2. �� ≠ �� ⇔ �� ∩ �� = ∅ 
El teorema anterior nos dice que dada una relación de equivalencia en un conjunto A, las 
clases de equivalencia pertenecientes a A a o son iguales o son disjuntas. Como 
consecuencia se tiene: 
� Todos los elementos de una misma clase son equivalentes entre sí. 
� Una clase queda determinada por uno cualquiera de sus elementos, es su 
representante. 
Teorema 2.5 Sea R una relación de equivalencia sobre un conjunto A. Entonces, el 
conjunto de las clases de equivalencia de R constituye una partición en A. Al conjunto 
de las clases de equivalencia se le denomina conjunto cociente y se designa por A/R. 
A/R = {��  a ∈ A} 
Tema 2 Aritmética modular 
2 
 
 
2.2 Congruencias en ZZZZ módulo n 
Definición 2.6 (Congruencia módulo n) En el anillo de los números enteros (Z, +, .), 
dado un número entero positivo n, se define la siguiente relación: 
a ≡ b (mod n) ⇔ a – b es múltiplo de n, 
Esta relación es de equivalencia. 
Teorema 2.7 La relación de congruencia se puede reescribir como: 
a ≡ b (mod n) ⇔ el resto de la división euclídea de a y de b por n es el mismo. 
Demostración. 
Supongamos primero que a ≡ b (mod n). 
 a ≡ b (mod n) ⇒ Existe k ∈ Z tal que a – b = kn. Al realizar la división euclídea de b 
por n se tiene: b = pn + r con 0 ≤ r < n. Sustituyendo b en la expresión anterior se tiene 
que a = (k + p)n + r, con 0 ≤ r < n. Se ha obtenido que el resto de la división euclídea 
de a por n es también r. 
Recíprocamente, supongamos el resto de la división euclídea de a y de b por n es el 
mismo. Esto es, a = qn + r y b = pn + r con 0 ≤ r <n 
Restando se obtiene a – b = (q – p)n, por tanto a – b múltiplo de n. Lo que significa a ≡ 
b (mod n). � 
Por tanto, se tienen n clases de equivalencia en el conjunto cociente que suele escribirse 
en la forma Z/nZ o Zn, cada una de ellas correspondiente a uno de los posibles restos, es 
decir, 0, 1, …, n – 1. El conjunto {0, 1,…, n – 1} constituyen un sistema de 
representante de la relación de congruencia módulo n. 
Z/nZ = Zn = {0�, 1�,…, � � 1�������} 
 
2.3 Aritmética modular 
En el conjunto Zn se definen dos operaciones, suma o producto, de la forma siguiente: 
� Si �� y �� son dos clases de equivalencia, se define �� � �� 
 � � ��������, 
� Si �� y �� son dos clases de equivalencia, se define ��. �� 
 �. ������. 
Teorema 2.8 La operaciones suma y producto en Zn definidas anteriormente están bien 
definidas y dotan a Zn de estructura de anillo conmutativo con elemento identidad. 
Tema 2 Aritmética modular 
3 
 
Demostración. 
� Veamos primero que la suma está bien definida: Si a ≡ b (mod n) y c ≡ d(mod n), 
entonces a + c ≡ b + d (mod n) 
a ≡ b (mod n) ⇒ Existe r ∈ Z tal que a – b = rn 
c ≡ d (mod n) ⇒ Existe s ∈ Z tal que c – d = sn 
Sumando se tiene (a + c) – (b + d) = (r + s) n, esto es, a + c ≡ b + d (mod n) 
� Veamos que el producto está
bien definido: Si a ≡ b (mod n) y c ≡ d(mod n), 
entonces a . c ≡ b .d (mod n) 
a ≡ b (mod n) ⇒ Existe r ∈ Z tal que a – b = rn ⇒ Existe r ∈ Z tal que (a – b). c = rnc 
c ≡ d (mod n) ⇒ Existe s ∈ Z tal que c – d = sn ⇒ Existe s ∈ Z tal que b.(c – d) = bsn 
Sumando se tiene a.c - bd = (rc - bs) n, esto es, a.c ≡ b.d (mod n). 
� Se deja como ejercicio comprobar las propiedades. 0� es el elemento neutro respecto 
de la suma, el elemento opuesto de �� es la clase � � �������� y que el elemento neutro 
respecto al producto es la clase 1�. � 
Observación 2.9 Restos potenciales 
El hecho de que el producto sea una operación bien definida en Zn permite calcular los 
retos potenciales módulo n de las potencias sucesivas de un número dado N. 
Si llamamos a estos restos potenciales r1, …, rk módulo n, esto es, 
N ≡ r1(mod n), …., Nk ≡ rk(mod n), 
Se verifica que Nk+1 ≡ N Nk≡ r1. rk(mod n), 
Ejemplo 2.10 Los restos potenciales de 6 módulo 11 son: 
6 ≡ 6 (mod 11), 62 ≡ 36 (mod 11) ≡ 3 (mod 11), 63 ≡ 6*3 (mod 11) ≡ 7 (mod 11), 
6
4
 ≡ 6*7 (mod 11) ≡ 9 (mod 11), 65 ≡ 6*9 (mod 11) ≡ 10 (mod 11), 
6
6
 ≡ 6*10 (mod 11) ≡ 5 (mod 11), 67 ≡ 6*5 (mod 11) ≡ 8 (mod 11), 
6
8
 ≡ 6*8 (mod 11) ≡ 4 (mod 11), 69 ≡ 6*4 (mod 11) ≡ 2 (mod 11), 
6
10
 ≡ 6*2 (mod 11) ≡ 1 (mod 11) 
Se vuelven a repetir. 
Tema 2 Aritmética modular 
4 
 
Ejemplo 2.11 Una aplicación de las congruencias es la obtención de criterios de 
divisibilidad. Así, por ejemplo, se puede saber si un entero x es divisible por 3 sin 
realizar la división. 
Sea x = xn xn-1… x2 x1 x0 un número natural escrito en base diez, es decir, 
x = xn . 10
n
 + xn-1.10
n-1
 +… + x2.10
2
 + x1.10 + x0, y 0 ≤ xi≤ 9, ∀i∈ {0,…, n} 
Como 10 ≡ 1 (mod 3), se tendrá que xi.10i ≡ xi (mod 3), por tanto, 
� 
 ∑ ������ ���� 3�. 
En consecuencia, x es divisible por 3 si, y sólo si, ∑ ������ 0���� 3�, es decir, la suma 
de sus cifras es múltiplo de 3. 
 
2.4 Ecuaciones y sistemas de congruencias 
2.4.1 Ecuaciones de congruencias 
En este apartado se trata de resolver congruencias del tipo a x ≡ b (mod n) 
Proposición 2.12 La congruencia ax≡b (mod n) tiene solución si, y sólo si, d = 
mcd(a,n) divide a b. Además, si existe solución, esta es única módulo n/d. 
Demostración. Basta observar que la congruencia anterior tiene solución si, y sólo si, la 
ecuación diofántica ax + ny = b tiene solución. Sabemos que tiene solución si, y sólo si, 
d = mcd(a, n) divide a b. 
Las soluciones de la ecuación diofántica ax + ny = b son de la forma 
� 
 �� � 
�
� �
� 
 �� � 
�
� �
 
con t cualquier número entero y (x0, y0) una solución cualquiera de ax + ny = b. 
Todas ellas son congruentes módulo 
�
�. Por tanto la solución es única módulo 
�
�. � 
Ejemplo 2.13 Resuelve la siguiente congruencia: 10x ≡ 15 (mód 25) 
mcd(10,25) = 5 y 5 divide a 15, por tanto tiene solución, que es única módulo 25/5 = 5. 
La ecuación diofántica que resulta sería: 10 x + 25 y = 15. Una solución particular es (-1,1), 
por tanto el conjunto de soluciones es x = -1 +5 t, con t cualquier número entero. � 
Ejemplo 2.14 Resuelve la siguiente congruencia: 10x ≡ 7 (mód 25) 
Tema 2 Aritmética modular 
5 
 
mcd(10,25) = 5 y 5 no divide a 7, por tanto no tiene solución. � 
2.4.2 Sistemas de congruencias 
Veamos qué ocurre si hay varias congruencias 
Teorema 2.15 Teorema chino de los restos Sean m1,…, mn números enteros positivos 
coprimos dos a dos, es decir, mcd(mi, mj) =1 si i ≠ j y sean b1, …, bn enteros cualesquiera. 
Entonces, el sistema de congruencias 
x ≡ b1 (mod m1), …. , x ≡ bn (mod mn) 
Posee una única solución entera entre 0 y m1…..mn-1, es decir, una única solución entera 
módulo m1…mn. 
Demostración. Sean � 
 �1…�� y �� 
 !" 
 ��…��#� ��$�…�� para k =1,…,n. 
Puesto que los mi son coprimos dos a dos, se tiene que mcd(mk, Mk) =1 y, por tanto, existen 
enteros tk y sk tales que 
sk Mk + tk mk = 1, k = 1,.., n 
sk Mk es múltiplo de mj si j ≠ k y congruente con 1 módulo mk. En consecuencia bk sk Mk es 
congruente con 0 módulo mj si j ≠ k y congruente con bk módulo mk. Por tanto, 
b1 s1 M1 + … + bn sn Mn ≡ bk (mod mk), ∀k ∈1{,…, n}. 
Consideremos x = b1 s1 M1 + … + bn sn Mn, es una solución al sistema dado. 
Falta demostrar que es única módulo M: 
Supongamos que existen dos soluciones, x e y. Restando se tiene que 
x – y ≡ 0 (mod mk), ∀k ∈1{,…, n}. 
es decir, x – y es múltiplo de todos los mk, luego es múltiplo del mínimo común múltiplo de m1, 
m2,…, .mn que, al ser coprimos dos a dos es su producto, esto es, M. Por tanto, x ≡ y (mód M). 
� 
Ejemplo 2.16 Resolver el sistema de congruencias x ≡ 1 (mod 2), x ≡ 4 (mod 7), x ≡ 3 (mod 11) 
{2, 7, 11} son coprimos. Aplicando el teorema chino de los restos: 
M = 2*7*11 = 154, M1 = 7*11 = 77, M2 = 2*11 = 22, M3= 2*7 = 14 
s1M1 + t1m1 = 1, s1 77 + t1 2= 1, una solución particular (1,-38), considerar 1*77 = 77, 
s2M2 + t2m2 = 1, s1 22 + t1 7= 1, una solución particular (1,-3), considerar 4*22 = 88, 
s3M3 + t3m3 = 1, s1 14 + t1 11= 1, una solución particular (4,-5), considerar 3*4*14 = 168, 
x = 1*77 + 4*22 + 3*4*14 = 77 + 88 + 168 = 333 ≡ 25 (mod 154), solución única módulo 154: 
Tema 2 Aritmética modular 
6 
 
x = 25+ 154 t, con t cualquier número entero. � 
También lo podríamos hacer: 
x ≡ 1 (mod 2) ⇔ x = 1 + 2.t para algún t entero 
Sustituyendo en x ≡ 4 (mod 7): 1 + 2.t ≡ 4 (mod 7) ⇔ 2.t ≡ 3 (mod 7) 
Se tiene la ecuación diofántica: 2t + 7y = 3, sus soluciones son t = -9 + 7s para algún s entero. 
Esto es, x = 1 + 2.t = 1 + 2(-9 + 7s) = -17 + 14s para algún s entero. 
 Sustituyendo en x ≡ 3 (mod 11): -17 + 14s≡ 3 (mod 11) ⇔ 14s≡20 (mod 11) ⇔ 14s≡9 (mod 11) 
Se tiene la ecuación diofántica: 14s+11z = 9, sus soluciones son s = 36+11k para algún k entero. 
Esto es, x = -17 + 14s = -17 + 14(36+11k) = 487 + 154k para algún k entero. 
x = 487 + 154k = 25 + 154*3 + 154k = 25 + 154r para algún r entero. � 
Ejercicio 2.17 Manteniendo la notación de la demostración del Teorema Chino de los 
restos, probar que EjEk ≡ 0 (mod M) si j ≠ k, siendo Ek = sk Mk . Probar que, para todo 
entero a, si a ≡ ak (mod mk), se tiene 
� 
 ∑ %�!��� ������ ��. 
Ahora, llamemos a los coeficientes ak coordenadas de a. Probar que si b tiene 
coordenadas bk, entonces ak ± bk y akbk son las coordenadas de a ± b y de ab, 
respectivamente. 
 
Teorema 2.18 El Teorema Chino de los Restos establece una biyección entre & 
y &!'� …� &!(. Por otro lado, consideremos la aplicación dada por: 
): & + &!'� …� &!( , )��� 
 ���, … , ���, 
Donde los ak son las coordenadas de a como se han definido en el Ejercicio. El 
teorema Chino de los Restos nos dice como construir ψ--1. 
Por otro lado, recordando que se puede dotar a &!'�…� &!(de estructura de anillo 
definiendo suma y producto componente a componente. Lo que nos dice el ejercicio es 
que ψ(a + b) = ψ(a) + ψ(b) y ψ(a . b) = ψ(a) . ψ(b), es decir, que ψ es un 
homomorfismo de anillos y, al ser biyectivo, es un isomorfismo de anillos. 
En el Teorema Chino de los Restos, se supone que los módulos son siempre coprimos 
dos a dos. Veamos qué ocurre si los módulos no son necesariamente coprimos dos a 
dos. 
 
Teorema 2.19 El sistema de congruencias 
x ≡ b1 (mod m1), …. , x ≡ bn (mod mn) 
tiene solución si, y sólo si, bi ≡ bj (mod mcd (mi, mj) ) para todo i ≠ j. Si existe solución, es única 
módulo mcm(m1,…., mn). 
Demostración. 
Tema 2 Aritmética modular 
7 
 
� Supongamos, en primer lugar, que existe solución del sistema de congruencias. Si x 
es una solución, x ≡bi (mod mi) y x ≡bj (mod mj). En consecuencia, x - bi y x – bj son 
múltiplos de mi y mj. Por tanto, son múltiplos de mcd (mi, mj), de donde se deduce que bi 
≡ bj (mod mcd (mi, mj)). 
 
� La unicidad módulo mcm(m1,…., mn) se demuestra de forma análoga al
teorema Chino de 
los Restos. 
 
� Falta demostrar que si se verifica la condición del Teorema, entonces tiene solución. 
 
La demostración se basa en la reducción de un par de congruencias a una sola. 
Supongamos, pues, que debemos resolver 
x ≡ b1 (mod m1), 
x ≡ b2 (mod m2), 
De la primera se obtiene x = b1 + tm1, para algún t ∈ Z. Sustituyendo en la segunda, se 
tiene b1 + tm1 ≡ b2 (mod m2), en consecuencia, tm1 ≡ b2 - b1 (mod m2). 
Por hipótesis, d = mcd (m1, m2) divide a b2 - b1 y se verifica que �-� . !'� ,
!/
� 0 
 1 
divide a 
1/#1'
� . En consecuencia, la congruencia 
� ��� 
 
�2 � ��
� .��� 
�2
� 0 
tiene solución única módulo m2/d, la solución será t ≡ a (mod m2/d). Esto es, 
� 
 � � �� !/� para algún t1 ∈ Z. 
Sustituyendo esta expresión en x = b1 + tm1, se tiene 
� 
 �� � ��� � �� 
���2
� 
 �� � ��� � �� �-����,�2� 
En consecuencia, x ≡ b1 + am1 (mod mcm (m1, m2)). 
Repitiendo la construcción n -1 veces se obtiene la solución del sistema. 
� 
Ejemplo 2.20 Resolver el sistema de congruencias x ≡5 (mod 6), x ≡3 (mod 10), x ≡13 (mod 20) 
� mcd(6,10) = 2 5-3 = 2, mcd(6,20) = 2 13-5 = 8, mcd(10, 20) = 10 13-3 = 10, por tanto 
existe solución única módulo mcm(6,10,20) = 60. 
� Consideremos primero las ecuaciones x ≡ 5 (mod 6), x ≡ 3 (mod 10), mcd(6,10) = 2 que 
es divisor de 5-3 = 2. Existe solución común. 
� !'� 
 
1/#1'
� .��� 
!/
� 0, 3t ≡-1(mod 5), 3t + 5y = -1, una solución particular t = -2 
La solución es x ≡ b1 + am1 (mod mcm (m1, m2)), x ≡ 5 -2*6 (mod mcm (6,10)) ≡ -7 (mod 30) ≡ 
23 (mod 30) 
� Ahora hay que considerar las ecuaciones x ≡ 23 (mod 30) y x ≡ 13 (mod 20), mcd(10, 20) = 
10 que es divisor de 23 - 13 = 10 
� !'� 
 
1/#1'
� .��� 
!/
� 0, 3t ≡1(mod 2), 3t + 2y = 1, una solución particular t = 7. 
Tema 2 Aritmética modular 
8 
 
La solución es x ≡ b1 + am1 (mod mcm (m1, m2)), x ≡ 23 -7*30 (mod mcm (30,20)) ≡ -187 (mod 
60) ≡ -7(mod 60) ≡ 53(mod 60). 
La solución es x ≡ 53(mod 60). � 
 
2.5 Aplicaciones del cálculo de congruencias: Sistema criptográfico de 
clave pública RSA. 
En esta sección se va a describir un sistema criptográfico que se conoce como RSA. La idea es 
transmitir mensajes por canales “inseguros” (esto es, accesibles a individuos distintos del emisor 
y del receptor) sin que puedan ser comprendidos más que por el emisor y el receptor. Esto exige 
un proceso de codificación del mensaje y su posterior decodificación. Los caracteres del 
mensaje se traducen a números, se envían números. 
Codificación 2.21 
� Se eligen dos números primos grandes p y q y se considera n = p.q 
� Se elige un número e, con 1 < e < (p-1)(q-1) y mcd(e,(p-1)(q-1))=1 
� Se transforma el número entero M, que representa el mensaje a enviar, en C con C ≡ 
M
e
(mod n) 
Descifrado 2.22 
El siguiente teorema, que demostraremos más adelante, justifica el descifrado. 
Pequeño teorema de Fermat: “Si p es primo y a es un entero no divisible por p, entonces a
p-1
 ≡ 
1(mod p)” 
El mensaje se puede recuperar cuando se conoce la clave de descifrado d. 
d verifica de ≡ 1(mod (p-1)(q-1)) (Este número d existe) 
Se sigue que C
d ≡ (Me)d (mod n) = Med ≡ M1+ k (p-1)(q-1) (mod n) ≡ M(M (p-1))k(q-1) (mod n) 
Al ser n = p.q, se verifica 
C
d ≡ M(M (p-1))k(q-1) (mod p) ≡ M.1 (mod p) ≡ M (mod p) 
C
d ≡ M(M (q-1))k(p-1) (mod q) ≡ M.1 (mod q) ≡ M (mod q) 
Al ser C
d solución del sistema de congruencias x ≡ M (mod p), x ≡ M (mod q). Por el 
teorema chino de los restos se sigue que la solución, M, es única módulo mcm(p, q) = 
p.q = n. 
Por tanto C
d ≡ M (mod n) permite leer el mensaje. � 
 
 
 
Bloque 2/Ejemplo_Newton.pdf
Construir el polinomio interpolador para los siguientes datos de una función f: 
f(0) = 5, f(1) = -2, f’(1) = 5, f’’(1) = 10, f’’’(1) = 3, f(4) = 1 y f’(4) = -2 
xi f[xi] f[xi,xi+1] f[xi,xi+1,xi+2] f[xi,xi+1,xi+2,xi+3] f[xi,xi+1,xi+2,xi+3,xi+4] f[xi,xi+1,xi+2,xi+3,xi+4,xi+5] f[xi,xi+1,xi+2,xi+3,xi+4,xi+5 ,xi+6] 
0 5 
 �2 � 5
1 � 0 � �7 
 
1 -2 5 � ��7	
1 � 0 � 12 
 
 f[1,1] = f’(1) = 5 5 � 12
1 � 0 � �7 
 
1 -2 f[1,1,1] = 
����	 
�! = 5 
 1
2 � ��7	
1 � 0 �
15
2 
 
 f[1,1] = f’(1) = 5 f[1,1,1,1] = 
������	
�! � 
�
�! �
�
� 
 ��4754� �
15
2
4 � 0 �
�113
54 
 
1 -2 f[1,1,1] = 
����	 
�! = 5 
 ��199 � �
1
2
4 � 1 � �
47
54 
 87
162 � ��
113
54 �
4 � 0 �
71
108 
 f[1,1] = f’(1) = 5 ��43� � 5
4 � 1 �
�19
9 
 20
27 � ��
47
54�
4 � 1 �
87
162 
 
1 -2 1 � 5
4 � 1 �
�4
3 
 1
9 � �
�19
9 �
4 � 1 �
20
27 
 
 1 � ��2	
4 � 1 � 1 
 �1 � ��43	
4 � 1 �
1
9 
 
4 1 �2 � 1
4 � 1 � �1 
 
 -2 
4 1 
 
P6(x) = f[0]+f[0,1](x-0)+f[0,1,1](x-0)(x-1)+f[0,1,1,1](x-0)(x-1)
2
+f[0,1,1,1,1](x-0)(x-1)
3
+f[0,1,1,1,1,4](x-0)(x-1)
4
+f[0,1,1,1,1,4,4](x-0)(x-1)
4
(x-4) 
= 5 � 7� � 12 ��� � 1	 � 7��� � 1	� � ��� ��� � 1	
� � ����� ��� � 1	
� � ����� ��� � 1	
� (x-4) = 
71 � � 794 �� � 3276 �� � 6530 �� � 7349 �� � 4128 � � 540
108 � 
71
108 �
 � 39754 �
� � 913 �
� � 326554 �
� � 7349108 �
� � 3449 � �
185
27 
 
 
 
 
 
 
 
 
 
 
 
Bloque 2/Tema_3_Cuerpos_Finitos/problemas3_cuerpos_finitos.pdf
1 Problemas tema 3: Cuerpos finitos 
 
Problema 1. Calcular el resto de dividir : 
(a) 19862061 por 7, (b) 16541255 por 23, (c) 2931767 por 7, (d) 62000 por 11 
(e) (1843)138648568243871569 por 11 
 
Problema 2. Hallar las dos últimas cifras de 75448. 
 
Problema 3. Demuestra que 1241es un divisor de 872 – 1 
 
Problema 4. Sea p un número primo impar, Demuestra que sólo son inversos de sí 
mismos en Zp 1� � � − 1�������. 
 
Problema 5. Encontrar el menor resto no negativo de 1! + 2! + 3!+… + 10! módulo 
cada uno de los siguientes enteros a) 3, b) 11, c) 4, d) 23 
 
Problema 6. Encontrar el menor resto no negativo de 1! + 2! + 3!+… + 100! módulo 
cada uno de los siguientes enteros a) 2, b) 7, c) 12, d) 25 
 
Problema 7. Encontrar el menor resto no negativo de: 
6! Módulo 7, (b) 10! Módulo 11, (c) 12! Modulo 13, (d) 16! Modulo 17. 
 
Problema 8. Demuestra que: 
(a) 437 es divisor de 18! +1, (b) 11 es divisor de 10! +1 
 
Problema 9. Encontrar los restos de la división euclídea en los siguientes casos: 
(a) 16! dividido por 19, (b) 5!25! dividido por 31, (c) 8*9*10*11*12 por 7 
(d) 8*9*10*11*12*13 por 7 (e) 3
999999999
 dividido por 17 
 
Problema 10. Encuentra el resto de dividir 40! por 1763. 
 
Problema 11. Demostrar que 310 ≡ 1(mod 112) 
 
Problema 12. Se considera la expansión en base 7 de 3100: 
(a) Encuentra el último dígito, (b) Encuentra los dos últimos dígitos. 
 
Problema 13. Demuestra que si p es un número primo impar, se verifica 
2( p- 3)! ≡ -1(mod p) 
 
Problema 14. Demuestra que si n es un entero compuesto con n ≠ 4, se verifica que 
(n -1)! ≡ 0 (mod n) 
 
Problema 15. Demuestra que a12-1 es divisible por 35 si mcd(a, 35) = 1 
 
Problema 16. Demuestra que a6-1 es divisible por 168 si mcd(a, 42) = 1 
 
Problema 17. Demuestra que 42 es divisor de n7 – n, para todo entero positivo n. 
 
Problema 18. Demuestra que 30 es divisor de n9 – n, para todo entero positivo n. 
 
Problema 19. Si p es un número primo impar, demuestra que 
2 Problemas tema 3: Cuerpos finitos 
 
1
p 
+ 2
p 
+ 3 
p
+ ….+ (p-1)
p
 ≡ 0 (mod p) 
 
Problema 20. Demuestra que si p es número primo y, a y b son enteros no divisibles 
por p, con a
p
 ≡ b
p
 (mod p), se verifica a
p
 ≡ b
p
 (mod p
2
). 
 
Problema 21. Demostrar que si p y q son dos primos distintos, se verifica que 
p
q-1 
+ q
p-1
 ≡ 1 (mod pq) 
 
 
Problema 22. Demuestra que si p es primo y p ≡ 3 (mod 4), se verifica que �� − 12 	 ! ≡ ±1(��� �) 
 
Problema 23. Encontrar los inversos de los números dados en los cuerpos que se 
indican: 
(a) 3, 5, 8 en Z13,
(b) 3, 6, 9, 10 en Z11, (c) 3, 4, 2 , en Z5, (d) 3, 11, 15, 22 en Z23. 
 
Problema 24. Resolver los siguientes sistemas de congruencia: 
(a) �� + 2� + 3� ≡ 1(��� 7)� + 2� + 4� ≡ 1(��� 7)� + 4� + 6� ≡ 1(��� 7) �, (b) �
3� + � + 3� ≡ 1(��� 5)� + 2� + 4� ≡ 2(��� 5)4� + 3� + 2� ≡ 3(��� 5)�, 
(c) �� + 2� + 3� ≡ 1(��� 7)� + 2� + 5� ≡ 1(��� 7)� + 4� + 6� ≡ 1(��� 7) �, (d) �
� + 2� + 3� ≡ 1(��� 11)� + 2� + 5� ≡ 1(��� 11)� + 4� + 6� ≡ 1(��� 11) �, 
(e) � 3� + � + 3� ≡ 1(��� 7)� + 2� + 4� ≡ 2(��� 7)4� + 3� + 2� ≡ 3(��� 7)�, (f) �
3� + � + 3� ≡ 1(���13)� + 2� + 4� ≡ 2(��� 13)4� + 3� + 2� ≡ 3(��� 13)� 
 
Problema 25. (Residuos cuadráticos) Un entero a se dice residuo cuadrático módulo n 
si mcd(a, n) = 1 y la ecuación 
x
2
 ≡ a (mod n) 
posee solución. Por ejemplo, en Z11, los residuos cuadráticos son 1, 3, 4, 5 y 9. 
Sea n = 4, p
k
, 2p
k
 (p primo impar). Demostrar que a es residuo cuadrático si, y sólo si, ��(�)� ≡ 1(��� ) 
 
Problema 26. Sea p un primo impar y mcd(a, p) = 1. Demostrar que a es residuo 
cuadrático módulo p si �!"#� ≡ 1(��� �) y que a no es residuo cuadrático módulo p si �!"#� ≡ −1(��� �) 
 
Problema 27. Sea p un primo impar y mcd(a, p) = 1. Demostrar que la ecuación x2 ≡ a 
(mod p) tiene o dos soluciones o ninguna módulo p. 
 
Problema 28. Demostrar que en Zp (p primo impar) hay tantos residuos cuadráticos 
como no residuos cuadráticos. 
 
Problema 29. Demostrar que la ecuación X2 + 1 ≡ 0 (mod p) tiene solución si, y sólo si, 
p = 2 o p ≡ 1 (mod 4). 
Bloque 2/Tema_3_Cuerpos_Finitos/tema3_El_cuerpo_Zp.pdf
Tema 3 
 
El cuerpo (��, +, .) (p número primo) 
3.1 El grupo multiplicativo ��� 
En el tema anterior se vio que (Zm, +, .) es un anillo conmutativo con elementos 
identidad. No preguntamos ahora para qué elementos existe inverso. A los elementos 
que poseen inverso se les denomina identidades. 
 
Proposición 3.1 El conjunto de las unidades del anillo (Zm, +, .) forman un grupo 
conmutativo, a dicho conjunto lo desinaremos por ��� . (En todo anillo conmutativo y 
con identidad el conjunto de las unidades forman un grupo conmutativo). 
 
Demostración. 
��� � � 	
∈ � �|�
� ��� � �������	��� 	
. 
� � 1
 � 
� Veamos que la operación multiplicación heredada de Zm es interna: 
Sean 	
,�
∈��� , esto es, existen 
� e � �∈Zm tales que 	
. 
� � 1
 y �
. �
 � 1
. Al ser la 
operación multiplicación asociativa y conmutativa se verifica que 1
 � 	
. 
�!. "�
. �
# �
"	
. �
#. 
�. �
! � "	�
#. 
�
! . Por tanto "	�
# ∈ ��� . 
� La operación es asociativa y conmutativa por serlo en Zm. 
� La identidad 1
∈ ��� . 
� Todo 	
∈ ��� tiene inverso. � 
 
Proposición 3.2 Un elemento a ∈ Zm es unidad si, y sólo si, mcd(a, m) = 1, es decir, 
��� � �	
 � ��|$�� 	,$! � 1�� 
 
Demostración. 	
 ∈ Zm es unidad si, y sólo si, existe 
� ∈ Zm tal que 	
 ≡ 1(mod m), es 
decir, si y sólo si, ax + my = 1 para algún entero y. Esto es, si y sólo si, la ecuación 
diofántica ax + my = 1 tiene solución. Y esto es equivalente a mcd(a, m) = 1. � 
Definición 3.3 Un conjunto K dotado de dos operaciones internas, +, ., verificando: 
� (K, +, .) es anillo conmutativo con elemento identidad. 
� Todo elemento de K distinto del 0 (0 es elemento neutro respecto de la suma) tiene 
inverso respecto de la multiplicación (Ello significa que, K-{0}, .) es grupo 
conmutativo) 
se dice que tiene estructura de cuerpo. 
Como consecuencia de la proposición anterior se verifica la siguiente proposición: 
Proposición 3.4 ( ��� , . ! tiene estructura de grupo. 
Teorema 3.5 El anillo Zm es cuerpo si, y sólo si, m es primo. 
Tema 3 El cuerpo Zp 
 
Demostración. 
Si m es primo, todo entero que no es múltiplo de m es coprimo con m. En consecuencia, 
��� � �� & �0
�. Por tanto Zm es cuerpo. 
Recíprocamente, si Zm es cuerpo, ��� � �(� � ��|$�� 	,$! � 1�� � � � & �0
�. 
Si m no fuese primo tendría un divisor a distinto de 1 y de m. Se tendría que mcd(a,m) 
=a, a ≠ 1, a ≠ 0 y 	
 ) ��� . Lo que contradice que , ��� � � � & �0
�. Por tanto m es 
primo. � 
 
 
3.2 Función de Euler 
Definición 3.6 Para un número positivo m, se define la función ϕ(m) como el número 
de enteros entre 0 y m que son primos con m. Esta función se dice Función de Euler. 
ϕ(m) = |��� | (esto es, el cardinal del conjunto ��� ) 
 
En lo que sigue se va a encontrar una fórmula que nos de el valor de la Función de 
Euler. Recordando el teorema fundamental de la aritmética: Todo entero positivo puede 
expresarse como producto de potencias no triviales de números primos; se va a proceder 
a calcular ϕ(m) para todo entero positivo m. 
 
Lema 3.7 Si p es un número primo, se verifica ϕ(p) = p – 1. 
 
Demostración. Si p es un número primo todos los números enteros positivos menores 
que p son coprimos con p: 1, 2, 3, …, p – 1. Por tanto ϕ(p) = p – 1. � 
 
Lema 3.8 Sea q un número positivo potencia de un número primo, esto es, con q = p
α
, 
con p primo. 
ϕ(pα) = * +1 & ,-. 
 
Demostración. 
Los enteros positivos menores que q = p
α
 coprimos con él son los no son divisibles por 
p. 
Los enteros positivos menores que p
α
 divisibles por p son: p, 2p, 3p, 4p, ….., p
α
 = p
α-1
p, 
hay p
α-1
. Los coprimos con él son todos los números positivos menores o iguales a p
α
 
(hay a p
α
) excepto esos p
α-1
. Por tanto 
 ϕ(pα) = pα - pα-1 = /0 +1 & ,-. � * +1 &
,
-. (p primo) � 
 
Lema 3.9 Si mcd(m1, m2) =1, la función ϕ verifica: ϕ(m1.m2) = ϕ(m1) .ϕ(m2), 
 
Demostración. 
mcd(a, m1) = 1 y mcd(a,m2) = 1⇔ mcd(a, m1m2) =1 
En el tema anterior se vio que existía una aplicación biyectiva: 
ψ: ��1�2� →→→→ ��1� ��2� 
Tema 3 El cuerpo Zp 
 
Por tanto, ϕ(m1.m2) = 3��1�2� 3= 3��1� 33��2� 3 = ϕ(m1) .ϕ(m2) � 
 
Teorema 3.10 Sea $ � ∏ /506758, la factorización en potencias de primos de m, se 
verifica 
9 $! � $:;1 & 1/5<
7
58,
 
Demostración. Teniendo en cuenta los resultados anteriores y mcd(/=0>, /?
0@
) = 1, si i ≠ j, 
se verifica 
9 $! � ∏ 9 /506758, ! � ∏ /506 +1 & ,-6.
758, � $∏ +1 & ,-6.
758, � 
 
Teorema 3.11 (Euler-Fermat) Si a y m son coprimos, se verifica a
ϕ(m) ≡ 1 (mod m). 
 
Demostración. Sean k = ϕ(m) y n1, n2,…,nk todos los enteros positivos menores que m y 
primos con m. No son congruentes entre ellos módulo m. 
Consideremos ahora an1, an2,…, ank. Al ser a primo con m y cada ni primo con m, se 
verifica que todos ellos son primos con m. 
Además, no son congruentes entre ellos módulo m. En efecto, si ani ≡ anj (mod m), m 
dividiría a a(ni - nj). Al ser n primo con a tendría que dividir a (ni - nj), esto es, 
ni≡nj(mod m), que contradice el hecho de que entre ellos no sean congruentes módulo n. 
En consecuencia, en {	�,
,…, 	�5
} hay k elementos distintos de Zn que son coprimos 
con n. En consecuencia, se verifica 
{�,
,…, �5
} = {	�,
,…, 	�5
} y akn1 … nk ≡ n1 … nk (mod m) 
Por hipótesis todos los �A 
son inversibles módulo n en Zm, por lo que, ak ≡ 1 (mod m) � 
 
El teorema anterior es útil si tratamos con potencias de números enteros. 
 
Ejemplo 3.12 Calcular el resto de la división euclídea de 2
1010
 por 23. 
Como 23 es primo, es ϕ(23) = 22, y como 1010 = 45.22 + 20, se tiene: 
2
1010
 ≡ (222)45 220 ≡ 2 20 ≡ (32)4≡ (9)4≡ (92)2 ≡ (81)2≡ (12)2≡ 144≡ 6 (mod 23) � 
 
Corolario 3.13 (Pequeño Teorema de Fermat) Si p es primo, 
a
p
 ≡ a (mod p) 
Demostración. Basta recordar que si p es primo ϕ(p) = p – 1. 
 
Algoritmo 3.14 (Algoritmo para el cálculo de potencias) 
Supongamos que necesitamos calcular la potencia trigésimo séptima de un entero a. 
La manera más ingenua de hacerlo es calcular las potencias sucesivas, 
a, a
2
, a
3
,…, a
36
, a
37
, 
lo que implica realizar 36 productos. 
Sin embargo, 
a
37
 = a . a
36
 = a . (a
2
)
18
 = a . (a
4
)
9
 = a .
a
4
 . (a
4
)
8
 = a . a
4
 . a
32
. 
Tema 3 El cuerpo Zp 
 
¿Cuántos productos necesito si actúo de esta manera? En primer lugar, 5 productos para 
calcular a
4
 y a
32
 haciendo (cada flecha significa elevar al cuadrado): 
a → a2 → a4 → a8 → a16 → a32: 
Con otros dos productos más, calculo a
37
. En total, 7 productos frente a los 36 por el 
método ingenuo. 
En realidad, hemos calcular la representación binaria del exponente, en este caso, 37 = 1 
+ 2
2
 + 2
5
 (37 = (100101)2). Este razonamiento es fácilmente extensible a cualquier otro 
exponente: si quiero calcular a
α
 siendo α = 
2
k
 + αk-1. 22k-1 +… + α2. 22 + α1. 2+α0, se tendrá que: 
 	0 � 	αB . 	α1C. 	α2C2 …	αEF1CEF1	C6 � 
 
 
Ejemplo 3.15 Calcular el resto de la división euclídea de 2
1010
 por 23. 
Como 23 es primo, es ϕ(23) = 22, y como 1010 = 45.22 + 20, se tiene: 
Por otra parte, 20 = 2
4
 + 2
2
 es la representación binaria de 20 
2,H,H I 2CH I 2,J2K, 22≡ 4 (mod 23), 2K I 16 $�� 23! 
2N I 64 $�� 23! I 3 $�� 23!, 2,J I 9 $�� 23!, 
2,H,H I 2CH I 2,J2K I 144 I 6 $�� 23! � 
 
 
3.3 El grupo multiplicativo �Q� (con p número primo). 
3.3.1 Polinomios con coeficientes en ZZZZp 
Lema 3.16 Sea f(x) = x
d
 + ad-1x
d-1 
+ …+ a1x + a0 un polinomio con coeficientes enteros 
y a un número entero. Existe un polinomio g(x) con grado d-1 y coeficientes enteros 
verificando f(x) = (x – a) g(x) + f(a). 
 
Demostración. 
Basta recordar la formula (x
n 
- y
n
) = (x – y)( x
n-1
 + x
n-2
y + … + x y
n-2
 + y
n-1
) 
f(x) - f(a) = x
d
 + ad-1x
d-1 
+ …+ a1x + a0 – (a
d
 + ad-1a
d-1 
+ …+ a1a + a0) 
= (x
d
 - a
d
) + ad-1 (x
d-1
- a
d-1
) + … + a1(x – a) 
Aplicando la fórmula indicada todos los sumandos son múltiplos de (x – a) , con lo que 
se puede sacar factor común. Además, el exponente mayor de x corresponde a la 
expresión (x
d
 - a
d
) = (x – a)( x
d-1
 + x
d-2
a + … + x a
d-2
 + a
d-1
) 
Por tanto, se tiene f(x) - f(a) = (x – a)g(x) con grado d -1. Esto es, 
f(x) = (x – a) g(x) + f(a) para todo entero a y para todo entero x. � 
 
Lema 3.17 Sea f(x) = x
d
 + ad-1x
d-1 
+ …+ a1x + a0 un polinomio con coeficientes enteros 
y p un número entero primo. Entonces, la ecuación f(x) ≡ 0 (mod p) tiene, a lo más, d 
soluciones en Zp.(Esto significa que el número de raíces de la ecuación en Zp no excede 
al grado) 
 
Demostración. 
Aplicando al resultado anterior congruencias p. Se verifica que: 
 f(x) = (x – a) g(x) + f(a) (mod p) para todo entero x. 
Veamos las tesis por inducción sobre el grado d. 
Tema 3 El cuerpo Zp 
 
� Para d =1: Si f(x) = x + a0 (mod p), es cierto, pues existe exactamente 1 solución 
x ≡ (p-a0) (mod p). 
� Supongamos cierto para d - 1 y veamos que es cierto para d. 
� Sea f(x) = x
d
 + ad-1x
d-1 
+ …+ a1x + a0. 
Si no existiesen raíces sería cierto, el número de raíces es 0 que es menor o igual que 
d. 
Su pongamos que existe al menos una, sea a, f(a) ≡ 0 (mod p). 
Se verifica f(x) = (x – a) g(x) + f(a) (mod p) ≡ (x – a) g(x) (mod p), siendo g(x) un 
polinomio con grado d - 1. Con lo cual, 
 
f(x) = (x – a) g(x) ≡ 0 (mod p) 
Por lo que, las raíces de f(x) distintas de a serían raíces de g(x). Además, g(x) es un 
polinomio de grado d-1. Por hipótesis de inducción, a lo más, tiene d-1 raíces en Zp. En 
consecuencia, f(x) tiene, a lo más, d raíces en Zp. � 
 
Lema 3.18 Sea p un número entero primo, la congruencia x
p-1
 ≡ 1 (mod p) tiene, 
exactamente, p - 1 raíces en Zp. 
 
Demostración. 
Por el Pequeño Teorema de Fermat se sabe a
p-1
 ≡ 1 (mod p), para todo a entero. Esto 
significa que que 1, 2, 3, …, p -1 son soluciones de la ecuación dada. Por otra parte, el 
lema anterior dice que a lo más tiene p -1 raíces. En consecuencia la ecuación dada tiene 
exactamente p raíces en Zp. � 
 
Lema 3.19 Si dp-1, la congruencia xd ≡ 1 (mod p) y tiene, exactamente, d soluciones en 
Zp. 
Demostración. Por el lema 3.15 sabemos que la congruencia tiene, a lo más, d 
soluciones. 
Al ser dp-1, existe k el cociente exacto de dividir p -1 entre d, esto es, kd = p-1. 
Por otra parte, se verifica la identidad x
k
 – 1 = (x – 1)(x
k-1 
+ … + x + 1). 
Sustituyendo en dicha identidad x por x
d
, se tiene: 
x
dk
 – 1 = (x
d
 – 1)(x
d(k-1) 
+ x
d(k-2) 
+ … + x
d
 + 1), esto es, 
x
p-1
 – 1 = (x
d
 – 1)(x
p-d-1 
+ x
p-d-2 
+ … + x
d
 + 1), 
Como xp-d-1 + xp-d-2 + … + xd + 1≡ 0 (mod p) tiene, a lo más, p - d -1 soluciones, si xd ≡ 1 
(mod p) tuviese menos de d soluciones, entonces xp-1 ≡ 1 (mod p) no tendría p - 1 
soluciones, esto sería contradictorio. � 
 
3.3.2 Orden de un elemento en el anillo (�R� , +, .) 
Definición 3.20 Si a es un elemento de ��� , se llama orden de a en ��� y se escribe 
ordm(a), al menor entero positivo d que verifica a
d
 ≡1 (mod m). 
 
Tema 3 El cuerpo Zp 
 
El teorema de Fermat justifica la existencia de enteros que verifican la condición: 
Si a es un elemento de ��� , se verifica aϕ(m) ≡ 1 (mod m). En particular, ordm(a) ≤ ϕ(n). 
 
Ejemplo 3.21 Consideremos el grupo multiplicativo �S� , analicemos las potencias de 3 
3
1
 = 3, 3
2
 = 2, 3
3
 = 6, 3
4
 = 4, 3
5
 = 5 y 3
6
 = 1, En �S� , ord(3) = 6. 
Lema 3.22 Si a
n
 ≡ 1 (mod m), entonces ordm(a) divide a n. 
Demostración. Sea n con a
n
 ≡ 1 (mod m) y llamemos d a ordm(a). Es d ≤ n, pues d es el 
menor entero positivo que cumple la condición. Consideremos la división euclídea de n 
por d: n = q.d + r con 0 ≤ r < d, observar que al ser d ≤ n es q ≥ 1. 
1 = a
n
 = a
qd + r
 = (a
d
)
q 
. a
r 
= a
r
, 
Por definición de orden, r = 0. 
Lema 3.23 Sea a un entero con mcd(a, m) = 1. Si a
e
 ≡ af ≡ 1 (mod m), entonces ad ≡ 1 
(mod m), donde d = mcd(e, f). 
 
Demostración. 
Si d = mcd(e, f) existen números enteros x e y tales que d = ex + fy. En cuyo caso, se 
tiene a
d
 ≡ aex + fy ≡ (ae)x . (af)y ≡ 1 (mod m). � 
Lema 3.24 Sean a y b enteros con ordp(a) = r y ordp(b) = s en �-� . Si r y s son 
coprimos, el orden de ab en �-� es igual a r.s. 
Demostración. Llamemos d al orden de ab. 
Se verifica que (ab)
rs
 ≡(ar)s (bs)r ≡ 1 (mod p). Por el lema anterior d divide a rs. 
Supongamos que d ≠ rs, existe k ≠ 1 tal que dk = rs, es más existe un número primo q 
que divide a k (cualquier número primo de la descomposición en factores de k), rs = dk 
= dqt, esto es 
TU
V � �W es múltiplo de d. En consecuencia, (ab)rs/q ≡ 1 $�� /!. 
Puesto que mcd(r, s) = 1 y q es divisor de rs, q dividirá uno de ellos, pero no a los dos a 
la vez. Supongamos que divide a r (sería análogo si dividiese a s) y no divide a s. 
Se verifica, 1 ≡ (ab)rs/q ≡ (a)rs/q(bs)r/q ≡ (a)rs/q (mod p) 
Además, al ser ordp(a) = r, se verifica (a)
r
 ≡1 (mod p) 
Como � � TV . * y 
TU
V � 
T
V . X y q no divide a s, se verifica que $�� + 
TU
V , �. �
$�� + TV X,
T
V *. �
T
V . $�� X, *! �
T
V 
Se ha obtenido (a)
r
 ≡1 (mod p) y (ab)rs/q ≡ 1 (mod p) $�� + TUV , �. �
T
V. Por el lema 3.23, 
se tiene que (a)
r/q
 ≡ 1(mod p), siendo r/q < r, lo que contradice que ordp(a) = r. 
Tema 3 El cuerpo Zp 
 
Por tanto d = rs. � 
Teorema 3.25 Si p es primo, existe a ∈�-� , tal que 
�-� � �	, 	C, 	Y, … , 	-Z,� 
Esto significa que �-� es un grupo cíclico y que a se dice que es un generador de �-� . 
Demostración. Sea ∏ /=[>7=8, la factorización en primos de p – 1. /=[> y /=[>Z, son 
divisores de p – 1. Por tanto, se verifica que 
->\> I 1 $�� /! tiene exactamente /=[> 
soluciones y 
->\>F1 I 1 $�� /! tiene exactamente /=[>Z, soluciones. Por tanto, existe 
alguna solución de la primera congruencia que no lo es de la segunda, esto es, existe ai 
verificando 	=->\> I 1 $�� /!, pero 	=->\>F1 ] 1 $�� /!. En consecuencia, el orden 
de ai es divisor de /=[>, pero no