TEORÍA DE LOS NÚMEROS

• El interés del hombre por los números es tan antiguo como la

civilización. Son muchos los pueblos antiguos que se interesaron
por los números bien por razones practicas inmediatas, bien por
su relación con la astronomía y el cómputo del tiempo o incluso
asociados a la adivinación y el esoterismo. Entre todos ellos
destacan los griegos, que llegaron a desarrollar una teoría de
números pura guiada por criterios estrictamente maten áticos en
el sentido moderno de la palabra.
• Los griegos descubrieron las leyes básicas de la aritmética.
Conocían la división euclídea, los números primos, el cálculo del
máximo común divisor y el mínimo común múltiplo, etc.
• Lo que hicieron los griegos al desarrollar la aritmética elemental
fue simplemente descubrir el lenguaje de los números, lo cual no
equivale a entender lo que se lee en ese lenguaje. Para entender
lo que queremos decir consideraremos un ejemplo tomado de la
Aritmética de Diofanto.
 ¿QUÉ ES LA TEORÍA DE LOS NÚMEROS?

• Es la parte de las Matemáticas que estudia los

números enteros y sus propiedades

Matemática Antigua Matemática Actual

Teoría de los
Números
Números
Figuras Geometría
 Gauss, 1801

La aritmética superior nos proporciona un conjunto

inagotable de verdades interesantes — de verdades que
además no están aisladas, sino en estrecha relación unas
con otras, y entre las cuales, con cada sucesivo avance de
la ciencia, descubrimos nuevos y, a veces, completamente
inesperados puntos de contacto.
C.F.Gauss

“La Matemática es la reina de las ciencias y la Teoría de los Números es la reina de las
Matemáticas”

Uno de los aportes más significativos de Gauss a la Teoría de Números, es la

formalización de la Aritmética Modular en su famoso Disquisitiones rithmeticae
(Investigaciones sobre aritmética) de 1801.
 NÚMEROS PRIMOS Y SU DISTRIBUCIÓN

? ¿Qué es un número primo?

Aquél divisible sólo por él mismo y por 1

2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...

? ¿Cuántos números primos hay?

EUCLIDES (c.300 a.d.C.): Infinitos

“Más que cualquier cantidad de primos

dada”.
 NÚMEROS PRIMOS Y SU DISTRIBUCIÓN

? ¿Cuántos números primos hay?

EULER (1737): La infinitud se puede

demostrar utilizando series infinitas. Hay
más primos que cuadrados.

? ¿En qué proporción?

CHEBYSHEV (1848): A la larga, la proporción se

hace tan pequeña como se quiera pero decrece
menos rápidamente que K/log x .
 EMPIRISMO: FILOSOFÍA “OFICIAL” DE LA CIENCIA

Hume: Las ideas son impresiones

debilitadas

Abstracción,
Realidad
Matemáticas

Hume, 1736

“A los matemáticos les es habitual pretender que las ideas de que se

ocupan son de naturaleza tan refinada y espiritual que no son dominio de
la fantasía, sino que deben ser comprendidas por una visión pura e
intelectual de la que sólo las facultades del alma son capaces.”
La mayoría de los matemáticos consideran que el valor
estético de la teoría de números y de las Matemáticas en
general, supera su hipotético valor utilitario.

Pero ...

Gracias a los números primos y sus propiedades se pueden

hacer conexiones seguras por canales inseguros, acreditar
identidades , etc.

No es propaganda. Las conexiones seguras en internet

hoy (protocolos SSH, SSL, firmas electrónicas)
funcionan así
de manera cotidiana.
 ¿CÓMO CONSTRUIR “CANDADOS” CON LOS PRIMOS?

Cosas fáciles (con ordenador):

· Multiplicar dos primos grandes
· Calcular el resto r de ab al dividir por p

Cosas difíciles (incluso con ordenador):

· Factorizar
· Tomar “logaritmos”: hallar b a partir de a, r y p

· RSA (Rivest, Shamir, Adleman 1978)

