República Bolivariana de Venezuela.

Universidad del Zulia.

Facultad Experimental de Ciencias.
División de Estudios Básicos Sectoriales.
Departamento de Matemática.

Aritmética Modular.
Trabajo de ascenso presentado por la Profesora Neida Murcia para optar a
la categoría de Profesor Asistente.

^|$*anKf)¿V

Sí "¡'i
Autor: Licda. Neida Murcia.
.#/

Maracaibo, Marzo 2011.

índice general

Acta de Evaluación. n

Resumen. ni

Abstract. rv

Introducción. v

1. Aritmética Modular. 1

1.1. Algoritmo de Euclides y Divisibilidad 1

1.2. Congruencias 7

1.3. Restos y Criterios de Divisibilidad 12

1.4. Teorema de Euler- Fennat 17

1.5. Ecuaciones Diofanticas Lineales 23

1.6. Sistema de Ecuaciones Lineales 30

Ejercicios Propuestos. 36

Bibliografía. 43
Acta de Evaluación.

Este jurado aprueba el Trabajo de Ascenso titulado Aritmética Modular, presentado

por la Profesora Licda. Neida Elena Murcia Briceno, portadora de la C.I. 15.407.238, ante el

consejo de la Facultad Experimental de Ciencias, en cumplimiento con los requisitos señalados

en el artículo 19 del Reglamanto del Personal Docente y de Investigación de la Universidad

del Zulia, para optar a la categoría de Profesor Asistente.

Jurado

Jurado

Jurado

n
Murcia Briceno Neida Elena. "ARITMÉTICA MODULAR". Trabajo de Ascenso para
optar a la categoría de profesor Asistente. Universidad del Zulia. Facultad Experimental de
Ciencias. Departamento de Matemática. Maracaibo, Venezuela 2011. 44p.

Resumen.

En este trabajo se utiliza la Aritmética Modular en dos sentidos diferentes: en primer

lugar con el sentido de identidad matemática, para encontrar restos de una división de
números muy grandes empleando el Teorema de Euler y el Pequeño Teorema de Fermat, asi
como también estudiar criterios de divisibilidad y deducir sí un número dado es divisible o no
por un entero específico; y en segundo lugar como un sentido de ecuación, donde aparecen
una o más incógnitas, y nos preguntamos si una ecuación de congruencia o sistema de
ecuaciones tiene solución y en caso afirmativo, mostrar explícitamente todas sus soluciones.

Palabras Claves: Resto, Divisibilidad, Congruencias.

Correo Electrónico: neidamurcia@[Link].

m
Murcia Briceno Neida Elena. "ARITMÉTICA MODULAR". Trabajo de Ascenso para
optar a la categoría de profesor Asistente. Universidad del Zulia. Facultad Experimental de
Ciencias. Departamento de Matemática. Maracaibo, Venezuela2011. 44p.

Abstract.

In this work we use modular arithmetic in two difrerent ways: first with the sense of
mathematicai identity, to find traces of a división of very large numbers using Euler's
Theorem and Fermat's Little Theorem, and also consider criteria divisíbility and deduce
whether a given number is divisible by an integer or not specifíc, and secondly as a sense of
equation, which shows one or more unknowns, and we wonder if a congruence equation or
system of equations has a solution and if so, to show explicitly all solutions.

Key Words: Rest, Divisibility, Congruence.

E- mail: neidamurcia@[Link].

IV
Introducción.

La congruencia es un término usado en Teoría de Números, para designar que dos números

enteros a y b tienen el mismo resto al dividirlos por un número natural n, llamado módulo;
esto se expresa utilizando la notación matemática a = b(modn) y se lee "a es congruente

con b módulo n".

La Aritmética Modular, estudiada sistemáticamente en primer lugar por Cari Friedrich

Gauss al final del Siglo XVIII en su monumental obra Disquisitiones Arithmeticae, es un sis
tema aritmético para clases de equivalencia de números enteros llamadas clases de congruen

cia y se utiliza para simplificar problemas teóricos - numéricos sustituyendo cada entero por el

resto de su división. Esto produce el efecto de renovar al conjunto infinito Z por un conjunto

finito Z„ que contiene n elementos y hereda muchas de sus propiedades como la suma, resta

y multiplicación.

La teoría de congruencias nos ayuda a trabajar con números muy grandes, al calcular los

restos de una división de una manera rápida y sencilla. En este texto, se hace un recorrido

por sus aspectos teóricos más interesantes comenzando con los fundamentos básicos de los

números enteros como son: el algoritmo de ia división de Euclides; la noción de divisibilidad;

el cálculo de máximo común divisor entre dos enteros; la noción de número primo y el teorema

fundamental de la aritmética.

Se introduce la definición de congruencia como una relación de equivalencia y se estudian

sus propiedades y operaciones de suma y producto, junto con sus clases de equivalencia o

clases de restos módulo n, formadas por cada entero y sus congruentes.

Se define el anillo de enteros residuales Zn y se calculan sus elementos inversibles, esto

v
Capítulo 0. Introducción.

con el propósito de estudiar la función ip(n) de Euler y los teoremas de Euler y Fermat;
teoremas clásicos en la teoría de números cuyas pruebas están basadas en congruencias y

que son de gran utilidad en la Aritmética Modular, Teoría de Números, Teoría de Grupos y

Criptografía.

También se usará la teoría de la Aritmética Modular para determinar las soluciones (si

existen) de ecuaciones del tipo ax + by —c con a, b y c enteros, así como también para la
resolución de sistemas de ecuaciones, junto con una serie de problemas interesantes, en donde

se aplica esta teoría.

Al final del texto, se incluye un conjunto variado y equilibrado de ejercicios y problemas

teóricos - prácticos, que ilustran el material tratado y brindan al lector la posibilidad de

poner a prueba la comprensión del mismo.

Cabe destacar, que este trabajo tiene una naturaleza básica elemental y proporciona una

introducción a la Teoría de Números, adecuada para cursos iniciales de la Licenciatura en

Matemática, en particular para el curso de Algebra Abstracta; poniendo de manifiesto, que

en la Teoría de Números surgen gran cantidad de problemas, muchos de los cuales pueden

ser abordados, en principio, sin necesitar grandes requisitos.

 Aritmética Modular.

1.1. Algoritmo de Euclides y Divisibilidad.

El conjunto de números más conocido es el conjunto de números enteros Z totalmente

ordenado por la relación <; por tal motivo, se hará un estudio de las propiedades en Z que se

utilizarán a menudo en los temas que siguen. El lector debe estar familiarizado con muchas

de estas propiedades y con el proceso de Inducción Matemática.

La suposición básica que se hace acerca de los números enteros es el Principio de Buena

Ordenación: Todo conjunto no vacío de enteros positivos, tiene un primer o mínimo elemento.
Formalmente:

Teorema 1.1.1. (Principio de Buena Ordenacción). Todo conjunto no vacio S de

enteros positivos tiene un elemento mínimo; esto es, 3 n e S (único) tal que n < x}Vx G S.

Este principio sen-irá como fundamento en el estudio que vamos a realizar, la prueba se

realiza aplicando un principio de inducción Matemática y puede ser consultada en diferentes

textos como por ejemplo Oneto.(2000). La primera aplicación de este principio, se hará en la
demostración del siguiente:

Teorema 1.1.2. (Algoritmo de Euclides). Dados dos enteros m yn con n > 0 y m > 0,
existen enteros únicos q y r ambos > 0 tales que n = rnq + r con 0 < r < m.
Capítulo 1. Aritmética Modular.

Demostración. Se probará la existencia y unicidad de tales enteros q y r.

Para la existencia considerar el conjunto S —{n —mx : x € Nu{0}}n(NU{0}). Como N

es un conjunto bien ordenado, también lo es N U {0}, y como 5/0 posee mínimo elemento
r. Luego, r G NU{0} y existe un q € NU{0} tal que r —n —mq con r <m. Si se tuviese que
r >m resultaría que r —m —n —m(q + 1) £ S contradiciendo el hecho que r es el mínimo

elemento.

Además, si n — 0, tomar q — r = 0; si n < in, tomar nuevamente q = 0yr = nysi

n = m basta con tomar q — 1 y r = 0. Suponer entonces que n > m y así n —mENy

0 <n —m <n. Por inducción en r¿, podemos tomar como hipótesis inductiva que el teorema

es válido para n—m, es decir, que existen enteros <?i, r > 0 y r < m tales que n—m —q^m+r.
De esta manera, n —m + q\m + r — (1 + qi)m + r; de donde, tomando q — (1 4- qi), se
comprueba la existencia de q y r.

Para la unicidad, suponer que existen q\, q%, r\, r% tales que:

n — q\m + ru 0 < ri < m

n = q2m -I- r2, 0 <r2 <m

Si ri < r2 ^ 0 < r2 —ri = (gi —q2)m < m, pero esto no es posible, de donde r\ > r2.

Similarmente, si r2 < Ti =4- 0 < r\ —r2 — (32 —9i)"í < "i, que no es posible, de donde
r2 > f]. De esta manera se obtiene que n = r2-

Ahora bien, n = <n?n + r y n — qim -\- r; luego restando ambas igualdades se obtiene:

0 = (<2i - Q2)m ^qi-q2 = 0=>gi = g2- •

A estos números enteros q y r se le llaman cociente y residuo (respectivamente) de la

división de n por m. El algoritmo de Euclides proporciona una multitud de consecuencias,

especialmente para la noción de divisibilidad.

Definición 1.1.3. Dados dos números enteros ny m con n / 0 , se dice que n divide amo