· Diffie-Hellman (1976)
• ¿Como averiguar si un número es divisible por 7
o por 11?
• Si contamos 100 días a partir de hoy ¿en qué día
de la semana caerá?
• Dígitos de control de las cuentas bancarias, ISBN
de los libros...
• De pequeños, en la escuela, se nos enseñan varios tipos de
números: los naturales, enteros, racionales, reales, complejos…
Tienen propiedades muy similares: todos se pueden sumar,
restar, multiplicar y dividir. También todos ellos tienen una
cantidad infinita de elementos. Pero existen muchas más
construcciones que son de sumo de interés. Una parte muy
peculiar de las ciencias exactas trabaja lo que se denomina
aritmética modular.
• En el fondo, aunque no la hayamos estudiado, todos la
conocemos. Imaginemos unas matemáticas que sólo empleasen
un número limitado de números; 24, por ejemplo, desde el cero
hasta el 23. Si a este último elemento, el 23, le sumamos uno,
volvemos a tener un cero. Y si al cero le restamos uno, tenemos
23. Con este conjunto de números también podemos sumar,
resta y multiplicar, pero repito, no son un grupo ilimitado, sino
finito.
• Hemos visto, un sistema de 24 elementos, porque tales son las horas del día.
Pero podríamos hablar, por ejemplo, de siete. A los elementos de este conjunto
los podemos llamar 0, 1, 2, 3, 4, 5 y 6; o bien lunes, martes, miércoles… Si al día
dos le sumamos siete, volvemos a estar en el día dos. Y si le restamos tres,
obtenemos el día seis. Para ser más correctos, en este dominio no se habla de
igualdad, sino de congruencia. Decimos que dos días son congruentes módulo
siete si son el mismo día de la semana, aunque uno sea 21 de febrero y el otro
17 de marzo. De la misma forma, dos horas son congruentes módulo 24 si el
reloj nos muestra el mismo número, aunque estemos en días diferentes. Un
tipo de aritmética modular muy curioso es la módulo dos. Las clases de
congruencia que crea dividen a los números naturales en dos grupos: los pares
y los impares. Por supuesto, posee sus reglas aritméticas propias: dos pares
suman siempre par; un par y un impar suman par; el producto de dos pares es
par, etc. Se trata de una aritmética de dos elementos: par e impar.
• El módulo o resto de las divisiones de los números naturales por n da lugar a
las diferentes aritméticas modulares. Supongamos que queremos trabajar con
un módulo 365. Por simplificar un poco la idea, lo que debemos hacer es
efectuar las operaciones de forma habitual, tal y como estamos acostumbrados
a hacer con los números naturales, dividir luego por 365 y quedarnos con el
resto. El resultado es lo que buscábamos.
 Una introducción a la Matemática
• Modular
Cuando dividimos dos enteros tenemos una ecuación que se ve de
la siguiente forma:
• A - es el dividendo A/B=Q residuo R
• B - es el divisor
• Q - es el cociente
• R - es el residuo
• A veces, solo estamos interesados en cuánto es el residuo cuando dividimos
A entre B.

• Para estos casos hay un operador llamado el operador módulo (abreviado

como mod).
• Usando los mismos A, B, Q y R que arriba, tendríamos: A mod B=R
• Esto lo diríamos como A módulo B es congruente con R. Donde a B se le
conoce como el módulo.
• Por ejemplo:
• 13513 mod 5==2 residuo 33
• Un caso particular de la aritmética modular es la llamada aritmética
del reloj. Cuando a las 10 de la mañana se le agrega 5 horas se llega
a las 3 de la tarde, es decir “10 + 5 = 3”.
• También si a las 2 de la tarde se le quita 4 horas, el resultado es las
10, lo que equivale a decir que “2-4 = 10”.
• Esta aritmética del reloj se llama más generalmente aritmética
módulo 12 y se realiza dentro del conjunto Z = {0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11} cuyos elementos se llaman enteros módulo 12.
• En realidad cualquier número entero es equivalente a un entero
módulo 12 que se obtiene como el residuo (nunca negativo)de la
división entre 12.
• Por ejemplo “29 es equivalente a 5 módulo 12” y se escribe “29 =
5(mod12)”, porque al dividir 29 ÷ 12 da cociente 2 y residuo 5. Esto
también se expresa mod(29, 12)= 5.
• Escribimos 0 en la parte superior de un círculo y
continuando en sentido de las manecillas el reloj escribimos
enteros 1, 2, ... hasta uno menos que el módulo.

• Por ejemplo, un reloj con el 12 sustituido por 0 sería el

círculo para un módulo de 12
Para encontrar el resultado de A mod B
podemos seguir estos pasos:
1. Construye este reloj para el
tamaño B
2. Empieza en 0 y muévete alrededor
del reloj A pasos
3. Dondequiera que caigamos es
nuestra solución.