que m es múltiplo de n (denotado por n \ m ), si existe un entero q tal que m ~ nq. En este
caso, se dice que ny q son factores de m. Luego por ejemplo 2 j 4, 5 [ 0 y 2 es un factor de 6.
Capítulo 1. Aritmética Modular.

Proposición 1.1.4. Sean a,b y c enteros. Se verifican las siguientes propiedades:

. 1 ¡ a y a \ a.

. Si a | b y b \ c, entonces a \ c.
. Si a\b entonces, a j kb para cualquier entero k.

. Si a | b y a \ c, entonces a\br + cs para cualquier par de enteros r, s.

. Sia\b y b \a, entonces a = ±b.
. Sia\b y a,b> 0 entonces a<b.

Demostración. La prueba se deja como ejercicio para el lector. •

Definición 1.1.5. Sean m,n dos enteros donde por lo menos uno es no nulo. Un entero

d> 0 es Máximo común Divisor demyn denotado por d = mcd(m,n) sil:

. d | m y d {n.
. Si e\mye\n=>e\d.

Observación 1.1.6. El máximo común divisor se puede definir también como el máximo

elemento del conjunto {d G Z : d | n y d j m}. Dado que 1 | n y 1 | m, el conjunto de

divisores comunes de fi y ít?, es no vacío. Además, si d \ n se tiene que |rf| < |ti|, de donde
el conjunto de divisores comunes es finito y tiene sentido de hablar de un máximo elemento.

De esta manera, siempre existe el máximo común divisor entre dos enteros nym, además:

Proposición 1.1.7. Sid y d* son máximos comunes divisores de los enteros nym, entonces

d = d*.

Demostración. Si d* es un máximo común divisor de n y m, por la definición anterior se

tiene que d* \ n, d* \ m y además d* \ d. Similarmente se obtiene que d \ d*, luego d —±d* y

como ambos deben ser positivos, d~ d*. •

Lema 1.1.8. Dados dos enteros m,fn no nulos, tales quen —mq+r conq,r EZyO <r <m

entonces, el mcd(n, m) —mcd(m, r) donde r es el resto de la división de n por m.

Demostración. Sean d = mcd(n,m) y d* =mcd(m,n —mq), por ver que d —d*. Comod | n
y d | m, d | n —mq. Luego d \ m y d \ n —mq, de donde d < d* ya que dl es el más grande con
Capítulo 1. Aritmética Modular.

esa propiedad. Recíprocamente, como d* \my d* \ n—mq se tiene que d* \ (n—mq)+mq —n.
Luego d* | n y d* \ m, de donde d* < d. Por lo tanto d —d'. D

Este resultado permite dar un algoritmo para calcular el máximo común divisor entre dos

números, además es fundamental para el siguiente:

Teorema 1.1.9. (Identidad de Bézout). Dados dos enteros nym ambos / 0; existen
enteros r yt tales que mcd(n, m) = nr + mt.

Demostración. Utilizando el algoritmo de Euclides, se pueden calcular las siguientes divi

siones sucesivas:

n — mqi +r\=$- r\=n —m.q\ 0 <r¡ <m

m = rxq2 + r2 => r2 = m —r1q1 0 < r2 < ri

ri = r2q3 + r3 =>• r3 = ri —r2q3 0 <r3<r2

r2 = r3q4 + rA =$• rA = r2 - r3qA 0 < r4 < r3

r-j-2 = rj-iQj +rj=>rj = r5.2 - r,--^ 0 < rá < r^

O-i =OSí+i-

Luego por el lema anterior se tiene que mcd{n,m) = mcdim^]) — mcef(ri,r2) —

mcd(r2,r3) = ••• = mcd(rj_2,rj-2) = mcd(rj-2,rj-i) = mcd(rj-i,rj) = mcd(rj,0) = r,-
que es el último residuo no nulo en la divisiones sucesivas. Además, sustituyendo de abajo
hacia arriba so obtiene:

ri = rj-20)+ri-i(-qj)
= rí-_2(l-qí-i)+rJ-_a{-gí)

hasta obtener una expresión del tipo r¿ = rn + mt con r y t enteros formados por una suma
algebraica de producto de los qj y r¿ respectivamente. •
Capítulo 1. Aritmética Modular.

Ejemplo 1.1.10. Calculemos el mcd(1750,429). Haciendo las divisiones sucesivas obtene

mos:

1750 -429-4 + 34

429 -34-12 + 21

34-21-1 + 13

21 = 13 -1 + 8

13 = 8 • 1 + 5

8-5-1 + 3

5-3-1 + 2

3-2-1 + 1

2-1-2 + 0

así, mcd(1750,429) —1 que es el último resto no nulo en esas divisiones sucesivas; además,

despejando de abajo hacia arriba y sustituyendo los restos correspondientes se obtiene:

1 = 3 - 2 = 3 - (5 - 3) = 2 • (3) - 5 = 2 - (8 - 5) - 5 = 2 •8 - 3 • (5) = 2 • (8) - 3 • (13 - 8) =

5-(8)-13-(3) = 5-(21-13)-13-{3) = 5-(21)-8-(13) - 5-(21)-8-(34-21) = 13-(21)-8-(34) =
13 • (429 - 34• 12) - 8 • (34) = 13 • (429) - 164 • (34) - 13 - (429) - 164 • (1750 - 429 -4) =
669-(429)+ 1750-(-164).

Por tanto, el mcd(1750,429) - 1750(-164) + 429(669) - 1.

Definición 1.1.11. Un entero p > 1 se dice primo, si p —mn con nym enteros positivos,

entonces n —1 ó m —1; esto es, los únicos divisores positivos de p son 1 y el mismo p. En

caso contrario p se dice compuesto. Por ejemplo, los enteros 2,3, 5,7,11,13 son primos y los

enteros 6,12,15,21,34 son compuestos.

Definición 1.1.12. Dos enteros no nulos ny m, se dicen coprimos o primos relativos, si el

máximo común divisor entre ellos es 1.

Notar que, por la Identidad de Bezout, se tiene como consecuencia inmediata el siguiente:

Teorema 1.1.13. Dos enteros nym son coprimos o primos relativos si, y sólo si, existen

enteros r y t tales que 1 —nr + mt.

Capítulo 1. Aritmética Modular. 6

Proposición 1.1.14. Seap un número primo y seann ym enteros no nulos tales quep \ mn;
entonces p j n ó p \ m.

Demostración. Suponer que p \ m, entonces el máximo común divisor de p y m es 1 y por lo

tanto existen enteros r y s tales que 1 —pr + ms =¿- n —npr+ nms, pero p \ nm ^nm = pk
para algún entero k; de donde, n —(nr + rk)p =>• p \ n. Similarmente, suponiendo que p\n
se llega a la conclusión que p\m. •

Teorema 1.1.15. (Fundamental de la Aritmética). Todo número entero n > 2 puede

ser expresado como un producto de números primos no necesariamente distintos.

Demostración. Para la existencia, sea 5 el conjunto de los enteros mayores o iguales que 2

que no pueden ser expresados como producto de primos y supongamos que 5/0; por el

principio de buena ordenación, 5 tiene un mínimo elemento k, donde A: es un entero no primo

que puede ser expresado de la forma k —de con dy e enteros mayores que 1. Pero dy e son

enteros más pequeños que k, entonces se escriben como producto de primos: d —pi •p2... pT

y e — ?i - q2 - - - qs- Por lo tanto, k — de = pi - p2 • • -pr • <?i • 32 - - - qs en contradicción con lo

supuesto. Luego 5 —0.

Para la unicidad, suponer que n se escribe de dos formas distintas: n — pi •p2... pT y

n = q¡_- q2...qs; luego p\ \ q\ • q2... qs =¥ p\ j q¡ para algún i. Sin pérdida de generalidad, se

puede suponer que i —1, entonces <ji —p\k para algún entero k y como q± es primo, k —1 y

así qi —pi obteniendo que p2 •p% ... pr — q2 • q3 ... qs. Procediendo de esa manera en forma

inductiva, se concluye que r ~ s y p¡ —<&, para todo i. •

Este resultado es muy importante, ya que a partir de él se pueden describir los números

enteros de una manera precisa y bien definida, esto es, si n es un entero mayor que 1, o

bien es primo o es producto de números primos. De ello se esperaría que deben existir una

infinidad de primos. Esta teoría se remonta hasta Euclides, y el argumento que se dará en el

siguiente teorema se bebe a él.

Teorema 1.1.16. Existe un número infinito de primos.

Capítulo 1. Aritmética Modular.

Demostración. Suponer lo contrario, que existen un número finito de primos Pi,p2, -•- ,Pk y

considerar el entero q = l+Pi-p2-•-Pk- Como q > p;, V¿ —1, 2, - - - ,k; q no puede ser primo;

además, como p¿ \ q ya que se obtiene un residuo de 1 al dividir q entre p¿, q no es divisible

por ninguno de los p{. De esta manera, q no es primo ni es divisible por ningún primo, en

contradicción con el teorema anterior. Por tanto, existe un número infinito de primos. D

1.2. Congruencias.

Las congruencias permiten clasificar a los números enteros en clases de equivalencia, es

decir, en conjuntos formados por cada número entero y todos sus congruentes. En este caso

se llaman clases de restos o residuales, porque cada clase se puede representar por el resto

que resulta al dividir cualquier entero entre un mismo número que llamaremos módulo.

Definición 1.2.1. Sea 5 im conjunto no vacío. Una relación ~ sobre 5 es una relación de

equivalencia sobre 5 si se cumplen las propiedades:

. Reflexiva: x ~ x, Va: G 5.

. Simétrica: Si x ~ y =* y ~ x, Va;, y G 5.

. Transitiva: S\x~yyy~z=$-x~z, Ve, y,z G 5.

Definición 1.2.2. Sea ~ una relación de equivalencia sobre un conjunto S y sea x un

elemento cualquiera de S. El conjunto x —{y G S : y ~ x} se llama la clase de equivalencia

de x. El conjunto de clases de equivalencia, se llama conjunto cociente y se denota por 5/ ~.

Definición 1.2.3. Sea n un entero mayor que 1 y sean x, y G Z; se dice que x es congruente

con y módulo n denotado por x = y(modn) si n | x —y; esto es, existe un entero q tal que
x —y —nq. Por ejemplo, 13 = 8(mod 5); 10 = 4(mod 3) y 17 = 3(mod 7).

Proposición 1.2.4. La relación x = y{modn), es una relación de equivalencia.

Demostración. La relación es claramente reflexiva, dado que n\x —x = 0 =^ x = x(mod n).

También es simétrica, puesto que si x = y(modn), por definición n\x~y^-x —y + nk

para algún k € Z; luego y —x + n(—k) de donde n \ y —x =$• y —x(mod n).
Capítulo 1. Aritmética Modular. 8

Por último, la relación es transitiva; si x = y(mod n) y y = z(modn) entonces, x —y+nki,

y = Z-Vnk2 => x —2 + (fci. + k2)n, de donde se obtiene que a; —z(modn). D

Proposición 1.2.5. Sean un entero positivo y sean a,b,c,d G Z; entonces se verifican las

siguientes propiedades:

. a = b(modn) => —a = —b(modn).

. a = b(mod n) y c = d(mod n)=^a + c = 6 + d(mod n). Compatibilidad con la suma.
. a —b(mod n) y c = d(modn) =í> a •c = b- d(mod n). Compatibilidad con el producto.
. a = b(modn) =^ am = bm{modn), con m entero positivo.
, oh —ac(modn) y m,cd(a, n) —1 => b = c{mod n). Ley de cancelación de congruencias.

Demostración. Surgen aplicando la definición de congruencias y quedan a cargo del lector.

Ahora, para todo x G Z, y n € Z, con n > 1, la clase de equivalencia de a; está definida

por: a: —{y G Z : y = x(modn)} = {x+nk,k GZ}. Así, se pueden considerar todas las clases
de equivalencia de los números enteros módulo tí, formadas por el resto de la divisón por n;

por tanto, hay n clases distintas de equivalencia {0,1, 2,••-n —1} que forman el conjunto
cociente Z/ = que notaremos por Zn y en él, se definen dos operaciones de suma y producto

de la siguiente manera:

Definición 1.2.6. En el conjunto Z„ se definen la suma y multiplicación de dos clases de

equivalencia x y y módulo n:

+ : Z„ x Z„ —* Z„ -:Z„xZ„ —• Z„

fav)—>~x~+y (x,y)—*x^y

Donde las operaciones x + y y x • y son la adición y multiplicación ordinarias en Z.

Observación 1.2.7. Estas operaciones de suma y producto en Zn, están bien definidas, es

decir, no dependen del elemento que se elija como representante de cada clase de equivalencia.

En efecto: Sean x,y,z y w G Z„ , entonces:

Capítulo 1. Aritmética Modular.

x + y —x + nki + y + nfc2 = (x + nfci) + (y + fifc2) = (a; + y) + (&i + k2)n = x + y

x • y = x + nfci • (y + rafc2) —sy + (a:&2 + ykx + n&ií^n = x^y.
Además, s\x — zyy = w entonces:

x + y = (z + nki) + {w + nk%) —(z + w) + n(&i +fc2) ^aT + y —s + w

x • y = (z + nfci) • (w + «¿2) ~ zw + n{2¿2 + lüfci + kik2) =$-x-y = z-w.

Definición 1.2.8. Se llama sistema completo de representantes módulo n, o sistema completo

de restos módulo n, a cualquier conjunto de n números enteros que contiene un elemento y

sólo uno de cada clase de equivalencia; esto es, un conjunto de enteros donde todas las clases

en Z„ estén representadas, de allí, Zn —{0,1, 2, •• • ,n —1}. En efecto:

Si a G Z„, con a G Z, por el Algoritmo de Euclides existen enteros q y r tales que

a = nq + r con 0 < r < n; luego a —r —nq=5>n\ a —r =$• a = r(modn) =>a = r.

Ejemplos 1.2.9.

1. El conjunto {0,1, 2,3}, es un sistema completo de representantes de Z4, donde la suma

y producto vienen dadas por:

+ 0 1 2 3 • 0 1 2 3

0 0 1 2 3 0 0 0 0 0

1 1 2 3 0 1 0 1 2 3

2 2 3 0 1 2 0 2 0 2

3 3 0 1 2 3 0 3 2 1

2. Las tablas de sumar y multiplicar de Zg —{0,1,2,3,4, 5} son respectivamente:

+ 0 1 2 3 4 5 . 0 1 2 3 4 5

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

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

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

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

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

5 5 0 1 2 3 4 5 0 5 4 3 2 1
Capítulo 1. Aritmética Modular. 10

Proposición 1.2.10. Sea a G Z tal que mcd(a,ri) — 1 y sea {í"i,r2,--- ,rn} un sistema
completo de representantes módulo n, entonces el conjunto {ar\, ar2, ••• , arn} es también un
sistema completo de representantes módulo n.

Demostración. Sabemos que cualquier sistema completo de restos módulo n debe tener n ele

mentos, así, para ver que los enteros ari, ar2, - • • , arn que son n, forman un sistema completo

de restos módulo n, basta demostrar que este conjunto no tiene elementos repetidos en el sen

tido de que dos elementos estén en una misma clase de equivalencia, es decir, ar¿ / arj(modn)
si i / j.

Esto último es cierto ya que si an —arj(modn) entonces por la ley de cancelación de

congruencias, r¿ —rj lo cual es absurdo, ya que el conjunto {ri,r2, ••• ,r„} es un conjunto
completo de restos módulo n. D

Las clases de congruencias o clases de restos residuales respecto a un módulo dado, per

miten caracterizar a diversos números enteros que cumplen con ciertas propiedades como por

ejemplo:

Ejemplo 1.2.11. Si un número entero z es cuadrado y cubo a la vez, entonces es de la forma

7nó7n + l. En efecto, considerar el conjunto de los enteros módulo 7 y buscar sus cuadrados

y cubos; esto es, Zr - {0,1,2,3,4,5,6}; (Z7)2 - {0,1,4,2} y (ZT)3 - {0,1,6}. Luego, los
cuadrados y cubos a la vez serán las clases que están en la intersección de estos conjuntos

(Z7)2 CliZr)3 = {0,1} correspondientes a tí - 7r¿ y T - 7rc + 1.

Ahora, vamos a introducir las definiciones de ciertas estructuras importantes:

Definición 1.2.12. Sea G un conjunto con una operación * : G x G —> G que satisface las

propiedades:

1. Asociativa: para toda terna (a,b,c) de elementos de G se cumple que (o* 6) *c = a*(b*c).
2. Conmutativa: para todo par de elementos de (a, b) G G se cumple que a * b —b * a.

3. Existencia de Neutro: existe un único elemento 1 G G tal que a*l = l*a = a, V a G G.

4. Existencia del Inverso: para todo a G G existe un elemento b G G tal que a * b — 1.

Capítulo 1. Aritmética Modular. Ll

El par {G, *) se llama grupo abeliano.

Definición 1.2.13. Si un conjunto A con dos operaciones + y * tales que (A, +) es un grupo

abeliano, (A \ {0},*) cumple con las propiedades asociativa, conmutativa, elemento neutro
y además con una relación entre las dos operaciones:

Distributiva: a * (b+ c) —a * b+ a * c, V a, b, c G A.
Entonces la terna (A,+, *) se llama anillo conmutativo. Si además, (A\{0), *) es un grupo
abeliano, la terna (A, +, *) se llama cuerpo.

Los ejemplos úsales de grupos abelianos son (Z, +}, (Q, +), (ffi, +). Los ejemplos usuales
de anillos conmutativos son (Z, +, •), (Q, +, •), (R, +, •). Además, estos dos últimos también
son cuerpos.

Definición 1.2.14. Sea n G Z, n > 1, el conjunto Z„ de enteros módulo n, junto con la

adición y multiplicación definidas previamente, se denomina el Anillo de clases de restos

módulo n.

Se introducen estas definiciones, porque estamos interesados en estudiar las unidades y

divisores de cero en Z„. Para ello, notemos que en el anillo ZI2 de clases residuales módulo

12, con la operación de multiplicación se observa lo siguiente:

2-6 = 0; 3-8-0; 8-9 = 0

Esto es, el producto de dos elementos no nulos puede ser cero. Además, hay clases que

cumplen con la particularidad:

5 • 5 = T; 7 • 7 = T; ÍI-IT = T

Esto es, el producto de dos elementos puede ser uno. Sin embargo, hay elementos x G Zi2

tales que x • y — 0 sólo si y — 0. Por ejemplo, se puede verificar directamente que 5 • y — 0

sólo si y — 0. y por supuesto 1-1 = 1.

Se producen situaciones análogas para los anillos Z¿, Zq, Zs y en particular, para los anillos

Z2,Z3,Z5,Z7, un producto de dos factores es cero únicamente si uno de ellos lo es, es decir,

x • y = 0 si y sólo si x = 0 ó y = 0. Podemos introducir las definiciones siguientes:

Capítulo 1. Aritmética Modular. 12

Definición 1.2.15. Un elemento i / 0 G Z„. es un divisor de cero, si existe un elemento

v / 0 G Zn tal que t-v = 0.

Definición 1.2.16. Un elemento ñ G Z„ es una unidad si existe un elemento v G Z„ tal que

íí-iJ= 1.

Ejemplos 1.2.17.

1. En los anillos Z4, Z6 y Z8, los elementos 2, 3, 4 son los respectivos divisores de cero.

En efecto:

2-2 = 0,, 2-3 = 0Q, 2-4 = 08

2. En el anillo Zg, los siguientes elementos son unidades: 1, 2, 4, 5, 7, 8. En efecto:

T-T-T, 2-5 = T, 4-7-T, 8-8-T

Proposición 1.2.18. Un elemento ñ G Z„ es una unidad, si y sólo si, mcd{u,n) = 1.

Demostración. =£-) Si ü es una unidad entonces existe v G Z„ tal que ñ • ü = 1 esto es,

uv = l(modn). Luego uv —1+nfcparaalgnfc e Zy uv—nk —1. Si llamamos d ~ mcd{u, n)

entonces d j u y d \ n con lo cual d j uv —nk —1 de donde d —1, por lo tanto mcd(u, n) —1.

•£=) Recíprocamente, suponer que mcdfan) —1, entonces existen enteros v y r tales que
1 —uv + jjí" y así; 1 —uv + nr — itw + to* = uv = zí - v. Por tanto íí es una unidad. D

1.3. Restos y Criterios de Divisibilidad.

Una de las aplicaciones más interesantes de la Aritmética Modular tiene que ver con

criterios bajo los cuales un entero dado es divisible por otro. La justificación de estos criterios

radica en el sistema de numeración que se utiliza y la demostración de su validez; en este

texto se hará basado en la teoría de las congruencias. Para ello se tendrá en cuenta que, dado

un entero b > 1 (base del sistema) y un entero positivo a, existe una expresión polinomial

en b, llamado el desarrollo b -ádico de a tal que: a = anbn + an^ibn~1 + • •- + a2b2 + a\b + ao-

Formalmente:
Capítulo 1. Aritmética Modular. 13

Teorema 1.3.1. (Desarrollo b~ ádico o expansión base b): Dado un número entero
b > 1, cada número entero positivo a se expresa de la forma única:

a - ajf + an-ibn~l +••• + a2b2 + ctib + a0.

donde n G N U{0} y los üí (los dígitos del sistema) son enteros tales que 0 < a¿ < b para
todo i — 0,1,- •• ,n.

Demostración. Probaremos el teorema por inducción. Si n = 1, el desarrollo b - ádico de 1

es 1 • 6o y el teorema es cierto. Supongamos que el teorema ha sido probado para todos los
enteros positivos k menores que a.

Por el algoritmo de división tenemos que a = bq + r con 0 < r < b. Más aún, podemos

suponer que a > b pues si a < b, entonces su desarrollo b -ádico es

a —Ob + a, sia<b ó a = lí»+ 0, si a = 6.

Así, a > b y como 1 < b tenemos que q < qb < qb + r = a. Por lo tanto tomando como

hipótesis inductiva que el teorema vale para q se tiene que existe una expresión poiinomial
en b tal que: q —ad>n + aíl_i&",~1 H 1- a\b + ao, con iiéNü {0} y 0 < a¿ < bobteniendo:

a = bq + r = anbn+1 + On-ifc" + •••+ a263 + ax62 + aQb + r

que es un desarrollo b - ádico de a.

Para la unicidad, suponer que:

a = anbn + an_xbn-1 + •-• + a2b2 + a^ + a0 - c,nbm + cm„16m_1 -\ + c2b2 + clb + cQ