(Si el número es positivo, damos

un paso
negativoen damos
sentido de
un laspaso
manecillas del
en sentido
opuesto areloj, si es
las manecillas del reloj.)
 LA ARITMÉTICA DEL RELOJ

2=14=122 8=20=-4

Suma Resta Multiplicación

11+4=3 2-3=- 7·7=1

1=11
División 2·algo=5, no existe 5/2.

Notación:

a  b (12) Significa que a y b son la misma hora

a  b ( p) Lo mismo para un reloj con p (primo) números

 Ejemplos
• 8 mod 4=?
• Con un módulo de 4 hacemos un reloj con los
números 0, 1, 2, 3.
• Empezamos en 0 y nos movemos 8 números en
sentido de las manecillas del reloj una secuencia
de 1, 2, 3, 0, 1, 2, 3, 0.
•
Terminamos en el 0 así que 8 mod 4=0

• 7 mod 2=?
• Con un módulo de 2 hacemos un reloj con los
números 0, 1
• Empezamos en 0 y nos movemos a través de 7
números en sentido de las manecillas del reloj
• una secuencia de 1, 0, 1, 0, 1, 0, 1.
Terminamos en 1 así que 7 mod 2=1.
• −5 mod 3=?
• Con un módulo de 3 hacemos un reloj
con los números 0, 1, 2
• Empezamos en 0 y nos movemos a
través de 5 números en sentido opuesta
a las manecillas del reloj (5 es negativo)
una secuencia de 2, 1, 0, 2, 1.
• Terminamos en 1 así que −5 mod 3=1.
Aritmética (o del
modular reloj)
Resto al dividir por 2: 0 (par) ó 1 (impar).

+ 0 1 x 0 1
0 0 1 0 0 0
1 1 0 1 0 1

Se escribe 15 = 1 (mod 2) ó 26 = 0 (mod 2)

Aritmética (o del reloj)
modular
Resto al dividir por 3: 0 , 1 ó 2.

+ 0 1 2 x 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1

Se escribe por ejemplo 16 = 1 (mod 3)

Acertij
o
CADA AÑO, UN REY AFICIONADO A LAS MATEMÁTICAS,
RECIBE DE LOS 10 NOBLES QUE FORMAN SU CORTE UN
• SACO DE MONEDAS DE ORO. CADA MONEDA PESA 10
GRAMOS. UN AÑO, UN NOBLE DECIDE ESTAFAR AL REY
DÁNDOLE MONEDAS QUE PESAN 9 GRAMOS.

• EL ESPÍA DEL REY LE ADVIERTE QUE ALGUIEN LE ESTÁ

ENGAÑANDO. HACIENDO UNA SOLA PESADA EN UNA
BALANZA, EL REY DESCUBRE AL ESTAFADOR, ¿CÓMO LO HA
HECHO?
El rey pesó:

1 Moneda del Primer noble

2 Monedas del Segundo noble Hay en total 55
3 Monedas del Tercer noble monedas. Si fueran
.
. todas verdaderas
9 Monedas del Noveno noble
10 Monedas del Décimo noble
pesarían 550 gramos.

Si pesan 549, el estafador es el primer

noble, si pesan 548 el segundo…
 Congruencia
• Si ves una expresión como:
A≡B (mod m)
• Esto dice que A es congruente con B módulo m.

• Se dice que dos enteros A y B son congruentes módulo m

si la diferencia de A y B es divisible por m, y se emplea la
notación: A≡B (mod m).
• Esta definición equivale a decir que A y B dan el mismo
resto al ser divididos por m.
Ejempl
o
63 83 (mod 10)

63 10 83 10
60 6 80 8
03 03
NÚMEROS
CONGRUENTES
Características de los números
congruentes
 Propiedades
I. Si dos números son congruentes con un tercero son congruentes entre sí.
II. a ≡ 0 mod m quiere decir que a es múltiplo de m.
III. Si a ≡ b y c ≡ d; entonces a + c ≡ b + d; a – c ≡ b – d y ac ≡ bd (todas mod m). a ≡
IV. b mod m  na ≡ nb mod m. Es decir, podemos multiplicar sin problemas en
congruencias.
V. Si na ≡ nb mod m y n es primo con m; entonces a ≡ b mod m. Es decir, podemos
dividir sin problemas en congruencias por números primos con el que indica la
congruencia. Por ejemplo, 14 ≡ 4 mod 5  7 ≡ 2 mod 5 (por ser 2 primo con 5)
I. Sin embargo, si el número por el que dividimos no es primo con el que indica la congruencia la
propiedad anterior no es cierta. Por ejemplo, 14 ≡ 4 mod 10; pero sin embargo 7 y 2 no son
congruentes entre sí, módulo 10 (al no ser 2 primo con 10).
Pero existe otra propiedad que permite dividir en este caso:

vi. Si na ≡ nb mod m y d es el mcd(n, m); entonces a ≡ b mod (m/d):

Así, 14 ≡ 4 mod 10  7 ≡ 2 mod 5
• Otro ejemplo que puede ayudar a aclarar esta propiedad es el siguiente: 28 ≡ 8 mod 10 
7 ≡ 2 mod(10/2) = mod 5 (al ser el mcd(4,10) = 2). Otra forma de proceder, si hay problemas
con esta propiedad, es pasando a ecuaciones diofánticas y utilizando la propiedad v:
28 ≡ 8 mod 10  28 = 8 + 10y, que se puede simplificar entre 2, quedando: 14 = 4 + 5y 
14 ≡ 4 mod 5 y, por la propiedad v, entonces 7 ≡ 2 mod 5.

vii. Si a ≡ b mod m  an ≡ bn mod m. El recíproco no tiene por qué ser cierto.

• Por ejemplo: 72 ≡ 52 mod 3 y sin embargo 7 y 5 no son congruentes modulo3.

viii. Para calcular una potencia, an, módulo m, podemos poner un número
congruente con la base, a, pero no del exponente.
 PROPIEDADES DE LOS NUMEROS CONGRUENTES.

Sean a, b y m nu´meros enteros, se tiene que:

a ≡ b (mod m) ⇐⇒ a ≡ b (mod − m)

a ≡b (mod m) ⇐⇒ m|(a − b)

La congruencia a ≡b (mod 1) siempre es cierta.

Sean a, b, c, d y m nu´meros enteros, se tiene

que:
a ≡ b (mod m) =⇒ a · c ≡ b · c (mod m)

a ≡b (mod m) y c ≡d (mod m) =⇒ a + c ≡b + d (mod m) y

a − c ≡b − d (mod m)

a ≡b (mod m) y c ≡d (mod m) =⇒ a · c ≡b · d (mod m)

a ≡b (mod m) =⇒ ak ≡bk (mod m) y k > 0

a ≡b (mod m) y d|m =⇒ a ≡b (mod d)

m
a · c ≡ b · c (mod m) y d = mcd(c, m) =⇒ a ≡ b (mod )
d

Si mcd(m, n) = 1, a ≡ b (mod m) y a ≡ b (mod n) ⇐⇒ a ≡ b (mod m · n)

 Enter modul n
os o

Z2 = {0, 1}

Z5 = {0, 1, 2, 3, 4}
 Suma y resta modular
• Exploremos la propiedad de la suma de la aritmética modular:
(A + B) mod C = (A mod C + B mod C) mod C
• Ejemplo:

• Sea A=14, B=17, C=5

• Verifiquemos que: (A + B) mod C = (A mod C + B mod C) mod C
LI = Lado Izquierdo de la ecuación
LD = Lado Derecho de la ecuación
• LI = (A + B) mod C
LI = (14 + 17) mod 5
LI = 31 mod 5
LI = 1

• LD = (A mod C + B mod C) mod C

LD = (14 mod 5 + 17 mod 5) mod 5
LD = (4 + 2) mod 5
LD = 1

• LI = LD = 1
 Demostración de la Suma
• Modular
Probaremos que (A + B) mod C = (A mod C + B mod C) mod C
• Debemos mostrar que LI=LD

Podemos escribir A y B como:

A = C * Q1 + R1 donde 0 ≤ R1 < C y Q1 son enteros. A mod C = R1
B = C * Q2 + R2 donde 0 ≤ R2 < C y Q2 son enteros. B mod C = R2
• (A + B) = C * (Q1 + Q2) + R1+R2
LI = (A + B) mod C
LI = (C * (Q1 + Q2) + R1+ R2) mod C
Podemos eliminar los múltiplos de C cuando tomamos mod C
• LI = (R1 + R2) mod C

LD = (A mod C + B mod C) mod C

• LD = (R1 + R2) mod C

LI=LD= (R1 + R2) mod C