con m G N U {0} y 0 < c¿ < b, Vj —0,1, ••• , m. Además notar que:

a - ao + [ai + a2b + ••• + Onb^b = co + [ci + c26 + ••- + cfc"1"1^

y por la unicidad del cociente y eí resto se tiene:

a0 = Co a1+a2b-\ + aj)n~l = ci + c2b H 1- cJT^1

de donde, aphcando la hipótesis inductiva en la igualdad derecha resulta que n — m y

üí —c¿ Vi — 0,1, - • • ,n. D

*•••"" —Mr'm

FAC. ejíp. ca.

Capítulo 1. Aritmética Modular. 14

La escritura decimal que estamos acostumbrados a utilizar en los números enteros no

es ni más ni menos que el desarrollo 10 - ádico o expansión base 10. Algunas veces, para

determinar si un número es divisible por otro, es suficiente con observar la última cifra; esto

depende de que el divisor divida a la base, como cuando se trabaja en la base decimal y se

quiere saber si un entero es divisible por 2 o por 5.

Proposición 1.3.2. Sea a = (ag, ai, ••• On-i, a„,)b; si b = 0(modc) entonces a es divisible
por c si, y sólo si, aü = 0(mod c).

Demostración. Sabemos que a = aa+aib + a2b2 -i hOn-i^"-1 + Onbn. Como b= Q(modc),

aplicando la aritmética de las congruencias se obtiene que a — ao{modc). Además, a es

divisible por c, si y sólo si a = 0(modc) de donde a0 = 0(modc). G

Notar que, la última cifra a0 determina la clase de congruencia módulo c a la cual pertenece

el entero a; es decir, lo que se obtiene observando la última cifra, es el residuo al dividir por

c.

Otro manera de decidir si un número es divisible o no por otro, es estudiando la suma de

sus cifras. Es el caso de los conocidos criterios para saber si un número es divisible por 3 o

por 9, cuando está escrito en nuestra base decimal. La siguiente proposición justifica éstos y

otros casos.

Proposición 1.3.3. Sea a = (a.o,cti, • ••On~i, On)b¡ si b = l(modc) entonces a es divisible

por c si, y sólo si, a0 + ai + a2 -f h an = 0(mod c).

Demostración. Sabemos que o = ao+aib+a^b2^ ha„_ií>"-1+a„6", y como 6 = l(mo-ic),

aplicando aritmética de congruencias se obtiene que

ao —ao(íTiodc)

ai&= ai{modc)

Onbn = an(mod c)

de donde, sumando estas congruencia se tiene

Capítulo 1. Aritmética Modular. 15

a = a0 + ai + a2 -I + an(mod c).
Luego, a es divisible por c sii a = 0(m,od c), obteniendo el resultado. D

Se ha demostrado que si un niimero b es congruente con 1 módulo c, y el número a

está escrito en base b, entonces a es congruente con la suma de sus cifras módulo c. Además,

para saber si un número (escrito en base b) es divisible por c, es suficiente saber si la suma

de sus cifras lo es. Por ejemplo; en la base decimal, la suma de las cifras del entero 19168639

es 43 por tanto: 19168639 = l(mot¿3) y 19168639 = 7(mod9).

Otro criterio utilizado para saber si un número es divisble por otro, es el criterio de la

suma y resta de sus cifras; este es el caso del criterio de divisibilidad por 11 en la base

decimal. Se halla la diferencia entre la suma de cifras de lugares pares y la suma de cifras de

lugares impares; el número es múltiplo de 11 si, y sólo si, la diferencia lo es. Por ejemplo, el

número 19168639 no es dividible por 11 ya que, la suma de las cifras de los lugares pares es

3 + 8 + 1 + 1 — 13, la suma de las cifras de los lugares impares es 9 + 6 + 6 + 9 — 30 y la

diferencia es 17 que no es múltiplo de 11. Este hecho se ilustra en la siguiente:

Proposición 1.3.4. Sea a —(«o. a¡, -• -an_i,an)b; si b = —l(modc), entonces a es divisible

porc si, y sólo si, a$ —ai + a2 —--• + (—l)nan = 0(mod c).

Demostración. Sabemos que a —a0 + a]b + a2b2 + --- + a„_i¿n_1 + Onfe"; si b = —l(mod c)
aplicando la aritmética de congruencias se obtiene

a0 =ao(modc)

a,ib = —ai ([Link] c)

a2b2 = a2{m,odc)

Onbn = (-l)no^(modc).

Luego, sumando se tiene

a = ao —ai + a2 + (—l^Onímod c)
proporcionando así el resultado. D

Además de establecer estos criterios de divisibilidad, la Artimética Modular, proporciona

Capítulo 1. Aritmética Modular. 16

herramientas para decidir si un número dado muy grande que a simple vista no se puede

calcular, es divisible o no por otro, o equivalentemente, encontrar el resto de su división.

Como muestra de ello, se tienen los siguientes:

Ejemplos 1.3.5.

1. Para cualquier entero positivo n, se cumple que 22" —1 = 0(mod 3) o equivalentemente,

22n - 1 es divisible entre 3. En efecto: 22" - 1 = (22)" - 1 - (4)" - 1 = (1)" - l(mod 3) =
l-l(jTMjd3) = 0(mod3).
2. Similar al caso anterior, se prueba que para todo entero n > 1 se cumple que 24" —1

es divisible por 15 o equivalentemente, 2in —1 = 0(mod 15).

3. Para todo entero positivo n, el número 10" + 3 -4"+2 + 5 es divisible por 9. En efecto:
10" + 3 •4"+2 + 5 = 1" + 4" -42 -3 + 5{mod 9)
-l+5 + 48-4"(mod9)

-6 + 3-4"(mod9)
= 6 + 3-(3 + l)"(mod9)

= 6 + 3 • (3" + ji3"-] + ••• + 3n + l)(mod 9)

= 6 + 9 - (3""1 -j- n3"-2 + -•• + n) + 3(mod 9)
= 9 + 9 - (3""1 + tí3""2 + ••• + n)(mod 9)
= 0 + 0(mod 9)

= 0(í77fld9).
4. Para encontrar el resto módulo 5 del número (37)4 -I- 49 • 801 + 120 se procede de la
siguiente manera:

(37)4 + 49 • 801 + 120 = (2)4 + 4 -1 + 0(mod5)

= 16 + 4(mod5)

= 20(mod 5)

= 0(mod5).
Así, el número (37)4 + 49 • 801 + 120 es divisible entre 5.
5. Para encontrar el último dígito de las unidades del número 2-325+3-(8)7+ 5104+(123)5
se procede de como en el ejercicio anterior, considerando módulo 10. Esto es:
Capítulo 1. Aritmética Modular. 17

2•325 + 3 - (8)7 + 5104 + (123)5 = 2•5 + 3{-2)7 + 4 + (3)5(mod 10)

= 10 + 3-6-2 + 4+ 243(mod10)
= 3 - 6 - 2 + 4 + 3(mod 10)
= 43(mod 10)

= 3(mod 10).

Así, el último dígito del número 2 -325+ 3 - (8)7 + 5104 + (123)5 es 3.

1.4. Teorema de Euler- Fermat.

Dada una unidad ü G Z„, el único elemento v G Z„ que cumple con u-v —1„ se denomma

inverso de u módulo tí y se denota por v = u~l. Así por ejemplo, el inverso de 7 en el anillo
Zi2 es 7 y el inverso de 81 en el anillo Zi52 es 137.

Se denotará mediante £7(Z„) al conjunto formado por todas la unidades del anillo Zn con

n > 1, esto es Í7(Z„) —{u G Z„ : mcd(u,n) —1}. Teniendo en cuenta la caracterización de

las unidades de Z„, se tienen los siguientes ejemplos:

U(Z2) = {1}
£/(Z3) = {T,2}
Í7(Z4) = {T,3}
(7{Z5) = {1,2,3,4}
[/(Z6) = {!,5}
ü{In) = {1,2,3,4, 5,6}
[/(Z8) = {1,3,5,7}
U(ZB) = {1,2,4,5,7,8}
C/(Zi0) = {T,3,7,9}

Definición 1.4.1. Para cada entero n > 1 se denota por <p(n) el número de elementos del

conjunto U(Zrí) de las unidades del anillo Z,„ con <p(l) = 1. Queda así definida la función:
i^:N—>N

tí —> 'pin)
Capítulo 1. Aritmética Modular. 18

que se denomina Punción de Euler. En la siguiente tabla, se muestran los valores de (p(n)
para n desde 1 hasta 10.

n 1 2 3 4 5 6 7 8 9 10

<p(n) 1 1 2 2 4 2 6 4 6 4

Además, para todo número natural n, ip(n) coincide con el número de enteros positivos

menores o iguales que n y primos con n; es decir:

ip(n) —Card{m GN : 0 < m < n,mcd(n,m) = 1}.
La función de Euler cumple con las siguientes propiedades:

Proposición 1.4.2.

1. Un entero p> 1 es primo si, y sólo si, <p(p) = p —1.

2. Para todo primo p y todo entero positivo r se tiene queip(pr) =pr—pr~1 = pr_1(p—1)-
3. Sin y m son enteros positivos primos entre si, entonces <p(nm) —<p(n)tp{m).

4- Sin = pripr2 • --p^fc donde los p¡ son primos distintos y los r¡ G N, entonces

rtnJ-nd-J-Jd-ij-a-JL).
Demostración.

1) Si p es un número primo, el conjunto formado por todas la unidades de Zp viene dado

por Zp = {1,2, 3,4, •••p —1}, en consecuencia <p(p) —p —1.

2) Se procederá por inducción en r. Para r = 1, <p(p) = p —1. Suponer cierto para r —k,
<PÍPk) —{v—l)p*-1 y probaremos para r = k + 1; <p{pk+i) = pk+1 —pk-
Notar que p^1 —pk —pk(p —1) —(p —l)pk~1p = f>(pk)p. Como f(pk) son todos los
coprimos con pk, si se multiphcan por p, se añaden p números restantes para el valor de
tp(pk+i), en consecuencia, tp(pk+1) = <p(pk)p = pk+1 —pk-
3) Sabemos que ip(nm) = card{U(Znm)} y (p(n)<p(m) = card{U(Zn)} • card{U(Zm)} =

card{U(Zn)}x {U(Zm)}. Luego, basta con probar que existe una biyección entre los conjuntos
U(Znra) y U(I.n) x U(Zm). Para ello, definir la función:
/ : U(1nm) —» U{Zn) x [/(Zm)
Capítulo 1. Aritmética Modular. 19

/(a) —> (a, a)

donde a, a y a son las clases módulo nm, nym respectivamnete. Notar que,

/(o) - /(fe) «• (a, a) = (fe, fe) «* a = 6,

además, si a —fe se tiene que nm ¡a —fe^m|a —feynja —6-^-a = 6ya = fe; así, la
función está bien definida y es inyectiva.

Por último, hay que probar que Ja función es sobreyectiva, es decir, que dado un elemento

(a,a) G Z„ x Zm, existe un a G Znm tal que f(a) = (a,a). En efecto; como mcd{n,m) = 1
existen p y q e Z tales que 1 —np + mg ^- fe —c = (fe —c)np + (fe —c)mq. Luego tomando

s —(fe —c)py r —{6 —c)q se tiene que fe —c = sn + rm =S- fe —sra = c + rm y llamando a a ese

valor común se tiene que a —b —sny a = c + rm, de donde, a = b(modn) y a = c(mod m),

es decir, f(a) = (a, a).

4) Utilizando 2 y 3 se tiene que:

¥>(«) = ¥>(p?Ml>?) •-•?(&)

=p?-i(Pl-i)p?-,(P2-i)---pTri(pk-i)
= p?(i-¿-)p5'(i-¿)"-p?(i-¿)
= «<1-í)c1-í)í1-¿)- a
Ejemplo 1.4.3. Calculemos ^(1800). Como 1800 = 23 • 32 • 52 se tiene que ^(1800) =
ip{2z •32 •52) = 1800(1 - \) •(1 - |) -(1 - \) = 480. Así, hay 480 elementos inversibíes enel
anillo Zi8o0.