• Observa la figura siguiente. Si queremos calcular (12+9) mod7 podemos
fácilmente ir alrededor del círculo modular por una secuencia de 12+9 pasos en
sentido de las manecillas del reloj (como se muestra en el círculo inferior
izquierdo).
• Podemos tomar un atajo si observamos que cada 7 pasos
terminamos en la misma posición en el círculo modular. Estas
vueltas completas alrededor del círculo modular no contribuyen a
nuestra posición final. Podemos ignorar estas vueltas completas
alrededor del círculo calculando cada número mod 7 (como se
muestra en los dos círculos modulares superiores). Esto nos dará
el número de pasos en sentido de las manecillas del reloj, relativos
a 0, que contribuyen a cada una de las posiciones finales
alrededor del círculo modular.
• Ahora, solo tenemos que ir alrededor del círculo en sentido de las
manecillas del reloj el número total de pasos que contribuyen a la
posición final de cada número (como se muestra en al círculo
modular inferior derecho). Este método aplica, en general, a
cualesquiera dos enteros y cualquier círculo modular.
• Resta Modular
• Una prueba muy similar se hace para la resta modular
(A - B) mod C = (A mod C - B mod C) mod C
 ADICIÓN, SUSTRACCIÓN Y
MULTIPLICACIÓN
•
El número 12 (en el calculo de horas) es sólo un ejemplo
separa
realiza en el conjunto
presentar Z= la
el concepto de {0,aritmética
1, 2, ..., (N - 1)}, para
módulo N que
cualquier entero N>1. A N se le llama “el módulo”.
• Provisto este conjunto de las operaciones de suma, resta y
multiplicación se convierte en el sistema ZN. Suma y
multiplicación se hacen como aprendimos en la escuela,
pero el resultado hay que tomarlo módulo N. Por ejemplo
en Z13 el producto 8 × 11 = 10.
• Sólo recuerda que estaremos haciendo operaciones en
un sistema diferente. Los “números” del sistema en
realidad no son números en el sentido corriente. Son
elementos de un sistema y solo nos prestamos los
numerales 0, 1, 2, 3, ... para entendernos. No hay
números negativos, o mejor, todos los números en ZN son
a la vez positivos y negativos. En realidad todo número en
este sistema es siempre el negativo de otro.
• En a + b =0, a es el negativo de b y b es el negativo de a.
Por ejemplo, para efectuar 3 8, en Z12, a 3 le sumamos el
negativo de 8 que es 4. Por tanto, 3 - 8=3+(-8)=3+4=7.
Tablas de multiplicar: Z6 , Z7 :

Z6 0 1 2 3 4 5
0 0 0 0 0 0 0

1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

Z7 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
• División:
• Si a × b = 1, entonces b es el recíproco o inverso de a y también a es el inverso
de b.
• Por ejemplo, inverso de a = 4 es b =0.25 porque 4 × 0.25 = 1. El inverso del
entero 4 es el decimal (racional) 0.25. Esta es una anomalía que no queremos en
ZN . Quisiéramos que en ZN los inversos de los elementos de ZN caigan en ZN,
como sucede con los negativos. Pero esto no siempre sucede.

• Por ejemplo en Z9 = {0, ..., 8}, ningún elemento es inverso de 3, porque ningún
número multiplicado por 3 dará 1. Tendría que dar 10, para que al tomarlo
módulo 9, dé 1, y ese entero no existe. Sin embargo 2 × 5 = 1. lo que revela que
el 5 es el inverso del 2 y, simétricamente, el 2 es el inverso de 5. Podemos
afirmar que en Z9 , el 2 es invertible, es decir tiene inverso y su inverso es 2-1 =
5. Observa la notación: el inverso de a es a-1 . Contar con inversos es importante
porque nos permiten hacer divisiones y resolver ecuaciones. En efecto, la
división a/b la n tendemos como a × b-1, es decir multiplicamos a por el inverso
del divisor b.
Unidades Z
de
n
Pequeño teorema de
Fermat
Ejempl
o
Función de
Euler
Propiedades de función de
Euler
Teorema de
Euler
Congruencias
lineales
Propiedades de congruencias
lineales
Calculo de una solución
particular de
ax ≡ b (mod n)
Propiedad
es
• Ecuaciones.
• Recuerda que una ecuación es una proposición abierta (puede
ser cierta o falsa) en la que hay una incógnita (o desconocida) y
que clama por ser resuelta. Es decir, debe hallarse el valor o los
valores de la incógnita que hagan cierta (satisfagan) la ecuación.
Por ejemplo, en los números enteros, la ecuación 2x + 3 = 11
tiene la solución x = 4, porque 2×4+3 es en efecto 11, y, muy
importante, 4 es un entero. Es decir esa ecuación la resolvemos
dentro de los números enteros.
• Las técnicas para resolver ecuaciones en los números regulares,
se usan también en ZN. Sólo se requiere tener cuidado de que las
operaciones se hagan en ZN. Por ejemplo, para resolver x +7 = 3 en
Z27, restamos 7 a ambos lados y obtenemos x + 7 – 7 = 3 - 7 y de
aquí x = 3 - 7= - 4 = 23(mod 27). La solución es entonces 23.
• Del mismo modo, resolver la ecuación 2 x =7 en Z9 , resulta fácil. Nos
aseguramos que 2 sea invertible. Ahora multiplicamos ambos miembros por el
inverso de 2 y obtenemos;