La función de Euler es utilizada en Aritmética Modular, para calcular restos de números

grandes, para ello se tiene el siguiente:

Teorema 1.4.4. (Euler) Si mcd{a,n) —1 entonces a?^ —l(modTí).

Demostración. Considerar el conjunto R —{í*i,r2,--- ,rp(n)} de los enteros positivos menores

que tí y que son coprimos con n. R es un sistema completo de restos módulo n y como

mcd(a, n) = 1, el conjunto aR —{ari, ar2, - -- , af>(„)} es también en sistema completo de

restos módulo n; por consiguiente, a cada r\ G R le corresponde un y sólo un ari G aR tal

que r¡ = oXi(modn).
Capítulo 1. Aritmética Modular. 20

Por otro lado, a elementos diferentes de R le corresponden elementos diferentes de aR,

por tanto:

ar1ar2 •••arv(n) = rxr2- --r^){m,odn)

no necesariamente en ese orden; de donde:

av£n)(rir2 --•rv(„)) = rir2 •-•rv(n){modn)

y como mcd(ri,n) —1 para todo i; aplicando la ley de cancelación de cogmencias se obtiene

a^n) = l{modn). D

Ejemplo 1.4.5. Vamos a calcular el resto de dividir 3348I)2 entre 35. Como med(33,35) = 1
por el Teorema de Euler se tiene 33^35' = 1(mod 35). Como 35 = 7 • 5 y como 5 y 7 son
coprimos y la función ip es multiplicativa resulta que tp(35) —<p(6)-ip(7) —4-6 = 24, de esta

manera 3324 = l(mod35). Por otro lado, 4802 = 24 - 200 + 2 entonces:

334802 = 33<2il'200+2> = (3324)200 •332 = 120G •332{mod35)
= 332{mod35)
= 4(mod 35)

Por lo tanto, el resto de dividir 334802 entre 35 es 4.

Por otro lado, el Teorema de Euler es muy útil en la resolución de ecuaciones de congruen

cia del tipo ax = b{modn), donde mcd(a,n) = 1, muestra de ello se presenta en el siguiente:

Corolario 1.4.6. La solución de la congruencia lineal ax = b{modn) donde mcd(a,n) —1,

viene dada por x —av'^~lb(modn).

Demostración. Si mcd(a,n) —1, según el teorema anterior se tiene que a^"' = l(modn).
Aphcando las propiedad de simetría se tiene que 1 = avi-n\modn); luego multiplicando por
by aphcando la propiedad transitiva de las congruencias resulta que ax = a^^b^modn), de
donde, x = a^^bimodri). •

Ejemplo 1.4.7. Como mcd(9, 5) = 1, la congruencia lineal 9a; = 163(?7iod 5) tiene solución

x - ^5)-llQZ{mod 5); esto es, x - 93 - 3(mod 5) => x - 43 -3(mod 5) => x - 4 -3(mod 5) =>
x = 2(mod5).
Capítulo 1. Aritmética Modular. 21

Otro resultado importante del Teorema de Euler, es el Pequeño Teorema de Ferrnat, cuyo

término fué usado por primera vez por el matemático alemán Kurt Hensel en 1913 en su libro

Zahlentheorie, y más tarde fue conocido como teorema de Fermat, como recoge por ejemplo

Cari Friedricb Gauss en su libro Disquisitiones arithmeticae.

Corolario 1.4.8. (Pequeño Teorema de Fermat). Si p es primo y a un entero tal que

p\a entonces ap = a(modp). Además, para cualquier entero fe, bp = b(modp).

Demostración. Como p es primo, <p(p) —p —1, luego aplicando el teorema anterior se obtiene

que aP~l = l(modp), por consiguiente ap ~ a(modp). Por otro lado, si p j fe entonces
fe = O(modp) y fep —O(modp) de modo que If = b(modp). O

Ejemplo 1.4.9. Calculemos el resto de dividir 1254577 por 13. Observar que 4577 = 12-381+5

y utilizando el pequeño teorema de Fermat se tiene que 12512 = l(mod 13) donde resulta:
1254577 = (m)12-381^ = 1255(mod 13)
= (53)5{mod 13)
= 515(mod 13)
= 512 -53(™?d 13)
y utifizando nuevamente Fermat se tiene que 512 = l(mod 13); de donde
1254577 = 53(mod 13)
= 8(mod 13)
esto es, el resto al dividir 1254577 por 13 es 8.

Ejemplo 1.4.10. Calculemos el resto de dividir 237 por 35. En la ecuación 237 —r(mod 35)
el módulo es 35 = 7 • 5 y el Pequeño Teorema de Fermat no tiene validez para 35, pero si

para los primos 7 y 5 respectivamente. Esto es, 24 —l{mod 5) y 26 = \(mod 7) de donde se

obtiene que 23T = 236 • 2 = (24)9 • 2 = 2(mod5) y 237 = 236 • 2 - (26)6 - 2 - 2(mod7), por lo
tanto 237 = 2(?7íod 35) y así, el resto de dividir 237 por 35 es 2.

El Pequeño Teorema de Fermat es uno de los teoremas clásicos de Teoría de Números

relacionado con la divisibilidad; las aplicaciones son numerosas, se ha utilizado históricamente

Capítulo 1. Aritmética Modular. 22

para analizar la descomposición en producto de factores primos de ciertos enteros y estudiar

problemas de primalidad.

El Pequeño Teorema de Fermat da una condición necesaria para que un número p sea

primo. Es necesario que, para todo número natural a menor que p, ap~l —1 sea divisible por p,
o sea, a?"1 —l(jriodp), este principio es la base del test de primalidad de Fermat. Este test,
al que asumimos un entero n, consiste en ir probando que a"-1 = l(modn) para una serie
de valores de a menores que n. Si n es primo, entonces la congruencia se cumplirá siempre

(condición necesaria del teorema) mientras que si n es compuesto, la congruencia puede no

cumplirse. Si para algún valor de a menor que n no se cumple la congruencia, entonces n es

compuesto.

Sin embargo, el Pequeño Teorema de Fermat no da na condición suficiente para estudiar

la primalidad de un número entero. Tanto es así que existen números enteros p compuestos y

coprimos con a tal que ap~i = l(roodp), estos son los llamados números pseudoprimos. Estos
números tienen la peculiaridad de que pueden pasar el test de primalidad de Fermat algunas

veces, siendo reconocidos como falsos primos. Ejemplo de ello se verifica en la congruencia
234i-i = i(mod341), siendo 341 compuesto.

Teorema 1.4.11. (Wilson). Un entero p es primo si, y sólo si, (p —1)! = —l{modp).

Demostración. (=?*:) Para p=2yp = 3el teorema es claro; suponer entonces que p > 3 y
considerar el conjunto {1, 2, 3, - -• ,p —1} formado por todos los primos relativos con p y sea
a G {1,2,3,-- • ,p —1} con mcd(a,p) —1; luego, existe un único elemento fe en Zp tal que
ab = \{modp) y comop es primo, a = fe si y sólo si, a —1 ó a —p— 1; esto es, 1 y p —1 son

inversos uno del otro; por tanto, cualquier elemento que se elija del conjunto {2,3, ••- ,p —2}
tiene su inverso distinto a él.

En consecuencia, se tienen p —3 elementos que agrupándose de a pares (cada uno con su

inverso) se obtienen ^f3- parejas cuyo producto es congruente con 1 módulo p, esto es:

2-3----p-2 = l(modp)
Capítulo 1. Aritmética Modular. 23

o equivalentemente:

(p —2)1 = l{modp)

de donde, multiplicando ambos lados por (p —1) y utilizando que p —1 = —l(modp) se

obtiene el resultado buscado.

(<í=) : Sea a un entero tal que a | p, entonces \a\ < p. Si \a\ — p entonces a — ±p. Si
\a\ < p entonces a es uno de los números 1, 2, - -- , (p —2), (p —1) y así, a | (p —1)!; como
(p —1)! = —l(modp) ^> (p —1)! + 1 = pfc para algún entero k, se tiene que a | 1, es decir,
a = ±1, de donde se concluye que p es primo. D

Ejemplo 1.4.12. Vamos a resolver la congruencia lineal 17! = r(mod 19). Como 19 es primo,

por el teorema de Wilson se tiene que 18! = —l(modl9). Así, multiplicando la ecuación

original por 18 se obtiene:

17! •18 = 18r{mod 19)

esto es,

18! = 18r(mod 19)

18r = -l(modl9)

18r = í8(mod 19)

r = l(modl9)

por tanto, 17! = l(mod 19).

1.5. Ecuaciones Diofanticas Lineales.

Las Ecuaciones Diofanticas son todas aquellas ecuaciones en la que tanto sus coeficientes

como sus soluciones son enteras; se clasifican según el número de incógnitas y el grado de éstas.

Reciben este nombre en honor al matemático griego del siglo III Diofanto de Alejandría, qmen

dedicó su obra Aritmética a la determinación de soluciones particulares enteras o racionales

de ecuaciones algebraicas.

Las Ecuaciones Diofanticas tienen gran utilidad en diversos problemas de la matemática.

Entre las Ecuaciones Diofanticas más famosas se encuentran las pitagóricas, expresiones en
Capítulo 1. Aritmética Modular. 24

tres variables de la forma x2 -\-y2 —z2 , y su generalización conocida como el último Teorema
de Fermat, x" + yn = z", con n entero positivo.

Sin embargo, y aún cuando es de enorme interés su estudio, en este texto en particular,

se quiere estudiar la resolución de Ecuaciones Diofanticas Lineales de dos incógnitas en el

anillo Zn, es decir, ecuaciones del tipo ax + by = c donde a, fe y c son enteros. La Teoría de

las Congruencias, puede ser usada para determinar las soluciones (si existen ) de este tipo

de ecuaciones, ya que buscar sus soluciones es equivalente a determinar las soluciones de la

congruencia hneal ax = c(mod b).

Consideremos los siguientes ejemplos:

Ejemplo 1.5.1. Considerar la ecuación 3x-\-hy — —4, que es equivalente a la congruencia

lineal 3x = —4(mod 5), de donde 3x = l(mod 5) . El procedimiento para resolver esta última

ecuación, es el mismo que para el caso de los números racionales, tratar de despejar la variable

x y para ello, se necesita multiplicar por el inverso de 3 módulo 5.

ComofTícd(3, 5) —1 entonces 3 tiene inverso módulo 5 y además 1 —3-2 + 5- (—1), de tal

manera que el inverso de 3 módulo 5 es 2. Así, al multiplicar por 2 se obtiene x = 2(mod 5)
que es la solución de la ecuación.

Ejemplo 1.5.2. Considerar la ecuación 3a;+2 = 0(T7iod6). Siguiendo el mismo procedimiento

anterior, al despejar resulta la acuación 3x = 4(mod6) y como 6 y 3 no son coprimos, no

existe inverso de 3 módulo 6.

Por la definición de congruencia, se quiere buscar un x tal que 6 | 3a:—4, estoes, 3x—4 —6k

para algún k G Z. Despejando se obtiene que 3x —Qk — 3(x —2k) = 4 lo cual no puede

suceder, dado que 4 no es divisible por 3; luego la ecuación no tiene solución.

Ejemplo 1.5.3. Variemos un poco la ecuación del ejemplo anterior. Consideremos la ecuación

3x + 3 = 0(mod 6) que es equivalente a 3x = 3(mod 6). En este caso, estamos buscando un

número x tal que 6 | 3a; —3, de donde 3x —3 — 6k y 3x —6k — 3. Dado que todos los

términos son divisibles entre 3, resulta que x —2k — 1 que reescribiendo como ecuación se

obtiene x = l(mod 2).

Capítulo 1. Aritmética Modular. 25

Así, la solución de la ecuación es la clase de 1 módulo 2. Todas las soluciones del problema

original son aquellas clases módulo 6 que coinciden con la clase del 1 módulo 2; dado que, si

a = b(mod6) =^ 6 | a —fe; en particular 2 | a —fe, con lo cual a = b{mod 2).

Estos ejemplos motivan al siguiente:

Teorema 1.5.4. La ecuación diofántica lineal ax + by = c tiene solución entera (x0, yo) si,

y sólo si, mcd(a, b) | c. En tal caso, si d = mcd(a, b), con d —ap + bq, p,q G Z se obtiene
una solución particular de la ecuación de la siguiente forma:

xQ = -d-p , y^-d-q

Demostración. (=^)Suponer que los enteros x0 y y0 son soluciónde la ecuación ax+by = c, es

decir, aa:o + by0 = c. Pues bien, sid —mcd(a, fe) entonces d j a y d j fe =>• d | ax0+ by0 =$• d \ c.

(-^) Suponer ahora que d —mcd(a, fe) es un divisor de c. Entonces mcd^, 2) = 1- P°r la-
identidad de Bezout, existen enteros p y q G Z tales que:

a fe a fe

siendo c/d entero ya que d es divisor de c. Basta tomar:

para obtener que azo + byo —c, es decir, x0 y y0 son solución de la ecuación. O

Ahora bien, ya se sabe reconocer qué ecuaciones diofanticas lineales tienen solución y

además, calcular una solución particular de las mismas. Sin embargo, se quiere una solución

general, es decir, encontrar todas las soluciones de las ecuaciones diofanticas lineales que se

puedan resolver. Para ello, tenemos el siguiente:

Teorema 1.5.5. Si Xq y yo es una solución particular de la ecuación ax + by = c; entonces

todas las soluciones enteras x,y de la misma, son de la forma:

fe a
x = xD + --t y = yo--j-t

con i G Z siendo d — mcd(a,b). Esta solución se llamará solución general de la ecuación

diofántica lineal ax + by — c .
Capítulo 1. Aritmética Modular. 26

Demostración. Si xq, ya es una solución de la ecuación ax + by = c entonces se cumple que

aar0 + by0 = c. Pero entonces las expresiones x = x0 + 2-tyy^ 3/0 - | •í también son solución
de dicha ecuación.

Faltaría ver entonces que todas las soluciones de la ecuación son de la forma como se han

descrito anteriormente. Para ello, partiendo de la solución particular anterior x0, yo, suponer

que se tiene otra solución x, y de la ecuación. Surgen entonces las ecuacioues siguientes:

ax + by = c

ax0 + by0 — c

de donde, restando ambas ecuaciones se obtiene

a(x - aro) + b(y - y0) = 0 (*)

=• a(x - x0) - b(y0 - y)
^i{x-xo) = 2'{yo-y)
y como d —mcd[a, 6), | y \ son coprimos y -d divide a ^(y0 —y) entonces debe cumplirse
que j divide a (y0 —y); esto es y —yo —2 •í con í GZ.
Sustituyendo este valor de y en (*) se llega después de unos cálculos sencillos a la expresión

buscada para a:: x —x0 + | •t. C3

Ejemplo 1.5.6. Considerar- la ecuación diofántica lineal 48x +7y = 17. Como mcd(48,7) —

1, la ecuación tiene solución. Determinemos primeramente una solución particular de la

congruencia lineal equivalente:

48a; = 17(mod 7)

-x = 17(mod7)
—x = 3(mod 7)

x = —3(TTíod 7)

x = 4(m,od 7)

Ahora, sustituyendo x —4 en la ecuación dada se obtiene: 48 - (4) + 7y = 17 de donde

y ——25. Por lo tanto, x = 4 y y = —25 es la ecuación particular de la ecuación 48x+7y —17.

Luego, la solución general de la misma será:

Capítulo 1. Aritmética Modular. 27

x - 4 -|- 7í

y = -25 - 48í £ G Z.

Se ha dado entonces una condición necesaria y suficiente para la existencia de soluciones de

ecuaciones diofanticas lineales con dos igcógnitas, pero también de manera similar se pueden

resolver ecuaciones diofanticas lineales con tres incógnitas. El siguiente ejemplo, muestra el

procedimiento para su resolución:

Ejemplo 1.5.7. Considerar la ecuación diofántica lineal 7x+4y+19z = 84. Tomando módulo

7, determinemos la solución de la congruencia lineal equivalente:

4y + 19z = 84(j7iod 7)

4y = -192(mod7)
4y = -122(mod7)
y = —3z(mod 7)

y = 4z(mod 7)

y = 7t + 4z, í > 0.

Luego, si 2 —n con n entero positivo, y = 4n + 7ty sustiyuyendo estos valores en la ecuación

original se obtiene: 7x + 4(4íi + 7£) + 19rí = 84 =*• x = 12 —5n—4í con ny t enteros positivos.

Así, la solución general de la ecuación será:

x - 12 - 5ti - 4í

' y = 4n + 7£

z —t n,i G Z.

Ahora nos propondremos a utilizar esa teoría de resolución de ecuaciones diofanticas

lineales, para resolver problemas de situaciones reales que pueden ser planteadas por dichas

ecuaciones.

Ejemplo 1.5.8. Una persona compra leche por grandes cantidades a una distribuidora y un

dia específico compra 12 botellones de leche entre entera y descremada pagando 1200 BF. Si

el botellón de leche entera cuesta 30 BF más que la descremada, y ha comprado el mínimo

posible de leche descremada. ¿Cuántos botellones de cada leche ha comprado?

Capítulo 1. Aritmética Modular. ^ 28

Solución: Sean x el número de botellones de leche entera; 12—x el número de botellones de

leche descremada; y el precio de la leche descremada y y-1-30 el precio de la leche [Link]

se ha pagado en total 1200 BF se tiene que:

x(y + 30) + y{12 - x) = 1200

de donde

xy + 30x + 12y -xy= 1200 =*• 30x + 12y = 1200

que es una ecuación diofántica lineal con dos incógnitas.

Comomcd(30,12) = 6 y 6 divide a 1200, la ecuación admite soluciones enteras; por tanto,
se procede a buscar sus soluciones.

La ecuación 30x + 12y = 1200 es equivalente a la ecuación 5x + 2y = 200. Determinemos

la solución entonces de la congruencia lineal:

5x = 200(í7iod 2)

x = 40(mod 2)

x - 2í + 40, í > 0

donde sustituyendo el valor de x se obtiene y — —5£, i > 0. Luego, la solución general de la

ecuación será:

x = 2í + 40

y=-5t í > 0.

Finalmente, veamos cuantos botellones se han comprado de cada leche. Denotemos por

Cd la cantidad de leche descremada y por Ce la cantidad de leche entera; por tanto,

Ce - 2í + 40, t > 0

Cd = 12 - Ce - -2í - 28, t> 0.

Suponiendo que se compra alguna cantidad de leche descremada, se tiene que:

0 < Ce < 12 ^=^ 0 < 2í + 40 < 12

<=*• -40 < 2í < -28

«=*• -20 < í < -14

<==^ í G {-19, -18, -17, -16, -15}

y la cantidad mínima de leche descremada corresponde con la cantidad máxima de leche
Capítulo 1. Aritmética Modular. 29

entera, que se dá para el valor máximo que pueda tener t, esto es, cuando t ——15. Así:

Ce = 2£ + 40=-30 + 40 = 10

0¿=12-Ce = 12-10 = 2 .

Así pues se compraron 10 botellones de leche entera y 2 botellones de leche descremada.

Ejemplo 1.5.9. Un ganadero gastó 100000 BF en 100 animales entre pollos, chivos y

terneros. Los pollos los compró a 50 BF, los chivos a 1000 BF y a 5000 BF los terneros,

adquiriendo animales de las tres clases. ¿ Cuántos animales compró de cada especie?

Solución: Sean x, y y z el número de pollos, chivos y terneros respectivamente. De

acuerdo con el enunciado se tiene el siguiente sistema de ecuaciones:

x + y + z = 100

50x + lOOOy + 50002 = 100000

de donde:

x + y + 2 = 100 x + y + z = 100

x + 20y + lOOs = 2000 x + 20y + 1002 = 2000

x + y + z= 100

x + y + 2 + 19y + 992 - 2000

obteniendo la ecuación dioántica lineal 19y + 992 — 1900. Como mcd(19,99) — 1; existen
soluciones enteras y se determinarán mediante la solución de la congruencia lineal:

19y = 1900(mod99)

y= 100(mod99)

y = l(mod 99)
y-99í + l, í>0

donde sustituyendo el valor de y se obtiene z —19(1 —t), t > 0. Luego, la solución general
de la ecuación será:

y = 99í + 1

y-19(l-í) í>0.
Capítulo 1. Aritmética Modular. 30

Veamos finalmente cuantos animales de cada especie compró el ganadero. Teniendo en

cuenta que adquirió animales de las tres clases, se tiene:

y > 0 => 99í + 1 > 0 =* 99£ > -1 => í > -0,01

z > 0 =*• 19 - 19i > 0 => 19 > 19í =*• 1 > í

de donde —0,01 < í < 1; y como í es un número entero, la única solución posible es cuando

í = 1. De esta manera, y == 1, z — 19 y x = 80; por tanto el ganadero compró 80 pollos, 1

chivo y 19 terneros.

1.6. Sistema de Ecuaciones Lineales.

¿Qué sucedería si se quiere resolver el siguiente problema?: Encontrar un número

tal que al ser dividido entre 3, el resto sea 2; al ser dividido entre 5 el resto sea 3 y al ser

dividido entre 7 el resto sea 5.

Ya en el siglo III, el matemático chino Sun-Tzi quizo saber este número. En atención

a él y otros matemáticos chinos como Lin Hiu (siglo III), Yang Hui (siglo XI y Chon Huo
(siglo XIII) que aportaron soluciones a los sistemas de congruencias lineales, hay un teorema
llamado Teorema Chino del Resto, que puede dar respuesta al problema anterior.

Teorema 1.6.1. (Chino del Resto). Dado un sistema de n ecuaciones lineales:

x = ai (mod rii)

x = a2(modn2)

x = Omimodn^)

donde los módulos son coprimos dos a dos, es decir, mcd(nitnj) -lsii^ j; entonces el

sistema tiene solución única módulo n¡ • n2 - • -tj™-

Demostración. La demostración en realidad es un método para construir la solución. Se pro

bará para el caso n = 2 dejando el general como ejercicio al lector. Considerar las ecuaciones:

x = o.i (mod tíj.) [1]

Capítulo 1. Aritmética Modular. ?1

x = a2(modn2) [2]
con mcd(ni,n2) —1.
Si un entero x verifica la ecuación [1] entonces x — ai + [Link], para algún entero U;

sustituyendo este valor en [2] se obtiene:

Oí +7ijt] —a2(modn2)

esto es,

üi + njii —a2 + íi2Í2Í para algún entero í2

o bien

Jiiíi —n2t2 = «2 —ai; para algún entero i2.

Como mcd(n1,n2) —1, existen enteros p y a tales que n_p+ n2q = 1 de donde, multiplicando
ambos miembros por a_ —ai se obtiene:

nip(a2 —a_) + n2q(n2 - a_) —a2 - a_.

Luedo, tomando l_ —p(a2 —ai) obtenemos que x = ai + nip(a2 —Oí) es la solución común
de las ecuaciones [1] y [2].
Ahora, vamos a describir todas las soluciones. Si x y x' son enteros que satisfacen las
ecuaciones [1] y [2], entonces:
x = x(mod ni)
x = x(modn2)
de ahí que x —x es múltiplo de m y n2\ y como mcdin^n-i) = 1 se concluye que x —x es

múltiplo de ni • n2\ esto es

x = x{modn_n2).
Recíprocamente, si x es una solución común de [1] y [2] y x' es un entero tal que:
x =x(modnin2)

entonces

x —x + n_n2 • t, para algún t G Z

de donde se sigue

x = x{modn_)

x =x(modn2)
Capítulo 1. Aritmética Modular. 32

y por tanto,

x = ai(modn_)

x = a2(modn2).
Luego, x es también una solución común de las ecuaciones [1] y [2]. En consecuencia, el
conjunto de soluciones comunes a las ecuaciones en congruencias [1] y [2] coincide con el

conjunto de soluciones de la congruencia simple

x = ai + n_p{a2 —a_) (modn_n_) •

Ejemplo 1,6.2. Utilicemos este algoritmo para encontrar las soluciones de un sistema de

tres ecuaciones lineales:

x —1(mod 3)

x = Q(mod 7)

x = 5(modll)

Como los módulos son coprimos dos a dos, el sistema tiene solución módulo 231. De la primera

ecuación x = l(mod3) se tiene que x = 1 + 3m, m G Z. Luego, sustituyendo este valor de x

en la segunda ecuación:

1 + 3m = 6(mod 7)
3m = 5(í7íod 7)

3m = 12(T7iod7)

m, = 4(mod 7)

m, = 4 + 7n, n G Z.

Luego x —1 + 3(4 + 7ti) =?> x = 13 + 21n, n G Z. Sustituyendo este nuevo valor de x en la

tercera ecuación se obtiene:

13 + 21n = 5(modll)
21n = -8(mod 11)
2lTíEE3{modll)

7n = l(mod 11)
—4n= l(modll)
Capítulo 1. Aritmética Modular. 33

4Tí=10{modll)
2tí = 5(mod 11)

2ti = 16(í7iod 11)

ti = 8(jnod 11)
tí = 8 + 3lí, í G Z.

Así, x - 13 + 21(8 + llí) =* x - 181 + 231í , í G Z.

¿Qué sucede si los módulos no son coprimos dos a dos?. Se puede llevar el sistema

a un sistema de ecuaciones hneales donde los módulos si sean coprimos dos a dos y poder

aplicar el Teorema Chino del Resto. Se mostrará con un ejemplo este procedimiento:

Ejemplo 1.6.3. Considerar' el siguiente sistema de ecuaciones:

x = 2(mod 10)

x = 6(mod 12)

Utihzando el Teorema Chino del Resto, la primera ecuación es equivalente al sistema de

ecuaciones:

x = 2(?nod 2)

x = 2(mod 5)

Luego en lugar de dos ecuaciones originales, se obtienen las cuatro ecuaciones siguientes:

x = 2(í7iod 2)

x = 2(mod 5)

x —Q(mod 4)

x —Q(mod 3)

La estrategia es factorizar el módulo como producto de primos y separar la ecuación en

varias ecuaciones según el número de primos que aparezcan.

Capítulo 1. Aritmética Modular. 34

Por otro lado, si x = 6(mod4) entonces x = 2(mod2), luego la tercera ecuación del
sistema anterior implica a la primera y se puede considerar simplemente el sistema:
H-

x —2{mod 5)

x = 6(mod4) (1-1)
x = 6(mod 3)

que tiene los módulos coprimos dos a dos, con lo cual se puede aplicar el Teorema Chino del

Resto para encontrar su solución.

También, existen situaciones donde se plantean sistemas de ecuaciones diofanticas hneales

como por ejemplo:

Ejemplo 1.6.4. Amparo nació un 29 de febrero y actualmente tiene una edad que es múltiplo

de 4 más un año. Desde los 14 años viaja a Marida cada tres años y este año le toca viajar.

Además, desde los 18 renueva cada cinco años su licencia de conducir y actuahnente la tiene

vencida. ¿Cual es la edad de Amparo?

Solución: sea x la edad de Amparo, considerando todos los datos dados en el problema,

se pueden plantear las siguientes ecuaciones:

x = \(mod 4); esto es, la edad de Amparo es múltiplo de 4 más 1 año.

x = 14(mod 3), esto es, la edad actual de Amparo menos 14 es múltiplo de 3.

x = 18(?nod 5), esto es, la edad de Amparo menos 18 es múltiplo de 5.
De esta manera, se obtienen el sistema de tres acuaciones hneales:

x —l(mod4)

' x = 2(mod3)

x —3(mod 5)

donde los módulos son coprimos dos a dos, así, por el Teorema Chino del Resto, el sistema

tiene solución.

De la primera ecuación x = l(mod4) se tiene que x —1 + 4i, í G Z. Luego, sustituyendo

este valor de x en la segunda ecuación:

Capítulo 1. Aritmética Modular. 35

l + 4t = 2{mod3)
4í = l(mod3)
4í = 4(mod 3)

£ = 1(mod 3)

í = 3fc + 1, k G Z.

Luego x —4(3k + 1) + 1 =¿- x = 12A; + 5, & G Z. Sustituyendo este nuevo valor de x en la

tercera y última ecuación se obtiene:

12fc + 5 = 3(mod5)
12fc--2(mod5)

12A: = 3(íTíod5)

2k = 8(mod 5)
fc = 4(T7iod 5)

A: - 5o + 4, g G Z.

Así, x —12(5g + 4) + 5 =>• x = 60g + 53 , o G Z. Luego, tomando <j = O que es la solución

más pequeña, se obtiene la edad de Amparo, 53 años.

Ejercicios Propuestos.

1. Pruebe todas las partes de la proposición 1.1.4.

2. Encuentre el máximo común divisor de los siguientes pares de números, además utilice

la identidad de Bezout para expresarlo como combinación lineal de ellos:

a) 116 y 84 b)1850 y 359 c) 3428 y 12600 d) 2400 y 225.

3. Sean a y b enteros y t > 0, pruebe que mcd(ta,tb) = t-mcd(a,b).

4. Sean a,b y c enteros, pruebe que si a \ be y mcd{a,b) —1; entonces a \ c.

5. Sean a,b y n enteros, pruebe que si a \ n, b j n y mcd(a,b) = 1 entonces ab \ n.

6. Sean a, b, c enteros, si b \ c entonces mcd(a,b) = mcd,(a -I- c, b).

7. Si mcd(a, b) —d entonces mcd(;|, 5) —1 cualesquiera sean ios enteros a y b.

8. Factorice en primos los siguientes números enteros:

a) 5040 b)21600 c}45360 d)77616 e) 265837.

9. Pruebe que existen infinitos primos de la forma 4n + 3.

10. Pruebe que existe un número infinito de primos de la forma 6n + 5.

11. Pruebe todas las partes de la proposición 1.2.5.

12. Describir expKcitamente las clases de congruencia módulo tí y el correspondiente con

junto cociente Z/ =n en cada uno de los siguientes casos:
a) tí - 7 b) tí = 9 c) n - 12 d) tí. = 15 e) tí = 37.

36
Capítulo 1. Ejercicios Propuestos. 37

13. Construya las tablas de sumar y multiplicar para cada uno de los sigiúentes sistemas

completos de restos módulo n:

a) Z7 b) Zia c) Z15 d)Z17 e) Zu f) Z23.

14. Pruebe que Z„ es un anillo conmutativo.

15. Pruebe que Z„ es un cuerpo si, y sólo si, n es primo.

16. Puebe que U(XP) con p primo es un grupo.

17. Sea p un primo. Pruebe que los únicos elementos del grupo ¡7(ZP) que coinciden con su