• de donde
5 · 2x = 5 × 7

• lo que da x =8
• La solution de 2x =7, en Z9 , es entonces x = 8. Puedes verificar que 2 ×8=
7(mod 9)
• Elementos invertibles. Elementos de Z9 que son
invertibles son 1,2, 4, 5, 7 y 8. El resto, 0, 3 y 6 no
son invertibles. Lo que es claramente común a
estos últimos es que comparten factores con el
modulo 9. Todos tienen el factor 3 y 3 es divisor del
módulo.
• Los invertibles, no comparten factores o divisores
con el módulo. Es decir que entre un elemento
invertible a y el módulo N el máximo común divisor,
mcd(a,N), es 1. Y esa es la condición necesaria y
suficiente para que un elemento de ZN sea
invertible
 Ecuaciones diofantinas
• Una ecuación con coeficientes enteros en una
o mas incógnitas es llamada diofántina (en
honor a Diofanto quien fue el primero en
estudiar este tipo de ecuaciones). En particular,
nos interesa examinar la ecuación diofántina,
llamada ecuación diofántina lineal en dos
Diofantus, nació alrededor
incógnitas del año 200 y falleció
alrededor del año 284. Su
libro “Aritmética” inspiro a
Fermat en sus
investigaciones.

• donde a , b y c son enteros dados, con a y b no

simultáneamente nulos. Un par de números x0,
y0 es una solución de la ecuación si y sólo si
ax0+ by0= c .
Ejempl
o
Ejemplo
Un comerciante gastó cincuenta y seis mil soles en telas, unas a cuatro mil
ciento diez, otras a tres mil novecientos setenta ¿Cuántos de cada cual ha
comprado?
Solución.
Sean x e y el número de telas a S/ 4.110 y 4 3.970, respectivamente.
Entonces, tenemos la ecuación diofántina 4110x + 3970y = 56000, esto es,
411x + 397y = 5600.
Nótese que 411 - 397 = 14.
Luego (probando por tanteo) podemos ver que
411 · 400 - 397 · 400 = 164400 – 158800= 5600 .
Por lo tanto, la ecuación diofántina debe satisfacer z = 400 - 397t
y = -400 + 411t , para algún entero t .
Para tener x e y ambos positivos, se necesita que t = 1 . Así x = 3 e y = 11 .
De modo que el comerciante compró 3 telas a S/ 4110 cada una y 11 telas a
S/ 3970 cada una.
HISTORI
A
así porque ya se empleaba en la
civilización china en el siglo I a.C. en casos muy
• Llamado
concretos, como era para calcular fechas de
sucesión ligadas a periodos de acontecimientos
astronómicos.
Leyenda: Un emperador chino solía contar sus soldados a través del
siguiente método.
Todas las tropas deben formar grupos de 3 y debían reportar el número de
soldados que no eran capaces de hacerlo.

• Repetir el procedimiento con grupos de 5.

• Repetir el procedimiento con grupos de 7.
• Etc.

Al final del día si el número de soldados es suficientemente grande, el

emperador podía encontrar el número de sus soldados mediante el uso de
una ingeniosa fórmula.
Teorema del Residuo Chino
mod 3:

N mod 3 = 1
mod 5:

N mod 5 = 2
mod 7:

N mod 7 = 2
¿Cómo podríamos deducir la fórmula secreta?
Para cualquier x, a, b, y c que satisfagan
x  a (mod 3)
x  b x (mod 5)
 c (mod 7)

El teorema del residuo chino dice que existe

suficiente información para determinar de manera unívoca x
módulo 3· 5· 7.
Prueba: se basa en encontrar un algoritmo capaz de
encontrar x, es decir, la fórmula secreta.
O de otra manera:
35*y1 = 1mod(3), como 35  3 y son coprimos podemos simplificar tomando residuo de 35/3, es decir
2*y1 = 1mod(3), ahora para encontrar inverso hay que preguntar “que numero tenemos que multiplicar
2 para que el residuo de mod(3) nos de 1. En este caso si (2*2)mod(3) = 1, entonces y 1= 2
21*y2 = 1mod(5)  1*y2 = 1mod(5), y2 = 1
15*y3 = 1mod(7)  1*y3 = 1mod(7), y3 = 1
Problema de compra de tres artículos con
diferentes precios, cantidad limitada de monto
monetario y de las cantidad de artículos a comprar

Precios

Cantidades
Si x es mayor que 10 no nos
alcanzaría 1000 unidades
monetarias , si exactamente 10 –
no podemos comprar otros dos
artículos, entones x debe ser
menor que 10
Pero sabemos que
20*y1 = 1mod(3) ,  2*y1 = 1mod(3), 2*2mod(3)=1, y1= 2
15*y2 = 1mod(4),  3*y2 = 1mod(4), 3*3mod(4)=1, y2= 3
12*y3 = 1mod(5),  2*y3 = 1mod(5), 2*3mod(5)=1, y3 = 3
Sistemas de congruencias
lineales
Ejempl
o

3*4(mod11)=1
419mod(8)=3
419mod(5)=4
419mod(11)=1
91mod(8)=3
91mod(5)=1
91mod(11)=3
 Ejempl
o

55mod(8) = 7,  7*d1=1*mod(8), que numero hay que multiplicar 7 para que residuo de 8
nos da 1, 7*7mod(8)=1, es decir d1=7
88mod(5) = 3,  3*d2=1*mod(5), 3*2mod(5)=1; d2 = 2.
40mod(11) = 7,  7*d3=1*mod(11), 3*8mod(11)=1; d3 = 8.
Método de solución de
sistemas de
congruencias lineales
 Siete ladrones tratan de repartir, PROBLEM
entre ellos y a partes iguales, un botín A
de lingotes de oro.
Desafortunadamente, sobran seis
lingotes y en la pelea que se desata
muere uno de ellos. Como al hacer de
nuevo el reparto sobran dos lingotes,
vuelven a pelear y muere otro. En el
siguiente reparto vuelve a sobrar una
barra y sólo después de que muera
otro es posible repartirlas por igual.
¿Cuál es el mínimo número de barras
para que esto ocurra?
 PROBLEM
A
• Una banda de 13 piratas
encontró cierto número de
monedas de oro. Al
distribuirlas equitativamente
les sobraron 8 monedas.
Debido a una fiebre
murieron 2 de los piratas y al Por peleas entre ellos
hacer un nuevo reparto des murieron 3 más y en último
monedas, les sobraron 3. reparto le sobraron 5
monedas. Hallar el menor
número de monedas que
encontraron.
SOLUCIÓN

• Representemos por x el número de monedas

encontradas. Tenemos el sistema:
 ISBN Standa BookNumber
r )
(International

Hasta 2007, el ISBN

constaba de 10 dígitos
divididos en 4 partes de
longitud variable: país,
editor, título y código de
control.
Número de control del ISBN

Ejemplo: 0 13 041717

(0 × 1) + (1 × 2) + (3 × 3) + (0 × 4) + (4 × 5)+ (1 × 6)
+ (7 × 7) + (1 × 8) + (7 × 9) = 157 =
= D (mod 11)

Si D=0,1…9 se pone ese número. Si D=10 se pone

una X. (Por eso, aproximadamente 1 de cada 11
libros acaba en X).

En el ejemplo, 11 x 14 = 154, luego D=3.

Ejempl
o
• Solución
• Empezamos dividiendo 3120 por 270
• Si despejamos 120 de la ecuación

• Al sustituir en la anterior obtenemos

• Analógicamente despejamos 150, obtenemos

Ejercici
o
Aplicaciones de la aritmética
modular
• Se aplica en teoría de números, álgebra abstracta,
criptografía, y en artes visuales y musicales.
Aplicación en
criptografía