inverso son lp y p —lp ——lp.

18. Describir explícitamente los divisores de cero y las unidades de los siguientes anillos:

a) Z_ b) Z7 c) Z_ d)Zi2 e) Z16.

19. Calcule <¿>{n) para cada uno de los siguientes enteros:

a) n = 139 b) tí - 143 c) tí = 385 d) n = 2592 e) n - 55125.

20. Pruebe que si p es primo impar, entonces p es de a forma 4n—l ó 4n + 3.

21. Pruebe que si p es primo impar, entonces p es de a forma 6tí + 1 ó 6tí + 5.

22. Pruebe que ningún entero cuadr-ado positivo es de la forma 3n —ló3n + 2, pero si de

la forma, 3n, ó 3rt + 1.

23. Pruebe que toda potencia par de cualquier número impar es de la forma 8r + 1, con r

entero positivo.

24. Pruebe que la octaba potencia de cualquier número entero es de la forma .1 7ti ó 17tí +1

ó 17n + 16 con tí entero positivo.

25. En la base decimal, pruebe que un número es divisible por 2 si, y sólo si, termina en

cifra par.
Capítulo 1. Ejercicios Propuestos. 38

26. En la base decimal, pruebe que un número es divisible por 5 si, y sólo si, termina en 0

o en 5.

27. En la base decimal, pruebe que un número es divisible por 20 si, y sólo si, termina en

00, 20, 40, 60, 80.

28. En la base decima!, pruebe que un número es divisible por 3 o por 9 si, y sólo si, la

suma de sus cifras es divisible por 3 ó 9 respectivamente.

29. Pruebe que un número en base diez es múltiplo de 11 si, y sólo si, lo es la diferencia

entre las sumas de las cifras de lugar par y las de lugar impar.

30. Todo número entero n puede ser expresado de la forma n —10Í + u donde 0 < u < 9.

Pruebe que n es divisible por 7 si, y sólo si, lo es t —2u.

31. Deduzca un criterio de divisibilidad para los enteros 13 y 17 respectivamente.

32. Sea p un número primo y n un entero tal que 1 < n < p —1; pruebe que el coeficiente

binomial (£) es divisible por p.

33. Sea p un primo, pruebe que para cualquier par de enteros x, y se tiene que (x + y)p —

xp + yp(modp).

34. Puebe que el número 32451 + 5235D + 4 es divisible por 2.

35. Pruebe que para cualquier entero positivo ti, el número 32" + 7 es divisible por 2.

36. Pruebe que para todo entero positivo n se cumple que 23™ —1 = 0(mod 7).

37. Pruebe que para cualquier entero positivo n, el número 2 - 7™ + 3 • 5™ —5 es divisible

por 3.

38. Pruebe que para cualquier entero positivo tí, el número 33™-1 + 2"+I es divisible por 7.

39. Pruebe que 3 - 52n+1 + 23n+1 es divisible por 17, para todo entero positivo n.

40. Pruebe que para cualquier entero positivo tí, el número 4 • 6" + 5"+1 = 9(mod 20).
Capítulo 1. Ejercicios Propuestos. 39

41. Pruebe que para cualquier entero positivo tí, el número 8 - 7n + 4™+2 es divisible entre
24.

42. Pruebe que si o es un entero impar, entonces a2 = l(T7iod8).

43. Encuentre el residuo al dividir 230 entre 15.

44. Encuentre el resto al dividir 220 — 1 entre 41.

45. Encuentre el resto al dividir 244 — 1 entre 89.

46. Encuentre el resto al dividir 61S87 entre 37.

47. Encuentre el último dígito de las unidades de 32008 + 32006.

48. Encuentre el último dígito de las unidades de los números 31G0 y 77 .

49. Puebe que los números 42528 + 63143 y 3245i + 52350 + 4 son divisibles por 8.

50. Pruebe que 7 divide a 22225555 + 55552222.

51. Pruebe que si n es un entero positivo, n2 —n es divisible por 2; n3 —n es divisible por

6 y ns —n es divisible por 10.

52. Sean o, b G Z y p primo. Pruebe que si aP = tfimodp), entonces a = b(modp).

53. Pruebe que si p y q son primos distintos y av = a(mod p) y aq = a(mod q) entonces

ap<} —a(modpq) para cualquier entero a.

54. Pruebe que 2340 = l(mod341).

55. Encuentre la solución positiva más pequeña de 2403T = x(mod 7).

56. Encuentre la solución general de la ecuación 98x = l(mod 139).

57. Encuentre la solución general de la ecuación 17x = 5(mod 13).

58. Encuentre el resto de la división de 2i3 por 7.

Capítulo 1. Ejercicios Propuestos. 40

59. Encuentre el resto al dividir 44+6™ entre 7.

60. Encuentre el resto de la división de 3101 por 23.

61. Encuentre el resto de la división de 325 por 77.

62. Encuentre el resto de la división de 54"+1 + 2 • 46n+1 por 13.

63. Deduzca si los números 205 y 2047 son speudoprimos.

64. Resolver la congruencias: 21! = r{mod23) y 49! = r(rnod 51).

65. Demuestre que 10! = —l(mod 11).

66. Encuentre las soluciones positivas de las ecuaciones diofanticas hneales:

a) 5x + 3y - 52

b) 15x + 7y = 111

c) 40x + 63y - 521

d) 123x + 57y = 531

e) 97x + 98y = 1000

f) x + 2y + 32 - 10

g) 3x —6y + 5z— 11

h) 7x + 4y + 193 = 84

i) 23x + 17y +112-130

67. Encuentre los enteros positivos c, con 10 < c < 20 para los cuales no tiene solución la

ecuación diofántica 84x + 990y = c. Determine la solución general para los restantes

valores de c.

68. Encuentre el valor máximo de c para que la ecuación 7x + 9y = c tenga exactamente

seis soluciones enteras positivas.

Capítulo 1. Ejercicios Propuestos. 41

69. Encuentre las soluciones enteras de la ecuación:

V(x + y)(x - y) + (2x + 2y - 3)y - 2(x - 7) - x + y + 3

70. Encuentre la forma general de todos los enteros positivos que al ser devididos por 5,7

y 8 dejan residuos 3, 2 y 5 respectivamente.

71. Encuentre los dos enteros positivos más pequeños que al ser divididos por 3, 7 y 11,

dejan residuos 1, 6,y 5 respectivamente.

72. Encontrar todas las soluciones de los siguientes sistemas de congruencias lineales:

x = 5(77íod 3)
x = l(mod 3) x = 2(mod 3)
x = \(rnod 5)
x = —l(mod 4) x = 3(mod4)
a) b) { ¿){x = 3(mod 7)
x = —2{mod 5) x = 2(mod 5)
x = 4(mod ]1)
X= 12(7TÍ0dll) x = 3(mod 8)
x = 2(mod 13)

73. Una mujer tiene una cesta de manzanas. Haciendo grupos de 3 le sobran 2 y haciendo

grupos de 4 le sobran 3. Encuentre el número de manzanas que contiene la cesta,

sabiendo que están entre 100 y 110.

74. Un hombre va a una tienda de ropa y compra 12 franelas entre negras y grises por 1200

BF. Si las franelas negras cuestan 30 BF más que las grises, y ha comprado el mínimo

posible de estas últimas, ¿Cuántas franelas ha comprado de cada color?

75. Una persona va al supermercado a comprar 12 piezas de frutas entre manzanas y

naranjas por 99 BF. Si una manzana cuesta 3 BF más que una naranja y compró más

manzanas que naranjas; ¿Cuantas de cada una compró?.

76. Si cada gallo vale 5 BF, cada gallina vale 3 BF y cada tres polluelos valen 1 BF.

¿Cuántos gallos, gallinas y polluelos se pueden comprar' con 100 BF, comprando por lo

menos un ave de cada especie?

Capítulo 1. Ejercicios Propuestos. 42

77. Un vendedor de naranjas recuerda que el día anterior tenía entre 100 y 150 naranjas y

cuando hacía montones de 2,3,4,5,y 6 naranjas, siempre sobraba una. ¿Cuántas naranjas

tema el día de ayer?.

78. Tres campanas comenzaron a sonar al mismo tiempo y sonaron a intervalos de 23, 29 y

34 segundos respectivamente. La segunda y tercera campana sonaron 39 y 40 segundos

más que la primera. ¿Cuántas veces sonó cada campana?. ¿Durante cuánto tiempo
sonó cada campana si todas cesaron antes de los 20 minutos?.

79. Un viejo problema chino: Cual es el menor número de monedas de oro que podía tener

un grupo de 17 piratas si se sabe que al repartirlas por igual sobraron 3 y después

de pelear por esas tres, uno de ellos fué asesinado. Al repartir de nuevo el total de

las monedas, sobraban 10 y de nuevo lucharon por ellas y un pirata resultó muerto.

Después de eso, se repartieron las monedas por igual.

80. Resolver el siguiente acertijo indio: si los huevos de una cesta se retiran de 2 en 2; de

3 en 3; de 4 en 4; de 5 en 5 o de 6 en 6, quedan respectivamente, 1,2,3,4,5, huevos.

Sin embargo, si se retiran de 7 en 7 no queda ninguno. ¿Cuál es la menor cantidad de
huevos que debe haber en la cesta?
Bibliografía.

Apóstol, T. (1980). Teoría Analítica de Números. Editorial Reverte. Barcelona

- España.

Herstein, I. (1990). Álgebra Moderna. Editorial Trilas. México.

Isaacs, R. (2007). Criterios de Divisibilidad y Congruencias. Notas de Álge

bra y Combinatoria. Universidad Industrial de Santander. Bucaramanga - Santander,
Colombia.

Kostrikin, A. (1983). Introducción al Álgebra. Editorial Mir. Moscú.

Oneto, A. (2000). Notas de Álgebra. F.E.C. Universidad del Zulia. Maracaibo -

Venezuela.

Pollard, H. y Diamond, H. (1998). The Theory of Algebraic Numbers. Tercera

edición. Mineloa, New York.

Romero, E. (2009). Enteros, Anillos y Polinomios. Notas de álgebra. F.H.E.

Universidad del Zulia. Maracaibo - Venezuela.

Santos, D. (2010). Prácticas de la Teoría Elemental de Números para

Olimpiadas Matemáticas. Departamento de Matemática. Universidad de Alcalá -

España.

Rosas, T. (2004). Un curso de Álgebra. Trabajo de ascenso. F.E.C. Universidad

del Zulia. Maracaibo - Venezuela.

43
Capítulo 1. Bibliografía. 44

• Stewart, I. y Tall, D. (1979). Algebraic Number Theory. Chapman and Hall,

Londres.

• Vinogradov, I (1977). Fundamentos de la Teoría de los Números. Segunda

Edición. Editorial Mir. Moscú.