Aritmetica de Numeros Enteros

Aritmetica de N umeros Enteros
Pablo De Napoli
versi on 0.8.2
Resumen
Este es un apunte de las teoricas de Algebra I, turno noche del
primer cuatrimestre de 2007, con algunas modicaciones introducidas
en 2014.
Dios cre o los n umeros naturales. Todo lo demas es invento del
hombre. Leopold Kronecker (1823-1891)
La matem atica es la reina de las ciencias, y la teora de los
n umeros es la reina de la matem atica. (Carl F. Gauss, 1777
1855)
1. Divisibilidad
Recordamos algunas notaciones usuales:
Notamos por N al conjunto de los n umeros naturales (o enteros positivos)
N = 1, 2, 3, . . .
y por N
0
al conjunto de los n umeros naturales incluyendo al cero (tambien
llamados enteros no negativos):
N
0
= 0, 1, 2, 3, . . .
Finalmente, notamos por Z al conjunto de los n umeros enteros (positivos,
negativos y cero)
Z = . . . , 3, 2, 1, 0, 1, 2, 3, . . .
1
Notas de

Algebra I - c _2007-2014 Pablo L. De N apoli 2
En el conjunto Z de los n umeros enteros, las operaciones de suma a + b,
resta a b y producto ab son siempre posibles
1
. En cambio, la divisi on a : b
no es siempre posible.
Por ejemplo, la division 6 : 3 es posible, ya que existe un entero 2 tal
que 6 = 3 2. Mientras que la division 7 : 3 no es posible, ya que no existe
ning un entero c tal que 7 = 3c.
Esto motiva la siguiente denicion:
Denici on 1.1 Sean a, b Z dos enteros, b ,= 0, diremos que b divide a a,
o que a es divisible por b, o que a es un m ultiplo de b, o que b es un factor
de a si existe alg un entero c Z (necesariamente unico) tal que a = bc. (De
modo que a : b = c). Simbolizamos este hecho mediante la notacion: b[a
Por ejemplo, 3 divide a 6, pero 3 no divide a 7.
Algunas propiedades elementales de la divisibilidad son las siguientes:
Para cualquier a Z, a ,= 0; a[a (ya que a = a1). Es decir, la relaci on
de divisibilidad es reexiva.
Para cualquier a Z, a ,= 0; tenemos que a[0.
Para cualquier a Z, 1[a y 1[a (ya que a = 1 a = (1) (a)).
Vemos que 1 y 1 son divisores universales
2
.
Si a[b y b[c (siendo a, b ,= 0) entonces a[c, vale decir que la divisibilidad
es una relaci on transitiva.
Prueba: Como a[b, existe un entero e tal que
b = ae
y como b[c, existe un entero f tal que
c = bf
1
Esto suele expresarse en algebra diciendo que Z es un anillo. Mas adelante veremos
otro ejemplo de anillos como los polinomios, en los cuales tambien es posible desarrollar
una teora de la divisibilidad, en estrecho paralelismo con la aritmetica de los enteros.
2
En la terminologa usual en algebra, esto se expresa diciendo que 1 son las unidades
de Z
Notas de

Sustituyendo en esta ecuacion el valor de b, y usando la propiedad
asociativa del producto:
c = (ae)f = a(ef)
Concluimos que a[c.
Si a[b, entonces (a)[b, a[(b) y (a)[(b). Vale decir que para las
cuestiones de divisibildad los n umeros a y a son completamente equi-
valentes
3
(podemos olvidarnos del signo cuando estamos estudiando
cuestiones de divisibilidad)
Si b[a siendo a, b ,= 0, entonces [b[ [a[.
Prueba: Si b[a, entonces existe un c tal que a = bc. Tomando m odulo,
tenemos que:
[a[ = [b[[c[
y como [c[ 1 (ya que si c = 0 entonces sera a = 0), concluimos que:
[a[ [b[
Si a[b y b[a (siendo a, b ,= 0) entonces a = b.

Prueba: Por la propiedad anterior, [a[ [b[ y [b[ [a[. En consecuen-
cia, [a[ = [b[. Y concluimos que a = b.
En particular, concluimos que si nos restringimos a los enteros positivos,
la relacion de orden resulta antisimetrica. Siendo reexiva, antisimetrica
y transitiva, concluimos que la divisibilidad es una relaci on de orden (en
sentido amplio) en N. Sin embargo, no es una relacion de orden total, ya
que existen elementos incomparables (por ej: 3 y 5 son incomparables,
ya que no es cierto que 3 divida a 5, ni tampoco que 5 divida a 3).
Si a[b y a[c, se tiene que a[b + c y que a[b c.
Prueba: Como a[b, existira un entero e tal que:
b = ae
3
En la terminologa usual en algebra, se dice que a y a son elementos asociados de Z
Notas de

y como a[c, existira otro entero f tal que:
c = af
Sumando estas dos ecuaciones, y aplicando la propiedad distributiva,
tenemos que:
b + c = ae + af = a(e + f)
Concluimos que a[b + c. Similarmente, tenemos que:
b c = ae af = a(e f)
y concluimos que a[b c.
2. N umeros Primos
Denici on 2.1 Decimos que un n umero p N, p > 1 es primo, cuando
sus unicos divisores (en N) son 1 y p. Los n umeros naturales mayores que 1,
que no son primos, se denominan compuestos. Un n umero n es compuesto
si es posible expresarlo en la forma n = n
1
n
2
donde 1 < n
1
, n
2
< n.
Los primeros n umeros primos (menores que 100) son
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
La importancia de los n umeros primos radica en que en alg un sentido son
los atomos o bloques con los que se forman los dem as n umeros:
Teorema 2.1 Todo entero n > 1, o bien es primo o se puede descomponer
como producto de n umeros primos.
Prueba: Hacemos inducci on global en n. Para n = 1 no armamos nada
(luego el teorema es trivialmente cierto en este caso). Consideremos pues
un n umero n > 1, y supongamos que el teorema es cierto para los n umeros
menores que n. Si n es primo, tampoco armamos nada. Supongamos pues
que n es compuesto. En este caso, por denicion, es posible escribir a n como
producto de dos n umeros naturales n
1
, n
2
N menores que n
n = n
1
n
2
Notas de

Pero por hip otesis de induccion entonces, n
1
y n
2
se descomponen como
producto de primos:
n
1
= p
1
p
2
. . . p
k
n
2
= q
1
q
2
. . . q
s
donde p
1
, p
2
, . . . p
k
y q
1
, q
2
, . . . q
s
son primos. Entonces n tambien se puede
descomponer como producto de primos:
n = p
1
p
2
. . . p
k
q
1
q
2
. . . q
s
En virtud del principio de induccion global, concluimos que el teorema es
verdadero para cualquier n N.
Corolario 2.1 Todo n umero entero n > 1 que no sea primo, es divisible por
un primo.
Por ejemplo, supongamos que queremos obtener una descomposici on de
60 como producto de primos. Comenzamos escribiendo 30 = 4 15. Pero
4 = 2 2 y 15 = 3 5, luego
60 = 2 2 3 5
(Observemos que algunos primos pueden repetirse en la factorizaci on)
Constituye un hecho de fundamental importancia (conocido como teore-
ma fundamental de la aritmetica) que la descomposicion de un entero como
producto de primos es unica, salvo el orden de los factores. Demostrare-
mos esto m as adelante (obtendremos este heho, como una consecuencia del
algoritmo de Euclides para el calculo del maximo com un divisor).
Otra observacion importante es que si bien es relativamente sencillo obte-
ner la factorizacion en factores primos para n umeros peque nos, no se conoce
ning un algoritmo eciente (esto es: un procedimiento efectivo) para la obten-
ci on de la descomposicion en factores primos de n umeros grandes
4
.
Otro hecho muy importante, ya demostrado por el matematico griego
Euclides (que vivi o aproximadamente hacia el 300 A.C.) en sus Elementos
5
,
es que el conjunto de los n umeros primos es innito:
4
Por un algoritmo eciente, queremos decir un algoritmo cuya complexijad (n umero de
operaciones requeridas) sera polinomial, como funcion del n umero de dgitos del n umero
n. Se ha conjeturado que la factorizacion en factores primos tiene complejidad exponencial
pero esto no ha sido demostrado.
5
Libro IX, Proposicion 20. Disponible (traducido al ingles) en http://aleph0.clarku.
edu/
~
djoyce/java/elements/bookIX/propIX20.html
Notas de

Teorema 2.2 (Euclides) Existen innitos n umeros primos.
Prueba: La prueba de Euclides de este teorema, ha quedado como un ejem-
plo clasico de demostracion por reducci on al absurdo. Este metodo de de-
mostraci on consiste en suponer que el teorema es falso, y mediante una serie
de pasos l ogicos llegar a una contradicci on. Esta contradicci on nos permite
concluir que la suposici on de que el teorema es falso no puede sostenerse, y
en consecuencia, el teorema debe ser verdadero.
Supongamos pues que s olo existiera una cantidad nita de n umeros pri-
mos:
p
1
= 2, p
2
= 3, p
3
= 5, . . . , p
N
El argumento de Euclides, consiste entonces en formar el n umero
q = p
1
p
2
. . . p
N
+ 1
Conforme al corolario del teorema anterior, o bien q es primo, o bien es
divisible por alg un primo q
< q. Pero q no es divisible por ninguno de los

primos p
1
, p
2
, . . . p
N
(ya que si p
i
[q entonces p
i
[q p
1
p
2
. . . p
N
= 1 y sera
p
i
= 1, lo cual es absurdo). En cualquiera de los dos casos, hemos encontrado
un primo que no no esta en nuestra lista inicial, que de acuerdo a la suposicion
que hemos hecho era una lista completa de todos los n umeros primos.
Esta contradicci on prueba que nuestra hip otesis de que solo existe un
n umero nito de n umeros primos no puede sostenerse, y en consecuencia,
podemos concluir que existe un n umero innito de n umeros primos.
Ejercicio: La prueba de Euclides no es la unica prueba posible de la
innitud de los primos. Una prueba alternativa
6
debida a G. Polya utiliza
los denominados n umeros de Fermat:
F
n
= 2
2
n
+ 1
Los primeros F
n
son
F
0
= 3
F
1
= 5
6
G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 4ta. Edicion,
teorema 16
Notas de

F
2
= 17
F
3
= 257
F
4
= 65537
y son todos primos. Fermat conjeturo entonces, que los n umeros F
n
eran
todos primos. Sin embargo, esta conjetura result o ser falsa pues:
F
5
= 4294967297 = 641 6700417
A pesar de que los F
n
no son necesariamente primos, s es posible probar
que los diferentes F
n
son coprimos (no tienen factores en com un). En conse-
cuencia, cada F
n
es divisible por un primo diferente y por lo tanto, podemos
concluir que existen innitos primos.
Sugerencia: Usando la identidad algebraica
x
n
+ 1
x + 1
= x
n1
x
n2
+ x
n3
. . . + x 1
v alida para todo entero n par, demostrar que F
n
[F
m
2 si m > n. Concluir
que F
n
y F
m
son coprimos si n ,= m.
Otra prueba diferente de la innitud de los primos, fue dada por Juan
Pablo Pinasco en [6].
3. El algoritmo de divisi on
Toda la aritmetica gira en torno del siguiente hecho fundamental, conoci-
do desde la escuela primaria: Si bien la divisi on a : b puede resultar imposible
dentro de los enteros, siempre es posible efectuar una division aproximada,
obteniendo un resto menor que el divisor. Por ejemplo: la division entera de
7 por 3 da un cociente de 2 con un resto de 1, y se tiene que 7 = 3 2 + 1.
El siguiente teorema, formaliza este hecho:
Teorema 3.1 Dados n umeros naturales a N
0
y b N existen unicos
n umeros naturales tales que a = bq + r y 0 r < b.
Notas de

Denici on 3.1 En la situacion del teorema anterior, diremos que q es el
cociente y r el resto en la division entera de a por b.
Prueba: Primero probaremos la existencia: para ello consideramos el siguien-
te conjunto
C = a bk : k N
0
, a bk 0 N
0
Armamos que C es no vaco. En efecto tomando k = 0 vemos que a C.
En consecuencia, por el principio del mnimo entero C tiene un elemento
mnimo. Llamamos r a este mnimo. Como r C, se tiene que r se escribe
en la forma r = a bq para alg un q N
0
(y por lo tanto a = bq + r), y que
r 0.
S olo falta pues probar que r < b. Si por el contrario fuera r b, podemos
considerar r
= r b 0. Tenemos que:
r
= a bq b = a (q + 1)b
Concluimos que r
C. Pero como r
< r, esto contradice el hecho de

que r era el mnimo de C. En consecuencia, deducimos que necesariamente
r < b. Esto concluye la prueba de la parte de existencia.
Ahora hemos de demostrar la unicidad: para ello supongamos que tuvie-
ramos dos posibles cocientes q y q
, con sus correspondientes restos r y r
. Es
decir que,
a = bq + r con 0 r < b
a = bq
+ r
con 0 r < b
Entonces igualando estas ecuaciones tendramos que:
bq + r = bq
+ r
y por lo tanto:
b(q
q) = r r
(1)
En particular, vemos que
b[r r
Notas de

Podemos sin perdida de generalidad, suponer que r r
(intercambiando
sino los nombres). Entonces conclumos que si r ,= r
, sera b r r
, y por
lo tanto b r.
Pero sabamos que r < b. Esta contradicci on, muestra que necesariamente
se tiene que r = r
, y entonces por (1),

b(q
q) = 0
Como si el producto de dos enteros da cero, alguno de los dos debe ser
cero, concluimos as mismo que q = q
.
Observaci on: En particular, se tiene que b[a si y s olo si el resto en la
divisi on entera de a por b es cero.
En general, en matematica, la palabra algoritmo hace referencia a un
procedimiento mecanico para calcular algo. En este caso, la prueba anterior
no parece proporcionar realmente un algoritmo para calcular q y r; pero es
f acil darse cuenta que en efecto hay un algoritmo escondido en la prueba
anterior: se trata del algoritmo de division por restas sucesivas
7
ENTRADA: a (dividendo),b (divisor), siendo b ,= 0.
SALIDA: q (cociente) y r(resto), en la division entera de a por b
1. r a
2. q 0
3. Mientras r b, repetir las siguientes instrucciones:
a) r r b
b) q q + 1
En algunas situaciones ser a util considerar divisiones enteras con n umeros
negativos. En este caso el algoritmo de divisi on se enuncia del siguiente modo:
Teorema 3.2 Dados n umeros enteros a, b Z con b ,= 0 existen unicos
n umeros enteros tales que a = bq + r y 0 r < [b[.
7
Escribimos este algoritmo en forma de pseudocodigo, facilmente traducible a cualquier
lenguaje de programacion. q y r son variables, es decir espacios en la memoria de la
computadora en los que podemos guardar datos (en este caso, n umeros). La echa
representa la operacion de asignacion de un valor a una variable (es decir que dicho valor
se guarda temporariamente en dicha variable). Por ejemplo la asignacion q q + 1 tiene
el efecto de incrementar en uno el valor de la variable q.
Notas de

Prueba: El caso en que a 0, b > 0 ya lo demostramos antes. Consideremos
por ejemplo el caso
8
en que a < 0 y b > 0. En ese caso a > 0, y podemos
dividir a por b utilizando el teorema anterior, para obtener un cociente q
y un resto r
, de modo que
(a) = q
b + r
y 0 r
< b
Si r
= 0, tenemos que:
a = (q)b
Luego tomando r = 0 y q = q
tenemos lo que queremos. Si r
,= 0, notamos
que:
a = (q
)b r
= (q
1)b + b r
Como 0 b r
< b, tomando q = q
+1 y r = b r
se cumple el enunciado.
Esto concluye la prueba de la existencia del cociente y el resto en este caso, la
prueba de la unicidad es analoga a la que dimos antes. Queda ver que sucede
en el caso b < 0. La idea es similar. Lo dejamos como ejercicio.
Ejercicio: Completar la prueba del teorema anterior, para el caso en que
b < 0.
4. Bases de numeraci on
Desde la escuela primaria estamos familiarizados con la representaci on
de enteros en diferentes bases. Por supuesto, lo primero que se aprende es la
base decimal (donde tenemos 10 dgitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9).
1035 = 1 10
4
+ 0 10
3
+ 3 10
1
+ 5 10
0
Pero tambien es posible utilizar otras bases. Por ejemplo en la base binaria
(base 2) tenemos s olo dos dgitos 0 y 1, y por ejemplo el n umero once se
escribe como 1011 en binario
9
, ya que
1011
2
= 1 2
3
+ 0 2
3
+ 1 2
1
+ 1 2
0
= 11
8
Este caso nos sera util mas adelante, al estudiar congruencias.
9
Es costumbre indicar la base como subndice, as pues 102
3
quiere decir el n umero
cuyo desarrollo en base 3 es 102.
Notas de

La base binaria es muy utilizada en computacion, debido a que los cir-
cuitos de las computadoras digitales almacenan la informaci on en unidades
(bits) que tienen dos estados posibles
10
, que podramos pensar como encendi-
do (tpicamente 5 volt) o apagado (0 volt). Si pensamos al estado apagado
como cero, y encendido como uno. Entonces, un n umero puede represen-
tarse en una computadora como un conjunto de bits, utilizando el sistema
binario de numeracion.
El algoritmo para expresar un n umero en una determinada base es bien
conocido desde la escuela: consiste en efectuar sucesivas divisiones enteras
del n umero por la base, hasta obtener un cociente nulo.
Por ejemplo: para expresar 11 en la base 2 efectuamos las divisiones:
11 = 5 2 + 1
5 = 2 2 + 1
2 = 1 2 + 0
1 = 0 2 + 1
Entonces el desarrollo de 11 en base 2 esta formado por los sucesivos
restos 1, 1, 0 y 1.
Notemos que los ceros a la izquierda no aportan nada: por ejemplo
00123 = 123
Salvo esta ambig uedad, el desarrollo de un n umero en una base dada, es
unico. Ahora enunciaremos esto como un teorema formal:
Teorema 4.1 Dada una base b 2 entera, siempre es posible escribir a cada
entero n N de una unica forma como:
n = d
k
b
k
+ d
k1
b
k1
+ . . . + d
2
b
2
+ d
1
b
1
+ d
0
b
0
donde d
i
N
0
y 0 d
i
< b, y d
k
,= 0.
Prueba: Para probar la existencia del desarollo, utilizamos un argumento
de induccion global en n.
Claramente n = 1 admite el desarollo 1 = 1b
0
.
10
De hecho la palabra bit es una abreviatura de binary digit.
Notas de

Si n > 1, y suponemos que el teorema es cierto para los n umeros menores
que n, efectuamos la divisi on entera de n por b, escribiendo entonces:
n = qb + d
0
donde 0 d
0
< b. Pero como b 2, el cociente q es menor que n.
Entonces por la hip otesis inductiva, n admitir a un desarrollo de la forma:
q = d
k
b
k1
+ d
k1
b
k2
+ . . . + d
3
b
2
+ d
2
b
1
+ d
1
b
0
(para alg un k y ciertos d
i
con 0 d
i
< b, y d
k
,= 0).
Sustituyendo vemos que:
n = d
k
b
k
+ d
k1
b
k1
+ . . . + d
2
b
2
+ d
1
b
1
+ d
0
b
0
En virtud del principio de inducci on global, concluimos que cualquier
n N admite alg un desarrollo en base b.
Para establecer la unicidad del desarrollo, procedemos tambien por in-
ducci on global en n.
Claramente el unico desarrollo posible de n = 1 es 1 = 1 b
0
(pues si
d
i
,= 0 para alg un i > 1, n b. Y entonces debe ser 1 = d
0
).
Supongamos pues, que el n umero n admitiera dos desarrollos en base b:
n = d
k
b
k
+ d
k1
b
k1
+ . . . + d
2
b
2
+ d
1
b
1
+ d
0
b
0
n = d
j
b
j
+ d
k1
b
k1
+ . . . + d
2
b
2
+ d
1
b
1
+ d
0
b
0
donde 0 d
i
< b y 0 d
i
< b para todo i, d
k
,= 0, d
j
,= 0; y supongamos
que los n umeros menores que n admiten un unico desarrollo.
Nuevamente, tenemos que:
n = qb + d
0
n = q
b + d
0
donde
q = d
k
b
k1
+ d
k1
b
k2
+ . . . + d
3
b
2
+ d
2
b
1
+ d
1
b
0
q
= d
j
b
j1
+ d
j1
b
j2
+ . . . + d
3
b
2
+ d
2
b
1
+ d
1
b
0
Notas de

Pero entonces, por la unicidad del cociente y del resto en la division entera
de n por b, tendremos que q = q
y que d
0
= d
0
.
Pero entonces como q < n, en virtud de la hip otesis de inducci on global,
los desarrollos de q y q
(que son el mismo n umero) deben coincidir, es decir

que k = j y d
i
= d
i
para 1 i k.
En virtud del principio de induccion global, esto prueba que cualquier
n N admite un unico desarrollo en base b.
Otras bases muy utilizadas en computacion son la base 8 (octal) y 16
(hexadecimal), porque son utiles como abreviatura de la base binaria, pues
como 8 = 2
3
y 16 = 2
4
cada dgito octal equivale a tres dgitos binarios y
cada dgito hexadecimal equivale a cuatro dgitos binarios.
Por ejemplo: el n umero 202 = 2
8
+ 2
4
+ 2
3
+ 2
1
se representa en binario
como 11001010. Para escribirlo en octal agrupamos sus dgitos de a tres como
11 001 011, ahora 11 es 3 en binario, 001 es 1 y 010 es 2, concluimos que 202
se escribe como 312 en octal, y en efecto:
202 = 3 8
2
+ 1 8
1
+ 2 8
0
Para escribir un n umero en hexadecimal necesitamos 16 dgitos. Por ello,
adem as de los dgitos usuales 0,1,2,3,4,5,6,7,8,9; se emplean las letras A
(=10), B (=11), C (=12), D (=13), E (=14) y F (=15).
Continuando con el ejemplo anterior, para escribir 202 en hexadecimal,
agrupamos sus dgitos binarios de a cuatro:
1100 1010
Ahora 1100 es 12 (= C) en binario, y 1010 es 10 (= A) en binario.
Concluimos que 202 se escribr como CA en hexadecimal. Y en efecto,
202 = 12 16
1
+ 10 16
0
Ejercicio: Justicar porque la base octal y la base hexadecimal se pueden
utilizar como abreviatura de la base binaria.
Otro ejercicio: (base factorial) Probar que cada n N
0
puede expre-
sarse de una unica forma como
n = d
1
+ d
2
2! + d
3
3! + . . . + d
k
k!
donde 0 d
i
< k para i = 1, 2, . . . k.
Notas de

5. El algoritmo de Euclides para el calculo
del maximo com un divisor
El algoritmo de Euclides
11
es un algoritmo para el c alculo del maximo
com un divisor entre dos n umeros.
Denici on 5.1 Sean a, b N dos enteros positivos. Denimos el maximo
com un divisor entre a y b como el maximo de los divisores comunes entre a
y b, es decir como el maximo de los enteros positivos d tales que d[a y d[b.
Notacion: d = (a, b) o d = mcd(a, b).
Por ejemplo, sean a = 18 y b = 12. Los divisores de 18 son
12
1, 2, 3, 6, 9, 18
y los de 12 son
1, 2, 3, 4, 6, 12
Por lo tanto, los divisores comunes son 1, 2, 3 y 6, y en consecuencia, el
m aximo com un divisor entre 18 y 12 es 6.
Para calcular el m aximo com un divisor entre dos enteros r
0
= a y r
1
= b el
algoritmo de Euclides realiza una serie de divisiones sucesivas (Supondremos
por simplicidad que a > b, ya que sino podemos intercambiar los roles).
Primero dividimos a por b, obteniendo un primer cociente q
1
y un resto
que llamamos r
2
, de modo que:
a = bq
1
+ r
2
(0 r
2
< r
1
) (2)
(Llamamos r
2
al primer resto y no r
1
porque llamando r
0
a a y r
1
a b
podemos escribir esta ecuacion como
r
0
= r
1
q
1
+ r
2
(0 r
2
< r
1
)
11
Elementos, libro VII, proposicion 2, disponible (traducido al ingles) en http://
aleph0.clarku.edu/
~
djoyce/java/elements/bookVII/propVII2.html. Como siempre,
Euclides presenta sus razonamientos de una manera geometrica, pensando los n umeros da-
dos por longitudes de segmentos. Notar tambien que la version original del algoritmo utiliza
restas sucesivas en lugar de divisiones, pero esto es notablemente menos eciente.
12
Mas adelante veremos como obtener todos los divisores de un n umero en forma sis-
tem atica a partir de su factorizacion como producto de primos.
Notas de

y esto facilitar a la escritura de las demostraciones subsiguientes)
Si r
2
,= 0, podemos dividir r
1
por r
2
, obteniendo un nuevo cociente q
2
y
un nuevo resto r
3
de modo que:
r
1
= r
2
q
2
+ r
3
(0 r
3
< r
2
)
Si r
3
,= 0, podemos volver a dividir r
2
por r
3
, obteniendo ahora un cociente
q
3
y un resto r
4
de modo que:
r
2
= r
3
q
3
+ r
4
(0 r
4
< r
3
)
As podemos continuar este proceso, mientras r
k
,= 0, dividimos a r
k1
por r
k
, obteniendo un cociente q
k
y un resto r
k+1
, de modo que:
r
k1
= r
k
q
k
+ r
k+1
(0 r
k+1
< r
k
) (3)
Observamos que la sucesion de restos que vamos obteniendo es decrecien-
te:
r
1
> r
2
> r
3
> . . .
Por ello, tarde o temprano este proceso recursivo debe detenerse, y ob-
tendremos que r
N
= 0 para alg un N. Armamos entonces que el ultimo resto
no nulo proporciona el maximo com un divisor:
Teorema 5.1 Sean a, b N y sea r
0
= a, r
1
= b, r
2
, . . . , r
N1
, r
N
= 0 la
sucesion de restos construida por el algoritmo de Euclides. Entonces,
r
N1
= mcd(a, b)
Prueba:
Probaremos este teorema en dos etapas:
Etapa 1: Probaremos que r
N1
[r
k
para todo k y por lo tanto que r
N1
[a
y r
N1
[b, es decir que probaremos que r
N1
es un divisor com un de a y b.
Notamos que la ultima ecuaci on del algoritmo de Euclides es [(3) con
k = N 1]:
r
N2
= r
N1
q
N1
En consecuencia r
N1
[r
N2
. La ecuaci on anterior es:
Notas de

r
N3
= r
N2
q
N2
+ r
N1
Pero como ya sabemos que r
N1
[r
N2
podemos deducir que r
N1
[r
N3
.
En general, probaremos por inducci on global en j que r
N1
[r
Nj
para
j = 1, 2, 3, . . . , N: Para j = 1 es obvio, y para j = 2 ya lo probamos.
Supongamos que efectivamente r
N1
[r
Nl
para l = 1, 2, . . . , j 1. Enton-
ces por (3) con k = N (j 1)
r
Nj
= r
N(j1)
q
N(j1)
+ r
N(j2)
Pero por hip otesis inductiva, estamos asumiendo que r
N1
[r
N(j1)
y
r
N1
[r
N(j2)
. Concluimos que r
N1
[r
Nj
.
El principio de induccion global, implica entonces que r
N1
[r
Nj
para
todo j con 1 j N. En particular r
N1
[r
0
= a y r
N1
[r
1
= b, como
armamos.
Etapa 2: Probaremos que si d es cualquier divisor com un de a y b en-
tonces d[r
N1
, en consecuencia, si d > 0, d r
N1
. Esto probara que r
N1
es el m aximo com un divisor.
Notamos que si d es un divisor com un de a y b, la primera ecuaci on del
algoritmo de Euclides:
a = bq
1
+ r
2
implica que d[r
2
. La segunda ecuaci on:
r
1
= r
2
q
2
+ r
3
implica entonces que d[r
3
y continuando podemos probar por induccion
global en k que d[r
k
para k = 1, 2, . . . , r
N1
.
En efecto, para k = 1, 2 ya lo probamos. Si asumimos que d[r
l
para
l = 1, 2, . . . , k 1, tenemos que por (3) con k 1 en lugar de k):
r
k2
= r
k1
q
k1
+ r
k
y entonces como por hipotesis inductiva d[r
k1
y d[r
k2
, concluimos que d[r
k
.
El principio de inducci on global permite armar entonces que d[r
k
para
todo k con 1 k N 1.
Ejemplo: Calculemos el m aximo com un divisor entre 360 y 42 utilizando
el algoritmo de Euclides: mediante sucesivas divisiones encontramos que:
Notas de

360 = 8 42 + 24
42 = 1 24 + 18
24 = 1 18 + 6
18 = 3 6 + 0
En este caso, el ultimo resto no nulo, que proporciona el maximo com un
divisor es 6.
Incidentalmente la demostracion del teorema anterior, proporciona la si-
guiente caracterizaci on del m aximo com un divisor
13
:
Corolario 5.1 El maximo com un divisor d = mcd(a, b) entre dos n umeros
naturales a, b N, esta caracterizado por las siguientes propiedades:
i) Es un divisor com un: d[a y d[b.
ii) Cualquier otro divisor com un d
lo divide: si d
[a y d
[d, entonces d
[d.
Una consecuencia muy importante del algoritmo de Euclides es la siguien-
te:
Teorema 5.2 Sean a, b N y sea d = mcd(a, b) su maximo com un divisor.
Entonces, existen enteros , Z tales que:
a + b = d
es decir, que el maximo com un divisor entre dos enteros positivos, siempre
se puede escribir como una combinaci on lineal entre ellos, con coecientes
enteros.
Obtendremos la demostraci on de este teorema como caso particular (k =
N 1) del siguiente lema:
Lema 5.1 Para = 0, 1, . . . , N 1, existen enteros
k
,
k
Z tales que:
k
a +
k
b = r
k
13
Esta caracterizacion arma que el maximo com un divisor entre a y b es el nmo
entre ellos (o sea la mayor cota inferior de ambos), en el orden dado por la divisibilidad.
Notas de

Prueba: Deniremos la sucesiones (
k
)
0kN1
y (
k
)
0kN1
recursivamen-
te. Para k = 0, denimos
0
= 1,
0
= 0 de modo que:
a = r
0
=
0
a +
0
b
Similarmente, para k = 1, denimos
1
= 0,
1
= 1, de modo que:
b = r
1
=
1
a +
1
b
Tomemos ahora un k > 1, por (3), con k 1 en lugar de k, tenemos que:
r
k2
= r
k1
q
k1
+ r
k
o sea:
r
k
= r
k2
r
k1
q
k1
Entonces, utilizando nuevamente induccion global en k, tenemos que:
r
k
= (
k2
a +
k2
b) (
k1
a +
k1
b)q
k1
= (
k2
k1
q
k1
)a + (
k2
k1
q
k1
)b
En consecuencia,denimos
k
y
k
recursivamente por:
k
=
k2
k1
q
k1
para k = 2, 3, . . . , N 1
k
=
k2
k1
q
k1
para k = 2, 3, . . . , N 1
y el principio de induccion global nos permite concluir que el lema se verica
para todo con 1 k N 1.
Continuacion del ejemplo anterior: En el ejemplo anterior, en el que
calculamos el maximo com un divisor entre 360 y 42, el proceso descripto nos
proporciona las siguientes escrituras de los sucesivos restos como combinacion
lineal de 360 y 42 (La ultima igualdad, corresponde a la escritura del m aximo
com un divisor):
24 = 1 360 + (8) 42
18 = (1) 360 + 9 42
6 = 2 360 + (17) 42
M as adelante, resultar a de utilidad extender la nocion de maximo com un
divisor a n umeros enteros negativos o cero. Dado que dos n umeros enteros que
Notas de

s olo dieren en el signo son equivalentes respecto a la divisibilidad, resulta
natural denir que:
mcd(a, b) = mcd([a[, [b[)
Por ejemplo, de acuerdo a esta denici on, tenemos que:
mcd(4, 6) = mcd(4, 6) = 2
Y tambien denimos:
mcd(a, 0) = mcd(0, a) = a
Observenos que al extender la nocion de maximo com un divisor de esta
manera, los teoremas anteriores se siguen vericando.
El teorema anterior, proporciona una serie de consecuencias de gran im-
portancia. Comencemos por una dencion:
Denici on 5.2 Decimos que dos n umeros a, b Z son coprimos (o primos
entre s) si los unicos divisores comunes de a y b son 1. Esto es claramente
equivalente a decir que su maximo com un divisor mcd(a, b) es 1.
Corolario 5.2 Dos enteros a, b Z son coprimos si y solo si existen ,
Z tales que a + b = 1.
Prueba: Por el teorema anterior, si el maximo com un divisor es 1, es claro
que se escribe como una combinacion lineal de a y b. Recprocamente, si
existen y tales que 1 = a +b entonces si d es un divisor com un de a y
b, tenemos que d[a , d[b y en consecuencia: d[a + b = 1, luego d = 1.
Concluimos que a y b son coprimos.
Corolario 5.3 Si a[bc y a es coprimo con b, entonces a divide a c.
Prueba: Como a es coprimo con b, por lo anterior 1 se escribe como una
combinaci on lineal de a y b, es decir existen , Z tales que:
a + b = 1
Entonces, multiplicando por c tenemos que:
ac + bc = c
Notas de

Como a[ac, y a[bc, concluimos que a[c.
Un caso particular de este corolario, nos conducir a a la prueba del teore-
ma fundamental de la aritmetica (unicidad de la descomposici on en factores
primos):
Corolario 5.4 Si p es un n umero primo y p[ab, entonces p[a o p[b.
Prueba: Notamos que si p no divide a a, entonces p es coprimo con a (por
ser p primo). En consecuencia, por el corolario anterior como p[ab, p[b.
Es conveniente observar que este corolario se generaliza sin dicultad
a productos de mas de dos factores (haciendo inducci on en el n umero de
factores)
Corolario 5.5 Si p es un n umero primo y p[a
1
a
2
. . . a
k
, entonces p[a
i
para
alg un i.
Ejercicio: Demostrar por inducci on que en cada paso del algoritmo de
Euclides se tiene que:
mcd(a, b) = mcd(r
k
, r
k1
)
(Una prueba alternativa, quiz as m as sencilla, del teorema 5.1 puede basarse
en este hecho). Una condicion como esta, que se mantiene en cada paso de
un algoritmo se denomina un invariante del algoritmo.
Otro ejercicio: (el algoritmo de Euclides binario) La siguiente es
una variante del algoritmo de Euclides que solo utiliza divisiones por 2, lo que
resulta ventajoso si se opera con n umeros escritos en el sistema binario (como
sucede en una computadora), ya las divisiones se pueden efectuar mediante
operaciones de shift (corrimiento de los dgitos hacia la derecha).
El algoritmo puede describirse recursivamente de la siguiente manera:
mcd(u, v) :=
_
_
u si v = 0
2mcd
_
u
2
,
v
2
_
si u es par y v par
mcd
_
u
2
, v
_
si u es par y v impar
mcd
_
u,
v
2
_
si u es impar y v par
mcd
_
v,
uv
2
_
si u es impar y v impar
Por ejemplo: para calcular el maximo com un divisor entre 60 y 42, pro-
cedemos de la siguiente manera:
Notas de

mcd(60, 42) = 2mcd(30, 21) = 2mcd(21, 15) =
2mcd(15, 3) = 2mcd(6, 3) = 2mcd(3, 3) = 2mcd(3, 0) = 6
El ejercicicio consiste en demostrar que este algoritmo efectivamente fun-
ciona (Esto es: que siempre termina y que proporciona el resultado correcto).
Otra pregunta (para pensar): C omo podra adaptarse este algoritmo de
Euclides binario para que tambien proporcione los coecientes que permiten
escribir al maximo com un divisor como una combinaci on lineal de los n umeros
en cuestion (teorema 5.2) ?
Ejercicio optativo (para los que sepan programar): Escribir una
implementaci on del algoritmo de Euclides en su lenguaje de programacion
favorito, y (m as dicil) escribir un programa que proporcione tambien la
escritura del m aximo com un divisor como combinaci on lineal
14
.
6. Congruencias
En esta seccion, introduciremos la notacion de congruencias, que resulta
de gran utilidad, a la hora de estudiar muchas cuestiones relacionadas con la
divisibilidad.
Denici on 6.1 Sean a, b Z y sea a N. Decimos que a y b son congruen-
tes modulo n y lo escribimos
a b (mod n)
cuando n[b a.
Algunos ejemplos:
3 8 (m od 5)
6 1 (m od 7)
12 0 (m od 3)
Otra denicion equivalente de congruencia puede darse en terminos del
resto de la divisi on entera m odulo n:
14
En mi pagina web, encontrar an una implementacion en el lenguaje C.
Notas de

Proposicion 6.1 Sean a, b Z y sea n N. Entonces, a b (m od n) si y
solo si a y b proporcionan el mismo resto cuando los dividimos por n.
Prueba: Dividamos a y b por n, es decir escribamos:
a = nq + r donde 0 r < n
b = nq
+ r
donde 0 r
< n
Hemos de demostrar que a b (m od n) si y solo si r = r
.
Supongamos primero que r = r
. Entonces b a = nq
nq = n(q
q).
Luego n[b a o sea a b (m od n).
Por otra parte, supongamos que a b (m od n). Entonces:
b a = n(q
q) + r
r
Si suponemos que r
r entonces como 0 r
r < n, tenemos que

r
r debe ser el resto (y q
q el cociente) en la divisi on enterea de b a

por n. Pero entonces en virtud de la unicidad del resto en la division entera,
r
r = 0, ya que n[b a.
(Si fuera r
< r, la prueba es analoga pues b a (m od n))

Las congruencias comparten muchas de las propiedades de la igualdad,
por ejemplo:
Proposicion 6.2 La relacion de congruencia tiene las siguientes propieda-
des:
Reexividad: a a (m od n).
Simetra: Si a b (m od n), entonces b a(mod n).
Transitividad: Si a b (m od n) y b c (m od n), entonces a c
(m od n)
Prueba:
1. Para cualquier a Z, tenemos que:
n[a a = 0
en consecuencia,
a a (m od n)
Notas de

2. Si a b (m od n) entonces, de acuerdo a la denici on, n[b a y por lo
tanto n[ (b a), o sea n[a b. Lo que nuevamente, de acuerdo a la
denici on, signica que b a (m od n).
3. Si a b (m od n) y b c (m od n), entonces n[b a y n[c b. En
consecuencia, n[(b a) + (c b) y por lo tanto n[c a, lo que de
acuerdo a la denici on dice que a c (m od n).
Recordamos que una relaci on que verica estas tres propiedades se llama
una relacion de equivalencia, y que una relaci on de equivalencia determina
una partici on del conjunto donde est a denida en clases de equivalencia.
Para ser explcitos, denimos la clase de a de un a Z m odulo n por:
a = b Z : a b (m od n)
y denimos Z
n
como el conjunto de clases de equivalencia modulo n.
En virtud de la proposici on 6.1, existen tantas clases modulo n como
posibles restos en la division entera por n. Pero los posibles restos en la
divisi on modulo n son 0, 1, . . . , n1. Concluimos que existen exactamente n
clases en Z
n
, o sea:
Z
n
= 0, 1, . . . , n 1
Por ejemplo, si n = 5, existen exactamente 5 clases de congruencia modulo
5, a saber:
0 = . . . , 10, 5, 0, 5, 10, 15, . . .
1 = . . . , 9, 4, 1, 6, 11, 16, . . .
2 = . . . , 8, 3, 2, 7, 12, 17, . . .
3 = . . . , 7, 2, 3, 8, 13, 18, . . .
4 = . . . , 6, 1, 4, 9, 14, 19, . . .
y
Notas de

Z
5
= 0, 1, 2, 3, 4
Notemos que cada clase es innita, pero el n umero de clases es nito.
El hecho de que estas clases forman una partici on de Z signica que cada
n umero entero pertenece exactamente a una de estas clases.
Una propiedad muy importante de las congruencias es que pueden su-
marse, restarse y multiplicarse como si fueran igualdades:
Proposicion 6.3 Si a b (m od n) y c d (m od n) entonces se verican:
a + c b + d (m od n)
a c b d (m od n)
ac bd (m od n)
Prueba: Por hip otesis, n[b a y n[d c, en consecuencia:
n[(b a) + (d c) n[(b + d) (a + c)
es decir que a + c b + d (m od n), como armamos. Por otra parte,
n[(b a) (d c) n[(b d) (a c)
es decir que: a c b d (m od n), que es nuestra segunda armacion.
Por otra parte, como n[b a y n[d c, podremos escribir:
b a = ne
d c = nf
para ciertos enteros n, f Z. Entonces:
bd = (a + ne)(c + nf) = ac + nec + naf + n
2
ef = ac + n(ec + af + nef)
En consecuencia: ac bd (m od n).
Decimos entonces, que la relaci on de congruencia es compatible con las
operaciones de suma, resta y multiplicacion.
El hecho de ser compatible la relacion de congruencia con las operaciones
de suma, resta y producto hace posible denir las correspondientes operacio-
nes entre las clases de restos m odulo n (es decir en Z
n
)
Notas de

Denici on 6.2 Sean A, B Z
n
dos clases de restos modulo n. Para denir
la suma A + B procedemos del siguiente modo, elegimos un elemento cual-
quiera a A y otro elemento b B. Entonces denimos la clase A+B como
la clase en Z
n
que contiene al elemento a + b. Del mismo modo para denir
la resta A B o el producto A B procedemos del mismo modo, eligiendo
un elemento a A y otro b B, y deniendo AB (respectivamente AB
como la clase en Z
n
que contiene al elemento a b (respectivamente ab).
En virtud de la proposicion 6.3, estas operaciones entre las clases modulo
n resultan bien denidas ya que el resultado solo depende de las clases A y
B, y no de los elementos que a A, b B que hayamos elegido.
La aritmetica denida en Z
n
de esta manera se denomina tambien aritmeti-
ca modular (m odulo n).
Veamos algunos ejemplos:
Ejemplo 1: Consideremos dos clases m odulo 5 por ejemplo,
A = 3 = . . . , 7, 2, 3, 8, 13, 18, . . .
B = 4 = . . . , 6, 1, 4, 9, 14, 19, . . .
Para efectuar la suma A+B podemos elegir cualquier n umero en la clase
A, por ejemplo a = 13 y cualquier n umero en la clase B por ejemplo b = 6,
efectuamos la suma a + b = 7 y nos jamos en que clase m odulo 5 cae el
resultado (mirando cual es el resto en la divisi on entera de 7 por 5). En este
caso 7 C, siendo
C = 2 = . . . , 8, 3, 2, 7, 12, 17, . . .
por lo que, de acuerdo a la denicion tenemos que, A+B = C, o tambien
podemos expresarlo del siguiente modo:
13 +6 = 7
Que pasara si hubieramos elegido otros representantes de las clases
A y B por ejemplo a = 3 y b = 9 ?. En este caso, a + b = 12, pero notemos
que 12 pertenece a la misma clase C que obtuvimos antes, y en consecuencia
volvemos a obtner que A + B = C. Esto se debe a que justamente como
Notas de

13 3 (m od 5)
y
6 9 (m od 5)
podemos concluir que:
13 + (6) 3 + 9 (mod 5)
En general, la denici on 6.2 signica que:
a + b = a + b
a b = a b
a b = a b
La siguiente es una tabla de las operaciones de suma y producto en Z
5
:
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
Ejemplo 2: El ejemplo mas sencillo de aritmetica modular con el que en
realidad estamos familiarizados desde la escuela primaria, es Z
2
.
De hecho, existen dos clases modulo 2, la de los n umeros pares
P = 0 = . . . , 6, 4, 2, 0, 2, 4, 6, . . .
y la de los n umeros impares:
I = 1 = . . . 5, 3, 1, 1, 2, 3, 5, . . .
Las operaciones entre estas nos clases son familiares: por ejemplo la suma
de dos n umeros pares es par
Notas de

P + P = P o 0 + 0 = 0
la de un par y un impar es impar:
P + I = I o 0 + 1 = 1
y la de dos impares es par:
I + I = P o 1 + 1 = 0
An alogamente podemos considerar el producto, por ejemplo: el producto
de un par y un impar es par
P I = P o 0 1 = 0
Estas operaciones nos dan las siguientes tablas:
+ 0 1
0 0 1
1 1 0
0 1
0 0 0
1 0 1
Como se ve en estos ejemplos Z
n
resulta un conjunto (nito) donde est an
denidas las operaciones de suma, resta y multiplicaci on con propiedades
similares a las de dichas operaciones en los enteros. En el lenguaje del algebra
esto se esxpresa diciendo que Z
n
es (al igual que Z) un anillo
15
.
Ejercicio: Confeccionar las correspondientes tablas de la suma y el pro-
ducto para los modulos 3, 4, 6 y 7. Que similitudes y diferencias se observan?
A pesar de las muchas similitudes entre las igualdades y las congruencias,
es necesario notar que algunas propiedades de las igualdades no valen para
las congruencias. Por ejemplo, en general no es posible cancelar factores no
nulos en las congruencias. Por ejemplo:
2 1 2 4 (m od 6)
15
Mas adelante veremos otros ejemplos de anillos, como los polinomios. Para la denicion
formal de anillo vease por ejemplo el libro

Algebra Moderna, de Birko y Mc. Lane. Si
bien (formalmente) no estudiaremos las estructuras algebraicas como anillos y cuerpos en
este curso; es conveniente ir acostumbrandose a la terminologa.
Notas de

Sin embargo,
1 , 4 (m od 6)
En consecuencia, en general no se puede dividir congruencias.
La siguiente proposicion arma que sin embargo, es posible cancelar fac-
tores que sean coprimos con el m odulo:
Proposicion 6.4 Si ac bc (m od n) y c es coprimo con n, entonces a b
(m od n)
Prueba: Si ac bc (m od n), entonces n[bc ac = (b a)c. Pero como c
es coprimo con n, por el corolario 5.3, concluimos que n[b a, es decir que
a b (m od n).
Un caso particular, especialmente sencillo, es cuando el m odulo es primo.
Corolario 6.1 Si ac bc (m od p) y p es primo, entonces si c , 0 (mod p),
tenemos que a b (m od p)
Observaci on 6.1 Si a b (m od n) y m[n entonces tambien tenemos que
a b (m od m).
Prueba: Por hip otesis n[b a. Como m[n, por transitividad deducimos que
m[b a, o sea a b (m od m).
6.1. Criterios de divisibilidad
Las congruencias permiten demostrar en forma sencilla algunos criterios
de divisibilidad conocidos desde la escuela:
Criterio de divisibilidad por 3 o por 9: Un n umero natural (escrito
en el sistema decimal) es divisible por 3 (o por 9) si y s olo si la suma de sus
cifras es divisible por 3 (respectivamente por 9).
Prueba: Sea
n = d
k
10
k
+ d
k1
10
k1
+ . . . + d
2
10
2
+ d
1
10 + d
0
la escritura de n en decimal, con 0 d
i
< 10. Entonces como
10 1 (m od 3)
Notas de

deducimos que:
10
k
1 (m od 3) para todo k 1
y consecuentemente
n S = d
k
+ d
k1
+ . . . + d
2
+ d
1
+ d
0
(mod 3)
En particular n es congruente con 0 m odulo 3, si y s olo s la suma S de
sus cifras lo es. Para la divisibilidad por 9, la demostracion es enteramente
similar.
Otro criterio similar es el siguiente:
Criterio de divisibilidad por 11: Un n umero natural (escrito en el
sistema decimal) es divisible por 11 si y s olo la diferencia entre la suma de
sus cifras de los lugares pares, y la suma de sus cifras de los lugares impares
es disible por 11.
Prueba: Ahora, tenemos que:
10 1 (m od 11)
y en consecuencia:
10
k
(1)
k
(m od 11) para todo k 1
Entonces, manteniendo la notacion de la prueba anterior, vemos que:
n D =
k
j=0
(1)
j
d
j
(m od 11)
pero notemos que:
D =
_
_
j par
d
j
_
_
_
_

j impar
d
j
_
_
y n congruente a 0 m odulo 11 si y solo si D lo es.
Ejercicio: Demostrar los criterios de divisibilidad por 4 y por 5, a saber:
1. Un n umero n es divisible por 5 si y s olo si el dgito de las unidades es
0 o 5.
2. Un n umero n es divisible por 4 si y s olo si el n umero formado por el
dgito de las decenas y el de las unidades lo es.
Notas de

7. Ecuaciones Diofanticas Lineales
Como otra aplicacion mas del algoritmo de Euclides, podemos estudiar el
problema de resolver ecuaciones diofanticas lineales. Una ecuacion diof antica
es una ecuacion en la que interesa encontrar las soluciones enteras (reciben
este nombre en honor al matem atico Diofanto de Alejandra (siglo III), quien
estudi o estas ecuaciones en su Aritmetica).
Una ecuacion diofantica lineal en dos variables es una ecuaci on de la
forma:
ax + by = c (4)
siendo a, b y c n umeros enteros.
Geometricamente, este problema signica que buscamos los puntos en el
plano de coordenadas enteras que esten situados sobre una recta.
Teorema 7.1 La ecuacion diofantica lineal (4) tiene solucion si y solo si
d = mcd(a, b) divide a c.
Prueba: Como d[a y d[b, si hay una soluci on debemos tener que d[ax y d[ay
y por lo tanto que d[ax + by = c. Esto prueba que la condici on es necesaria.
Para demostrar que es suciente, supongamos que d[c. Entonces c = dc
para alg un c
Z. Pero en virtud del teorema 5.2, existen , Z tales que:

a + b = d
Multiplicando entonces esta ecuacion por c
:
c
a + c
b = c
y por lo tanto x
0
= c
, y
0
= c
es una solucion particular de la ecuacion

diof antica (4).
Ejemplo: consideremos la ecuacion diof antica

10x + 12y = 3
Entonces mcd(10, 12) = 2 y como 2 no divide a 3, de acuerdo al teorema
anterior la ecuaci on no tiene soluciones (Esto es particularmente obvio en
este ejemplo, pues el primer miembro es necesariamente par)
Notas de

Otro ejemplo: Consideremos por otra parte la ecuacion diofantica:
5x + 3y = 12 (5)
Como mcd(3, 5) = 1 podemos asegurar, de acuerdo al teorema anterior
que siempre existe una soluci on. Para encontrarla, utilizamos el algoritmo de
Euclides para escribir al 1 como combinacion lineal de 3 y 5:
5 = 1 3 + 2
3 = 1 2 + 1
En consecuencia, usando el procedimiento descripto en el teorema 5.2,
encontramos que:
2 = 1 5 + (1) 3
1 = 1 5 + 2 3
Multiplicando esta ecuacion por 12, tenemos que:
12 = (12) 5 + 24 3
En consecuencia, x
0
= 12, y
0
= 24 es una soluci on particular de la
ecuaci on diofantica (5).
Si bien la demostraci on del teorema anterior proporciona una solucion
particular, en caso de que tal soluci on exista, no proporciona todas las solu-
ciones.
Supongamos pues que hayamos encontrado una solucion particular (x
0
, y
0
)
de (4) y que (x, y) es otra soluci on de dicha ecuaci on. Entonces, restando y
utilizando que dicha ecuacion es lineal, vemos que:
a(x x
0
) + b(y y
0
) = 0
Vale decir que x = x x
0
, y = y y
0
es una soluci on de la ecuaci on
homogenea asociada:
a x + b y = 0 (6)
Por lo que podemos concluir que: toda solucion de la ecuaci on (no ho-
mogenea) (4) se puede escribir como la suma de una solucion particular
(x
0
, y
0
) mas una solucion ( x, y) de la ecuaci on homogenea (6):
Notas de

(x, y) = (x
0
, y
0
) + ( x, y)
Para encontrar entonces todas las soluciones de 4, nos falta entonces en-
contrar las soluciones de la ecuacion homogenea (6).
Supongamos primero que a y b fueran coprimos. En este caso, (6) implica
que:
a[ b y
b[a x
y como a y b son coprimos, por el corolario 5.3, deducimos que a[y y b[x.
Por lo tanto, existen s, t Z tales que:
x = bs, y = at
y entonces utilizando (6), vemos que:
abs + bat = 0 t = s
Concluimos que en el caso en que a y b son coprimos podemos concluir
que todas las soluciones de la ecuaci on homogenea son de la forma:
x = bs, y = as
y en consecuencia las de la no homogenea son:
x = x
0
+ bs, y = y
0
as
Continuacion del ejemplo: En el ejemplo anterior (5), todas las solu-
ciones enteras son de la forma:
x = 12 + 3s, y = 24 5s
Nos queda considerar el caso en que a y b no son coprimos. En este caso,
observamos que como d = mcd(a, b) divide a a, b y c por hip otesis, pode-
mos dividir ambos miembros de la ecuaci on por d, obteniendo una ecuaci on
equivalente:
a
x + b
y = c
(7)
Notas de

siendo a
= a : d, b
= b : d, c
= c : d.
Notamos que ahora a
y b
son coprimos: en efecto, por el teorema 5.2

existen enteros y tales que
a + b = d
y dividiendo ambos miembros de la ecuacion por d, resulta que:
a
+ b
= 1
y en consecuencia a
, b
son coprimos como armamos. Como (7) es equi-

valente a (4), el problema se reduce al caso ya considerado.
Corolario 7.1 Cuando d = mcd(a, b) divide a c, la ecuacion diofantica (4)
admite innitas soluciones enteras.
Ejercicio:(para pensar) Que sucede si consideramos una ecuaci on
diof antica en tres variables?
ax + by + cz = d
donde a, b, c, d Z. Cual sera el resultado an alogo al teorema (7.1) ?
Intentar demostrarlo. Sugerencia: el m aximo com un divisor entre a, b y c
puede calcularse de la siguiente manera:
mcd(a, b, c) = mcd(mcd(a, b), c)
(Es decir: el m aximo com un divisor es una operacion asociativa)
8. Ecuaciones de Congruencia
Un problema ntimamente relacionado con las ecuaciones diof anticas li-
neales, es la resoluci on de ecuaciones de congruencia lineales, de la forma:
ax b (m od n) (8)
o equivalentemente
a x = b en Z
n
Por ejemplo, consideramos la ecuaci on de congruencia:
Notas de

2x 3 (m od 5)
Entonces, haciendo una tabla de la funcion x 2x en Z
5
:
x 2x
0 0
1 2
2 4
3 1
4 3
vemos que la unica soluci on es x 4 (mod 5). Esta situaci on, no tiene
porque ocurrir en general: las ecuaciones de congruencia lineales pueden tener
varias soluciones o ninguna. Por ejemplo, consideremos la ecuaci on
2x 4 (m od 6)
entonces efectuando una tabla como antes de la funci on x 2x en Z
6
:
x 2x
0 0
1 2
2 4
3 0
4 2
5 4
vemos que esta ecuaci on posee dos soluciones no congruentes: a saber,
x 2 (mod 6) y x 5 (mod 6). Por otro lado, la misma tabla nos muestra
que la ecuci on de congruencia
2x 3 (m od 6)
no admite ninguna soluci on.
Obviamente, la resolucion de las ecuaciones de congruencia mediante una
tabla de restos como hemos hecho en estos ejemplos, solo resulta practicable
cuando el modulo es peque no. Por ello, resulta deseable desarrollar metodos
generales para resolver este problema.
Para ello, observemos que la ecuaci on de congruencia (8), signica que:
ax b = ny para alg un y Z
Notas de

o sea:
ax ny = b
y esta ultima ecuacion, es una ecuaci on diof antica lineal. Por lo tanto, pode-
mos resolverla por los metodos de la secci on anterior.
Ejemplo 1: Volvamos a la ecuaci on de congruencia:
2x 3 (m od 5)
Por lo que hemos dicho, esta ecuacion signica que:
2x 5y = 3 para alg un y Z (9)
Conforme a la teora que desarrollamos en la secci on anterior, como
mcd(2, 5) = 1, esta ecuaci on admite innitas soluciones enteras. Para econ-
trarlas, notamos que 1 se escribe como una combinaci on lineal de 2 y 5 en
la siguiente forma:
(2) 2 + (1) (5) = 1
luego
(6) 2 + (3) (5) = 3
y por lo tanto: x
0
= 6, y
0
= 3 es una soluci on particular de (9). Todas
las soluciones enteras, vendran entonces dadas por:
x = 6 + 5s y = 3 + 2s
En consecuencia, la soluci on de nuestra ecuaci on en congruencias ser a:
x 6 (m od 5)
o lo que es equivalente:
x 4 (m od 5)
(Notamos que el valor de la variable auxiliar y no interesa al resolver la
ecuaci on de congruencias).
Ejemplo 2: Volvamos a mirar ahora la ecuacion de congruencia:
2x 4(mod 6)
Notas de

Esta ecuacion de congruencia, conduce a la ecuacion diof antica lineal:
2x 6y = 4
Ahora los coecientes de la ecuacion no son coprimos, por ello dividimos
por su m aximo com un divisor (que es 2), la ecuaci on:
x 3y = 2
Despejando tenemos que,
x = 2 + 3y
y se obtiene una solucion para cada y Z.
Por lo tanto, la solucioes se determinan por la condici on
x 2 (m od 3)
Nos gustara expresar esta soluci on en terminos del m odulo 6, para ello
efectuamos la divisi on entera de y por 2, escribiendo
y = 2y
+ r
donde r = 0 o 1. Luego, sustituyendo:
x = 2 + 6y
+ 3r
o sea:
x 2 + 3r (m od 6)
Si r = 0 obtenemos la soluci on
x 2 (m od 6)
y si r = 1 obtenemos la soluci on:
x 5 (m od 6)
que son las que obtuvimos antes.
Ejemplo 3: Finalmente consideremos la ecuacion de congruencia:
2x 3 (m od 6)
Notas de

El metodo anterior conduce a la ecuaci on diof antica:
2x 6y = 3
y como mcd(2, 6) = 2 no divide a 3, concluimos conforme al teorema 7.1, que
no existe ninguna soluci on.
Ahora podemos generalizar los hechos que observamos en estos ejemplos,
en un teorema general:
Teorema 8.1 Sean a, b Z,n N y d = mcd(a, n). Consideramos la ecua-
cion de congruencia lineal:
ax b (m od n)
Entonces la ecuacion de congruencia lineal admite soluciones si y solo si d[b.
En ese caso existen exactamente d soluciones no congruentes modulo n.
Prueba: Como observamos antes, la ecuacion de congruencias del enunciado
es equivalente a la ecuaci on diofantica:
ax ny = b
y conforme al teorema 7.1, esta ecuaci on tiene soluci on si y solo si d =
mcd(a, n) divide a b.
Si esto sucede, llamando a
= a : d, n
= n : d, b
= b : d y dividiendo por
d, obtenemos la ecuaci on equivalente:
a
x n
y = b
donde ahora a
y b
son coprimos (como en la seccion anterior), y todas las

soluciones enteras de esta ecuaci on se pueden expresar en la forma:
x = x
0
+ n
s, y = y
0
a
s para alg un s Z
siendo (x
0
, y
0
) alguna soluci on particular. Por lo tanto, x ser a solucion de
nuestra ecuaci on de congruencia, si y s olo si
x x
0
(m od n
)
Notas de

Para expresar esto en terminos del m odulo n, como en el ejemplo anterior,
efectuamos la divisi on entera de s por d, escribiendo:
s = qd + r con 0 r < d
Entonces, sustituyendo obtenemos
x = x
0
+ nq + n
r
y las soluciones ser an
x x
0
+ n
r (m od n)
con r = 0, 1, 2, . . . , d 1.
Finalmente, observemos que estas soluciones no son congruentes m odulo
n, pues si
x x
0
+ n
r
1
x x
0
+ n
r
2
(m od n)
entonces
n
r
1
n
r
2
(m od n)
o sea:
n
r
1
n
r
2
= nk para alg un k Z
Luego multiplicando por d:
nr
1
nr
2
= dnk
o sea:
r
1
r
2
= dk
o
r
1
r
2
(m od d)
Pero como 0 r
1
, r
2
< d, concluimos que r
1
= r
2
.
Corolario 8.1 La ecuacion de congruencia lineal:
ax b (m od n)
tiene solucion unica si y solo si mcd(a, n) = 1.
Notas de

8.1. Inversos modulo n
Veamos otra forma de pensar las ecuaciones de congruencia que a veces
resulta util:
Si tenemos una ecuaci on lineal con n umeros
ax = b
(y a ,= 0), uno puede obtener la solucion multiplicando por el inverso multi-
plicativo de a, a
1
=
1
b
(lo que equivale a dividir por b), o sea:
x = b
1
a
Esto motiva el siguiente teorema
16
:
Teorema 8.2 Dados n N y a Z coprimo con n, existe una unica clase
a
en Z
n
tal que:
a a
= 1
Vale decir que:
aa
1 (m od n)
y dos posibles a
que cumplan esta condicion son congruentes modulo n.

a
se denomina un invereso multiplicativo de a modulo n.

Recprocamente si a admite un inverso multiplicativo en Z
n
, entonces a
es coprimo con n.
Este teorema es realmente el caso particular b = 1 del teorema 8.1.
En particular, notamos que si p es primo, en Z
p
todos los elementos no
nulos (que no sean la clase del cero), admiten un inverso multiplicativo (es
decir: se puede dividir por elementos no nulos
17
).
Ejercicio: Dar una demostracion directa
18
usando el teorema 5.2.
Ejemplo: Volvamos a mirar la congruencia lineal:
16
Este teroema signica que las clases a con a coprimo con n, son exactamente los
elementos que admiten un inverso multiplicativo en Z
n
, es decir las unidades del anillo
Z
n
17
Decimos entonces que si p es primo, Z
p
es un cuerpo, esto es un anillo en el que es
posible la division por elementos no nulos. Otros ejemplos familiares de cuerpos son Q (los
n umeros racionales) y R (los n ueros reales).
18
fue la que di en clase!
Notas de

2x 3 (m od 5)
Entonces dado que 2 y 5 con coprimos, el 1 se escribe como combinacion
lineal de ambos:
(2) 2 + 1 5 = 1
pero entones:
(2) 2 1 (m od 5)
Es decir que 2 y 2 = 3 son inversos multiplicativos en Z
5
. Entonces,
para pasar dividiendo el 2 en nuestra congruencia lineal, multiplicamos
ambos miembros de la congruencia por 3:
3 2x 3 3 (m od 5)
y obtenemos nuevamente que:
x 9 4 (m od 5)
8.2. El teorema de Wilson
Como aplicacion de las ideas anteriores, podemos probar el siguiente teo-
rema que proporciona un criterio para saber cuando un n umero es primo:
Teorema 8.3 (Teorema de Wilson) Sea p N, p > 1. Entonces p es
primo si y solo si p divide a (p 1)! + 1, o lo que es equivalente:
(p 1)! 1 (m od p)
Prueba: Primero probaremos que si p divide a (p 1)! + 1, entonces p
es primo. Supongamos que por el contrario p no fuera primo, estonces p
admitira un divisor d con 1 < d < p. Observemos que entonces d[(p 1)!
y como d divide a p, por transitividad tambien tenemos que d[(p 1)! + 1.
Pero entonces, d[[(p 1)! + 1] (p 1)! = 1, lo cu al es una contradicci on,
pues los unicos divisores de 1 son 1. En consecuencia, p debe ser primo.
Notas de

Ahora probemos que si p es primo, entonces (p 1)! 1 (mod p).
Para ello observemos que para cada n umero 1 a < p, existe en virtud del
teorema 8.2 un unico entero a
con 1 a
< p tal que:

aa
1 (m od p)
es decir, tal que a
y a son inversos modulo p.

Notamos adem as que debe ser a ,= a
, salvo si a = 1 o a = p 1. En
efecto: si a = a
, entonces
a
2
1 (m od p)
o tambien
a
2
1 0 (m od p)
Factorizando, podemos escribir esto como:
(a 1)(a + 1) 0 (m od p)
De lo cual en virtud del corolario 5.4, deducimos que:
a 1 (m od p) o a 1 (m od p)
Entonces, para calcular (p 1)! = 1 2 3 (p 1) m odulo p, agrupamos
cada factor con su inverso multiplicativo (usando las propiedades asociativa
y conmutativa del producto; ver ejemplo despues del teorema), y resulta:
(p 1)! (p 1) 1 (m od p)
Ejemplo: Para mostrar como funciona el proceso de agrupar cada n ume-

ro con su inverso multiplicativo m odulo p, veamos un ejemplo.
Sea p = 7. Entonces, tenemos la siguiente tabla de inversos modulo 7:
a a
1 1
2 4
3 5
4 2
5 3
7 7
Notas de

Entonces:
(p 1)! = 6! = 1 2 3 4 5 6 1 (2 4) (3 5) 6 6 1 (m od 7)
Ejercicio: Probar que si p es un primo impar, entonces
__
p 1
2
_
!
_
2
_
1 si p 1 (m od 4)
1 si p 3 (m od 4)
(m od p)
(Sugerencia: calcular (p1)! de otra manera agrupando cada n umero con
su inverso aditivo
19
m odulo p, vale decir agrupando a a con p a).
9. El teorema fundamental de la aritmetica
Ahora probaremos el teorema fundamental que ya hemos anunciado con
anterioridad:
Teorema 9.1 Cada entero n > 1, o bien es primo, o se descompone co-
mo producto de primos, y la descomposicion es unica, salvo el orden de los
factores.
Para ilustrar el teorema, obtengamos dos factorizaciones del n umero 360.
Un procedimiento posible, es ir dividiendo a 360 por los primos en orden de
magnitud, hasta obtener un 1:
360 2
180 2
90 2
45 3
15 3
5 5
1
Luego obtenemos la factorizaci on:
360 = 2 2 2 3 5 5
19
Dos n umeros a y a
son inversos aditivos modulo p si a + a
0 (mod p)
Notas de

Que sucede si hubieramos empezado dividiendo por otro primo? Por
ejemplo por 5:
360 5
72 3
24 3
8 2
4 2
2 2
1
Esto conduce la factorizaci on:
360 = 5 3 3 2 2 2
Pero ambas factorizaciones solo dieren en el orden de los factores, tal
como arma el teorema.
Ahora demostraremos el teorema:
Prueba: La existencia ya la probamos antes (teorema 2.1). Queda pues
probar la unicidad. Para ello, hagamos nuevamente inducci on global en n.
Para n = 1 el teorema no arma nada.
Sea entonces n > 1, y supongamos que el teorema es v alido para todo
n
< n.
Supongamos que n admite dos factorizaciones como producto de primos:
n = p
1
p
2
. . . p
r
= q
1
q
2
. . . q
s
siendo los p
i
y los q
i
primos (eventualmente alguna de las factorizaciones
puede constar de un solo primo).
Tomemos un primo en la factorizaci on de la izquierda, por ejemplo p
1
. En
virtud del corolario 5.5, deducimos que p
1
[q
i
para alg un i. Pero entonces como
q
i
es primo, p
1
= q
i
o p
i
= 1 (lo que es imposible pues 1 no es primo); es decir
que hemos probado que p
1
debe necesariamente aparecer en la factorizacion
de la derecha.
Podemos entonces. cancelar p
1
en ambos lados de la igualdad obteniendo
dos descomposiciones del n umero n
= n : p
1
como producto de primos:
n
= p
2
p
3
. . . p
r
= q
1
q
2
q
3
. . . q
i1
q
i+1
. . . q
s
Notemos que n
< n, entonces en virtud de la hip otesis inductiva, las dos

descomposiciones de n
s olo pueden diferir en el orden de los factores: es decir

Notas de

que r = s y los n umeros q
1
, q
2
, . . . , q
i1
, q
i+1
, . . . q
s
deben ser los mismos que
p
2
, p
3
, . . . p
r
, solo que en otro orden.
Deducimos entonces que las dos descomposiciones supuestas de n s olo
dieren en el orden de los factores.
En virtud del principio de induccion global, hemos demostrado el teorema
para todo n N.
Es importante notar que nuestra prueba del teorema fundamental de la
aritmetica, se bas o escencialmente en el corolario 5.4, el cu al a su vez lo
obtuvimos como una consecuencia del algoritmo de Euclides.
Ejercicio: Probar que recprocamente el teorema 9.1 implica el corolario
5.4, por lo que ambos resultados son en cierto modo equivalentes.
Una prueba alternativa
Una prueba alternativa del teorema fundmental, que no depende del al-
goritmo de Euclides, se puede hacer del siguiente modo
20
:
Prueba: Nuevamente, supongamos que n tiene dos factorizaciones
n = p
1
p
2
. . . p
r
= q
1
q
2
. . . q
s
y que ya hemos demostrado la unicidad de la factorizacion para cualquier
n
< n.
Podemos ordenar los primos que aparecen en cada factorizaci on de modo
que:
p
1
p
2
. . . p
r
q
1
q
2
. . . q
s
Claramente podemos suponer que p
1
q
1
. Adem as si fuera p
1
= q
1
, po-
demos cancelarlo en ambas descomposciones, obteniendo dos factorizaciones
para n
< n. Y usando la hip otesis inductiva, deducimos las dos n factoriza-

ciones de n coinciden salvo el orden de los factores.
Entonces, podemos suponer que p
1
< q
1
. Consideramos el entero:
n
= n p
1
q
2
. . . q
r
20
ver [1], suplemento al captulo I, seccion 1
Notas de

Este entero n
es menor que n y podemos escribirlo de dos maneras:

n
= p
1
(p
2
. . . p
s
q
2
. . . q
r
) = (q
1
p
1
)q
2
. . . q
s
Siendo, n
< n la factorizaci on de n
como producto de primos es unica,

por hip otesis inductiva. Y como p
1
es primo, deducimos entonces que o bien
p
1
= q
i
para alg un i con 2 i s, o bien p
1
[q
1
p
1
(por un razonamiento
similar al del ejercicio anterior).
En el primer caso, razonamos como antes, y deducimos que las dos fac-
torizaciones de n coinciden.
Por otra parte, si p
1
[q
1
p
1
, tenemos que: q
1
p
1
= p
1
k para alg un k Z,
lo que implica que q
1
= p
1
(k + 1), y q
1
no sera primo pues p
1
[q
1
.
Esta contradicci on prueba que n no puede tener dos factorizaciones dife-
rentes. En virtud del principio de inducci on global, el teorema queda demos-
trado para todo n N.
10. Consecuencias del Teorema Fundamental
de la aritmetica
Notemos que en la descomposicion dada por el teorema fundamental,
los primos pueden repetirse. Agrupando los primos que se repiten podemos
expresar a cada n umero n como productos de primos diferentes, elevados a
ciertas potencias, por ejemplo
360 = 2
3
3
2
5
1
Podemos si queremos incluir otros primos que no aparecen en esta facto-
rizaci on con exponente cero, ej:
360 = 2
3
3
2
5
1
7
0
11
0
Esto motiva la siguiente denicion:
Denici on 10.1 Si p es un n umero primo, denimos una funcion v
p
: N
N
0
, llamada la valuaci on p-adica del siguiente modo: v
p
(n) es el exponente
del primo p en la factorizacion en primos del n umero n en factores primos.
Ponemos v
p
(1) = 0 para todo primo p.
Notas de

Por ejemplo,
v
p
(360) =
_
_
3 si p = 2
2 si p = 3
1 si p = 5
0 si p ,= 2, 3, 5
Claramente la valuaci on p- adica esta bien denida, en virtud del teorema
fundamental de la aritmetica.
M as explicitamente podramos denir v
p
como el maximo exponente k tal
que p
k
divide a n:
v
p
(n) = maxk N
0
: p
k
[n
Entonces, la factorizacion de n podemos escribirla como
n =
pP,p|n
p
vp(n)
donde P es el conjunto de los n umeros primos, y el producto se extiende sobre
los primos que dividen a n.
A veces resulta util escribir esto formalmente como:
n =
pP
p
vp(n)
donde el producto se extiende ahora sobre todos los primos; y donde, si bien
el producto es formalmente innito, solo un n umero nito de factores son
diferentes de 1, por lo que es realmente un producto nito.
Observemos una propiedad importante de la valuaci on p- adica
21
:
Proposicion 10.1
v
p
(ab) = v
p
(a) + v
p
(b)
Prueba: Si las factorizaciones de a y b son:
a =
pP,p|a
p
vp(n)
21
Esta propiedad signica que la valuacion p-adica se comporta algebraicamente de
modo muy similar a un logaritmo: transforma productos en sumas.
Notas de

b =
pP,p|b
p
vp(n)
la de ab es
22
:
ab =
pP,p|a p|b
p
vp(a)+vp(b)
En consecuencia,
v
p
(ab) = v
p
(a) + v
p
(b)
Ejercicio: Probar que si a, b N, entonces:

v
p
(a + b) mn(v
p
(a), v
p
(b)
El teorema fundamental de la aritmetica nos permite dar un criterio para
saber cuando un n umero es divisible por otro en terminos de su factorizacion
en factores primos:
Teorema 10.1 Sean a, b N, entonces a[b si y solo si
v
p
(a) v
p
(b) para todo primo p P
Es decir: si y solo si todos los primos que aparecen en la factorizacion de a
aparecen en la de b, y el expoente con que aparecen es en la factorizacion de
a menor o igual que en la de b.
Prueba: Supongamos primero que a[b, entonces existe c N tal que b = ac,
y por el teorema anterior:
v
p
(b) = v
p
(a) + v
p
(c)
Pero v
p
(c) 0, luego v
p
(a) v
p
(b), como armamos.
Por otro lado si, v
p
(a) v
p
(b) para todo primo p y denimos:
c =
pP,p|b
p
vp(b)vp(a)
tendremos que c N (pues los exponentes son enteros no negativos) y, razo-
nando como en el teorema anterior, que ac = b. En consecuencia, a[b.
Este teorema tiene a su vez varias consecuencias importantes, por ejemplo
permite dar una caracterizacion del maximo com un divisor en terminos de
la factorizacion en primos:
22
En esta formula, simboliza el conectivo logico o (no exclusivo)
Notas de

Teorema 10.2 Si a, b N, el maximo com un divisor entre ellos, admite la
siguiente factorizacion:
mcd(a, b) =
pP,p|ap|b
p
mn(vp(a),vp(b))
Es decir, en la factorizacion de mcd(a, b) aparecen los primos que aparecen en
la de a y en la de b, y elevados al menor de los exponentes con que aparezcan
en ellas.
Prueba: Sea
d =
pP
p
mn(vp(a),vp(b))
N
Probaremos que d satiface la caracterizaci on del maximo com un divisor (co-
rolario 5.1):
i) Es un divisor com un: d[a y d[b.
ii) Cualquier otro divisor com un d
lo divide: si d
[a y d
[d, entonces d
[d.
Para probar que d[a, basta observar que para todo primo p P:
v
p
(d) = mn(v
p
(a), v
p
(b)) v
p
(a)
luego por el teorema 10.1, tenemos que d[a. Similarmente:
v
p
(d) = mn(v
p
(a), v
p
(b)) v
p
(b) p P
luego d[b. Supongamos ahora que d
es otro divisor com un: entonces

v
p
(d
) v
p
(a), v
p
(d
) v
p
(b)
luego para cualquier primo p,
v
p
(d
) mn(v
p
(a), v
p
(b)) = v
p
(d)
y en consecuencia, por el teorema 10.1 concluimos que d
[d. Como d satiface

la caracterizacion del maximo com un divisor, concluimos que d = mcd(a, b).
Una nocion dual de la de m aximo com un divisor es la de mnimo com un

m ultimo (m.c.m). Se tiene el siguiente an alogo del teorema 10.2:
Notas de

Teorema 10.3 Si a, b N, el mnimo com un m ultiplo entre ellos, admite la
siguiente factorizacion:
mcm(a, b) =
pP,p|ap|b
p
max(vp(a),vp(b))
Es decir, en la factorizacion de mcm(a, b) aparecen los primos que aparecen
en la de a o en la de b (donde el o es no exclusivo), y elevados al mayor
de los exponentes con que aparezcan en ellas.
Ejercicio: Efectuar la prueba de este teorema, probando que
m =
pP,p|ap|b
p
max(vp(a),vp(b))
satiface la siguiente caracterizaci on del mnimo com un m ultiplo
23
(dual del
corolario 5.1).
i) Es un m ultiplo com un: a[m y b[m.
ii) Cualquier otro m ultiplo m
es divisible por m: si a[m
y b[m
, entonces
m[m
.
Muchas propiedades del maximo com un divisor o del mnimo com un
m ultiplo se prueban facilmente a partir de esta caracterizacion:
Proposicion 10.2 Sean a, b, c N entonces:
i) mcd(ac, bc) = c mcd(a, b)
ii) mcm(ac, bc) = c mcm(a, b)
iii) mcd(a, b)mcm(a, b) = ab En particular, a y b son coprimos si y solo si
mcm(a, b) = ab.
23
Esta caracterizacion signica que mcm(a, b) es el supremo de a y b en el orden dado
por la divisibilidad
Notas de

Ejemplo: Sean a = 60 y b = 63. Tenemos las factorizaciones:
a = 2
2
3 5
b = 3
2
7
1
Entonces:
mcd(a, b) = 3
1
= 3
mcm(a, b) = 2
2
3
2
5
1
7
1
= 1260
y
ab = 2
2
3
3
5
1
7
1
= 3780 = 3 1260
En la prueba de la proposicion 10.2 necesitaremos utilizar ciertas propie-
dades del m aximo y el mnimo de dos n umeros naturales m, n N
0
:
1.
mn(m + k, n + k) = mn(m, n) + k m, n, k N
0
(10)
2.
m ax(m + k, n + k) = max(m, n) + k m, n, k N
0
(11)
3.
mn(m, n) + max(m, n) = n + m m, n N
0
(12)
Estas propiedades se comprueban sin dicultad, considerando separada-
mente los casos en que n > m y en que n m.
Prueba: Para demostrar una igualdad entre dos n umeros naturales, como
la armacion i):
mcd(ac, bc) = c mcd(a, b)
basta demostrar que todo primo p aparece en ambos miembros elevado al
mismo exponente, o sea que:
v
p
(mcd(ac, bc)) = v
p
(c mcd(a, b)) p P (13)
Notas de

Pero por el teorema 10.2, y la propiedad (10):
v
p
(mcd(ac, bc)) = mn(v
p
(ac), v
p
(bc))
= mn(v
p
(a) + v
p
(c), v
p
(b) + v
p
(c)) = mn(v
p
(a), v
p
(b)) + v
p
(c)
Por otra parte, utilizando nuevamente el teorema 10.2:
v
p
(c mcd(a, b)) = v
p
(c) + v
p
(mcd(a, b)) = v
p
(c) + mn(v
p
(a), v
p
(b))
Esto demuestra (13), y en consecuencia i). La prueba de la armaci on ii) es
completamente similar, y se deja como ejercicio. Finalmente, para probar la
igualdad iii), nuevamente bastar a probar que:
v
p
(mcd(a, b)mcm(a, b)) = v
p
(ab) p P (14)
Pero teniendo en cuenta la propiedad (12):
v
p
(mcd(a, b)mcm(a, b)) = v
p
(mcd(a, b)) + v
p
(mcm(a, b))
= mn(v
p
(a), v
p
(b)) + max(v
p
(a), v
p
(b)) = v
p
(a) + v
p
(b)
y por otra parte,
v
p
(ab) = v
p
(a) + v
p
(b)
lo que demuestra la armaci on (14), y en consecuencia iii).
Similarmente podemos demostrar otras propiedades, por ejemplo:
Proposicion 10.3 Si a, b N son tales que a
n
[b
n
, entonces a[b.
Prueba: Para ver que a[b basta ver que:
v
p
(a) v
p
(b)
pero como por hipotesis, a
n
[b
n
, tenemos que:
v
p
(a
n
) v
p
(b
n
)
o sea:
nv
p
(a) nv
p
(b)
y en consecuencia:
v
p
(a) v
p
(b)
Notas de

Ejercicio: El teorema 10.1 tambien puede emplearse para determinar la

cantidad de divisores de un n umero. Denamos d(n) como la cantidad de
divisores positivos de n. Probar que entonces,
d(n) =
p|n
(v
p
(n) + 1)
Otras consecuencias del teorema fundamental de la aritmetica, nos ser an
m as utiles mas adelante:
Proposicion 10.4 Sean a, b, c N. Si a[c, b[c, y a y b son coprimos, enton-
ces ab[c.
Prueba: Por el teorema 10.1, notamos que basta probar que:
v
p
(ab) v
p
(c) p P (15)
Pero
v
p
(ab) = v
p
(a) + v
p
(b)
Observemos que como a y b son coprimos, para cualquier primo p, ser a v
p
(a) =
0 o v
p
(b) = 0.
Si v
p
(a) = 0, entonces v
p
(ab) = v
p
(b) v
p
(c) pues b[c. Si v
p
(b) = 0,
entonces v
p
(ab) = v
p
(a) v
p
(c) pues a[c En cuqlquier caso, hemos probado
que se verica (15), en consecuencia ab[c.
11. El teorema de Fermat
Teorema 11.1 (Fermat) Sean p un n umero primo y a Z. Entonces:
i)
a
p
a (m od p)
ii) Si p no divide a a entonces,
a
p1
1 (m od p)
Notas de

Observemos ante todo, que las dos armaciones del enunciado, son equi-
valentes:
Para probar que i) implica ii), basta observar i) puede escribirse la forma:
a a
p1
a 1
Entonces, siendo p primo, si p no divide a a, p es coprimo con a, y podemos
cancelarlo en ambos miembros de la congruencia (por la proposici on 6.4).
Recprocamente es claro que ii) implica i), ya que basta multiplicar ambos
miembros de la congruencia por a.
Daremos dos pruebas diferentes de este teorema. La primera prueba se ba-
sa en el binomio de Newton, y en un argumento de inducci on. (Mas adelante,
veremos una generalizacion de este teorema que nos proporcionar a tambien
otra prueba diferente).
Recordamos que el binomio de Newton arma que:
(a + b)
p
=
p
k=0
_
p
k
_
a
k
b
pk
El siguiente lema arma que p divide a todos los coecientes binomiales
salvo los de los extremos:
Lema 11.1 Si p es primo, y 1 < k < p entonces
_
p
k
_
0 (m od p)
Prueba: Recordamos que:
_
p
k
_
=
p(p 1)(p 2) . . . (p k + 1)
k!
N
En consecuencia:
p[k!
_
p
k
_
Pero como k < p, los factores primos de k! deben ser exclusivamente primos
menores que p, por lo tanto p es coprimo con k!, y por el corolario 5.3,
concluimos que p[
_
p
k
_
.
Notas de

Corolario 11.1 Si a, b Z y p es primo, entonces:
(a + b)
p
a
p
+ b
p
(m od p)
Ahora resulta sencillo probar el teorema 11.1:
Prueba: Ya observamos que i) y ii) son equivalentes, luego basta probar i).
Para hacerlo hagamos induccion en a. Si a = 0 el teorema es evidente:
0
p
= 0 0 (m od p)
Si el teorema vale para un cierto a, veremos que se verica tambien para
a + 1: en efecto por el corolario 11.1
(a + 1)
p
a
p
+ 1
p
(m od p)
y usando la hip otesis inductiva, deducimos que:
(a + 1)
p
a + 1 (m od p)
En virtud del principio de inducci on, el teorema queda demostrado para
cualquier a N
0
. Si a < 0, notemos que a > 0 luego usando lo que ya
demostramos:
(a)
p
= (1)
p
a
p
a (m od p)
pero (1)
p
1 (mod p) tanto si p es un primo impar como si p = 2 (en
este caso 1 1). Por lo tanto
a
p
a (m od p)
Una observacion sobre la demostraci on anterior: En realidad el

teorema de Fermat puede pensarse como teorema sobre clases en Z
p
, que
arma que si a Z
p
y p es primo,
a
p
= a en Z
p
Ahora en Z
n
(n primo o no), vale una forma mas fuerte del principio de
inducci on: si P es una propiedad de las clases en Z
n
tal que:
1. P(a
0
) para alg un a
0
Z
n
Notas de

2. Si P(a) es verdadera, entonces P(a + 1) es verdadera:
entonces P(a) es verdadera para cualquier a Z
n
.
Ejercicio: Justicar porque en Z
n
se verica esta forma del principio de
inducci on.
Teniendo en cuenta esta observacion en la demostraci on anterior, no es
realmente necesario considerar el caso a < 0.
Nota historica:
Figura 1: Pierre de Fermat
Pierre de Fermat (1601-1665) fue un jurista (en el parlamento de Toulouse, en
el sur de Francia) y destacado matematico.
Ademas de haber obtenido importantes resultados en teora de n umeros, es uno
de los fundadores de la geometra analtica (contemporaneo de Descartes, conci-
bio independientemente de el, su principio fundamental), el calculo innitesimal y
el calculo de probabilidades (a traves de su correspondencia con Blaise Pascal).
El teorema 11.1 (conocido como el peque no teorema de Fermat) aparece en
una de sus cartas a su condente Frenicle de Bessy, fechada el 18 de octubre de
1640.
Fermat es tambien famoso por otro teorema (en realidad conjetura, ya que no
dio una demostracion), conocido como el ultimo teorema de Fermat, que arma
que si n > 2 la ecuacion diofantica
x
n
+ y
n
= z
n
no admite soluciones enteras con x, y, z no nulas. Este teorema fue formulado
por Fermat en un comentario en el margen que escribio mientras lea la aritmetica
de Diofanto. Fermat dijo tener una demostracion notable de esta armacion pero
que el margen era demasiado peque no para escribirla.
Pese a tratarse de un enunciado elemental, los intentos de demostrar este teo-
rema por numerosos matematicos de la talla de Euler, Dedekind, Legendre, Lame,
Notas de

Kummer, etc. fueron infructuosos (aunque lograron demostrar casos particulares,
y estas investigaciones condujeron al desarrollo de nuevas teoras matematicas de
gran importancia en la matematica actual, como la teora algebraica de n umeros
y las curvas elpticas). Finalmente, en 1995 Andrew Wiles dio una demostracion
de un teorema que implica el ultimo teorema de Fermat (pero esta demostracion
no es para nada elemental).
12. El Teorema Chino del Resto
Comencemos con una proposici on sobre congruencias respecto a m odulos
que son primos entre s.
Proposicion 12.1 Sean m
1
, m
2
N dos n umeros coprimos, a, b Z y m =
m
1
m
2
. Entonces a b (m od m) si y solo si se tiene simultaneamente que:
_
a b (m od m
1
)
a b (m od m
2
)
(16)
Prueba: Primero supongamos que a b (m od m) Entonces, como m
1
[m y
m
2
[m, por la obseraci on 6.1, deducimos que se satisface (16). Recprocamente
supongamos que se satisface (16) entonces, m
1
[b a y m
2
[b a. Dado que
m
1
y m
2
son coprimos, por la proposici on 10.4, deducimos que m
1
m
2
[b a,
es decir que a b (m od m)
Ejemplo: Para ilustrar la utilidad de la proposicion anterior, veamos
un an alogo del teorema de Fermat, para congruencias respecto a un modulo
compuesto de la forma n = pq, donde p y q son primos distintos.
Si ni p ni q dividen a a, tendremos en virtud del teorema de Fermat:
a
p1
1 (m od p)
a
q1
1 (m od q)
En consecuencia, elevando la primer congruencia a la potencia q 1, y la
segunda a la potencia p 1, tendremos que:
a
(p1)(q1)
1 (m od p)
a
(p1)(q1)
1 (m od q)
Notas de

y en virtud de la proposici on 12.1, tendremos que:
a
(p1)(q1)
1 (m od pq)
Esta congruencia puede considerarse como analoga al teorema de Fer-
mat, para el modulo compuesto n = pq. Volveremos sobre este ejemplo m as
adelante.
Ahora consideremos un sistema de congruencias respecto a dos m odulos
que son coprimos, por ejemplo:
_
x 2 (mod 3)
x 4 (mod 5)
(17)
Ser a posible reducirlo a una unica congruencia m odulo 3 5 = 15?.
Veremos que la respuesta a esta pregunta es armativa. Para ello, notemos
que el sistema (17) signica que existen q
1
, q
2
Z tales que:
_
x = 3q
1
+ 2
x = 5q
2
+ 4
Comenzamos multiplicando la primer ecuaci on por 5 y a la segunda por
3 (para que aparezca 15 como factor ):
_
5x = 15q
1
+ 10
3x = 15q
2
+ 12
Ahora notemos lo siguiente: como los m odulos 3 y 5 son coprimos, por el
teorema 5.2 (consecuencia del algoritmo de Euclides) existen enteros , Z
tales que:
3 + 5 = 1
De hecho, utilizando el algoritmo de Euclides, es f acil ver que podemos
tomar = 2 y = 1. Multiplicando entonces a la primera ecuaci on por
y a la segunda por , tenemos que:
_
5x = 15q
1
+ 10
3x = 15q
2
+ 12
y sumandolas obtenemos que:
(5 + 3)x = 15(q
1
+ q
2
) + (10 + 12)
Notas de

o sea, teniendo en cuenta la manera en que hemos elegido y ,
x = 15(q
1
+ q
2
) + (10 + 12)
Pero entonces:
x 10 + 12 = 14 (m od 15)
Recprocamente, si x 14 (mod 15), entonces
_
x 14 4 (m od 5)
x 14 2 (m od 3)
Por lo que vemos que el sistema (17) es equivalente a la congruencia
x 14 (m od 15)
Ahora generalizaremos este ejemplo, en un teorema general:
Teorema 12.1 (Teorema Chino del resto) Consideramos el sistema de
congruencias:
_
x a
1
(m od m
1
)
x a
2
(m od m
2
)
(18)
donde a
1
, a
2
Z, m
1
, m
2
N y, m
1
y m
2
son coprimos. Entonces existe un
a Z tal que el sistema (18) es equivalente a la congruencia:
x a (m od m) donde m = m
1
m
2
Prueba: Procedemos como en el ejemplo anterior: Notamos que el sistema
(18) signica que existen q
1
, q
2
Z tales que:
_
x = q
1
m
1
+ a
1
x = q
2
m
2
+ a
2
Por otra parte, como m
1
y m
2
son coprimos, por el corolario 5.2 (conse-
cuencia del algoritmo de Euclides), existen , Z tales que:
m
1
+ m
2
= 1 (19)
Notas de

Entonces multiplicando a la primer ecuacion por m
2
y a la segunda por
m
1
, deducimos que:
_
m
2
x = q
1
m
1
m
2
+ m
2
a
1
m
1
x = q
2
m
1
m
2
+ m
1
a
2
y sumando estas ecuaciones, tenemos que:
(m
2
+ m
1
)x = (q
1
+ q
2
)m
1
m
2
+ (m
2
a
1
+ m
1
a
2
)
o teniendo en cuenta la forma en que elegimos y :
x = (q
1
+ q
2
)m
1
m
2
+ (m
2
a
1
+ m
1
a
2
)
Llamando a a
a = m
2
a
1
+ m
1
a
2
esta ecuacion implica que:
x a (m od m) (20)
donde m = m
1
m
2
.
As pues hemos probado que cualquier solucion de (18) es una soluci on
de (20).
Recprocamente, vamos a probar que cualquier solucion de (20), es una
soluci on de (18). Para ello notemos primero que a satisface que:
_
a a
1
(m od m
1
)
a a
2
(m od m
2
)
(21)
Para verlo notemos que por la denici on de a:
_
a m
2
a
1
(m od m
1
)
a m
1
a
2
(m od m
2
)
pero por (19) tenemos tambien que:
_
m
2
1 (mod m
1
)
m
1
1 (mod m
2
)
(o sea que m
2
y son inversos m odulo m
1
, y del mismo modo m
1
y
son inversos modulo m
2
)
Notas de

Utilizando entonces la propiedad multiplicativa de las congruencias po-
demos concluir que se verica (21) (lo que dice que a es una soluci on de
18).
Cualquier otra solucion x de (18), vericar a entonces (por transitividad
de la relaci on de congruencia) que:
_
x a (m od m
1
)
x a (m od m
2
)
y entonces por la proposicion 12.1, tendremos que:
x a (m od m)
Esto demuestra que (18) y (20) son equivalentes.
Hagamos algunas observaciones sobre la demostraci on anterior: en primer
lugar notemos que la demostracion es constructiva (o sea: no s olo armamos
que el a del enunciado existe, sino que damos un metodo para encontrarlo,
ya que y pueden encontarse utilizando el algoritmo de Euclides. Por otra
parte, notemos que a es unica como clase de Z
m
(esto es: dos posibles valores
de a son congruentes modulo m).
El teorema chino puede genrealizarse facilmente a sistemas de mas de dos
congruencias:
Ejemplo: Consideremos el sistema
_
_
_
x 2 (mod 3)
x 4 (mod 5)
x 1 (mod 7)
(22)
formado por las dos congruencias del ejemplo anterior, m as una tercera
congruencia. Nuestro objetivo es encontrar una congruencia m odulo 105 =
3 5 7 que sea equivalente al sistema (22).
Notemos que en el ejemplo anterior vimos que las dos primeras congruen-
cias eran equivalentes a la congruencia:
x 14 (m od 15)
Sustituyendo, vemos que (22) es equivalente a
_
x 14 (mod 15)
x 1 (m od 7)
Notas de

Como nuevamente 15 y 7 son coprimos, podemos volver a aplicarle el
teorema chino a este sistema. Nuevamente buscamos y , tales que:
15 + 7 = 1
Encontramos que = 1, = 2 y procediendo como en la demostracion del
teorema 12.1, encontramos que a = 181, es decir que el sistema (22), es
equivalente a la unica congruencia:
x 181 (m od 105)
Generalizando este ejemplo, podemos dar un enunciado del teorema chino
del resto para sistemas de un n umero arbitrario de congruencias:
Teorema 12.2 (Teorema Chino del resto, version general) Consideramos
el sistema de congruencias:
_
_
x a
1
(m od m
1
)
x a
2
(m od m
2
)
. . .
x a
k
(m od m
k
)
(23)
donde a
i
Z, m
i
N y, m
i
y m
j
son coprimos si i ,= j (1 i, j
k). Entonces existe un a Z tal que el sistema (23) es equivalente a la
congruencia:
x a (m od m) donde m = m
1
m
2
. . . m
k
Ejercicio: Efectuar la prueba de este teorema, por induccion en el n umero
k de ecuaciones (imitando el procedimiento del ejemplo anterior)
A. La funcion de Euler y el teorema de Fermat-
Euler
Vimos en el teorema 8.2 que las clases a donde a es coprimo con n, tienen
un importante papel en la aritmetica de Z
n
, a saber son exactamente las
clases que admiten un inverso multiplicativo.
Notas de

Por ello, conviene que estudiemos en m as detalle el conjunto formado por
estas clases
24
. Introduzcamos una notaci on para este conjunto:
Z
n
= a Z
n
: a es coprimo con n
Notemos que ser coprimo con n es realmente una propiedad de la clase
a (y no solo del n umero a) pues si b pertenece a la misma clase en Z
n
que a,
es decir que b a (m od n) entonces a es coprimo con n si y s olo si b lo es.
Prueba: Si suponemos que a es coprimo con n y b a (mod n), entonces
existe q Z tal que b = qn + a. Luego si d[b y d[n, tedremos que d[a. Pero
como a es coprimo con n, y d es un divisor com un de ambos, debe ser d = 1.
En consecuencia b es coprimo con n.
Notemos que como cada n umero es congruente modulo n con alguno de
los n umeros 0, 1, 2, . . . , n 1 podemos describir Z
n
de modo un poco m as
explcito como:
Z
n
= a Z
n
: 0 a n 1, a es coprimo con n
Una observaci on importante es que el conjunto Z
n
es cerrado para el
producto en Z
n
ya que si a y b son coprimos con n, ab tambien lo es
25
.
Denimos tambien una funci on : N N (conocida como la indicatriz
de Euler), del siguiente modo: (n) es la cantidad de elementos de Z
n
, o lo
24
Los temas de este apendice son extras al programa de la materia, sin embargo cons-
tituyen una aplicacion y continuacion natural de la teora que venimos desarrollando, y
la funcion de Euler (n) que introducimos en en esta seccion tambien es importante en
coneccion con las raices primitivas de la unidad (tema que veremos mas adelante).
25
Observamos que Z
n
verica tres propiedades importantes:
1. Es cerrado para el producto
2. El producto tiene un elemento neutro (la clase 1 del 1) tal que:
a 1 = 1 a = a
3. Cada elemento a Z
n
posee un inverso multiplicativo a
(teorema 8.2) tal que

a a
= a
a = 1
Se dice entonces que el conjunto Z
n
tiene estructura de grupo respecto a la operacion de
producto modulo n denida en el.
Notas de

que es equivalente: (n) cuenta cu antos de los n umeros 0, 1, 2, . . . , n 1 son
coprimos con n.
Veamos algunos ejemplos:
Ejemplo 1 consideremos por ejemplo n = 6. Entonces:
Z
6
= 0, 1, 2, 3, 4, 5
y
Z
6
= 1, 5
En particular, (6) = 2.
Ejemplo 2: Si n = 15 = 3 5, para determinar (15) y los elementos
de Z
15
podemos proceder del siguiente modo: escribimos los n umeros del 0
al 14:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
Suprimos los que son m ultiplos de 3:
1, 2, 4, 5, 7, 8, 10, 11, 13, 14
y suprimamos los que son m ultiplos de 5:
1, 2, 4, 7, 8, 11, 13, 14
Los n umeros que nos han quedado son coprimos con 15, en consecuencia:
Z
15
= 1, 2, 4, 7, 8, 11, 13, 14
y (15) = 8. Este ejemplo muestra que el valor de (n) depende de c omo
sea la factorizaci on en primos del n umero n.
Ejemplo 3: Si p es primo, los unicos n umeros que no son coprimos con
p son los que son divisibles por p (que corresponden a la clase del cero 0), en
consecuencia:
Z
p
= 1, 2, . . . , p 1
y por lo tanto (p) = p 1.
Ejemplo 4: Si tenemos que n = pq, donde p y q son dos primos distintos,
podemos proceder como en el caso del 15, del siguiente modo: escribamos los
n umeros:
Notas de

0, 1, 2, . . . , n 1
y tachemos los que son m ultiplos de p: son exactamente q n umeros. Luego
tachemos los m ultiplos de q: son exactamente p n umeros. Pero hay exacta-
mente un n umero (el cero) que hemos tachado dos veces. En consecuencia:
en total nos quedan sin tachar:
pq q p + 1
n umeros. Este es el valor de
26
(n) = pq p q + 1 = (p 1)(q 1)
.
Notemos que en este caso se cumple que:
(pq) = (p)(q)
Esto motiva la siguiente propiedad que nos permitir a calcular en general
el valor de (n), en terminos de su factorizaci on en primos:
Teorema A.1 Si m
1
y m
2
son coprimos, entonces:
(m
1
) = (m
1
)(m
2
)
Para probar este teorema, necesitamos un lema sobre los sistemas de
congruencias que hemos considerado en el teorema chino del resto:
Lema A.1 Sean m
1
, m
2
N coprimos, y consideremos el sistema de con-
gruencias:
_
x a
1
(m od m
1
)
x a
2
(m od m
2
)
como en el teorema chino del resto (teorema 12.1). Entonces si a es la unica
solucion de este sistema modulo m (dada por el teorema chino), tenemos que:
a es coprimo con m, si y solo si a
1
es coprimo con m
1
y a
2
es coprimo con
m
2
.
26
Un argumento combinatorio similar puede utilizarse para determinar el valor de (n)
en general, por medio de la llamada formula de inclusiones y exclusiones, ver por ejemplo
[3], captulo V, seccion 2.
Notas de

Prueba: Supongamos primero que a es coprimo con m. Entonces, conforme
al teorema 8.2, a admite un inverso m odulo m. Es decir: existe un a
Z tal
que:
aa
1 (m od m)
En consecuencia, tendremos que:
aa
1 (mod m
1
)
aa
1 (mod m
2
)
y por lo tanto
a
1
a
1 (mod m
1
)
a
2
a
1 (mod m
2
)
pero esto, justamente dice que a
1
admite un inverso m odulo m
1
, por lo que
a
1
debe ser coprimo con m
1
; y del mismo modo, a
2
admite un inverso m odulo
m
2
, por lo que a
2
debe ser coprimo con m
2
. (de nuevo usando el teroema 8.2).
Para probar el recproco, supongamos que a
1
es coprimo con m
1
y que
a
2
es coprimo con m
2
. En consecuencia (nuevamente por el teorema 8.2), a
1
admite un inverso a
1
m odulo m
1
, y a
2
admite un inverso a
2
m odulo m
2
, o
sea existen a
1
, a
2
Z tales que:
a
1
a
1
1 (mod m
1
)
a
2
a
2
1 (mod m
2
)
Consideramos entonces el sistema de congruencias:
_
x a
1
(m od m
1
)
x a
2
(m od m
2
)
Conforme al teorema chino, este sistema admite una unica soluci on a
m odulo
m, o sea existe un a
in Z tal que:
_
a
1
(m od m
1
)
a
2
(m od m
2
)
(y dos a
posibles son congruentes m odulo m). Entonces tendremos que:

_
aa
a
1
a
1
1 (m od m
1
)
aa
a
2
a
2
1 (m od m
2
)
y por lo tanto:
aa
1 (m od m)
Notas de

Pero esto dice que a admite un inverso m odulo m, y en consecuencia a es
coprimo con m (teorema 8.2).
Ahora estamos en condiciones de probar el teorema A.1:
Prueba: Sea m = m
1
m
2
. Queremos calcular (m), es decir la cantidad de
elementos de Z
m
.
Denamos para ello una funcion f : Z
m
1
Z
m
2
Z
m
del siguiente modo:
dadas dos clases a
1
Z
m
1
, a
2
Z
m
2
, denimos f(a
1
, a
2
) como la unica
soluci on a m odulo m, del sistema de congruencias:
_
a a
1
(m od m
1
)
a a
2
(m od m
2
)
(24)
dada por el teorema chino del resto (teorema 12.1). Conforme al lema an-
terior (lema A.1), f est a bien denida (si a
1
Z
m
1
y a
2
Z
m
2
, efectivamente
tenemos que a Z
m
).
M as explcitamente, teniendo en cuenta la demostracion del teorema chino,
podemos denir f del siguiente modo: sean , Z tales que m
1
+m
2
= 1,
entonces:
f(a
1
, a
2
) = m
2
a
1
+ m
1
a
2
(clase en Z
m
)
Por otra parte, la que la clase de un a Z en Z
m
, determina a que clase
pertenece en Z
m
1
y Z
m
2
(proposici on 12.1). En consecuencia, f admite una
funci on inversa dada por:
f
1
(a en Z
m
) = (a en Z
m
1
, a en Z
m
2
)
Dado que f admite una funcion inversa, f es una biyecci on entre Z
m
1

Z
m
2
y Z
m
. En consecuncia, ambos conjuntos tienen la misma cantidad de
elementos, o sea justamente:
(m
1
)(m
2
) = (m)
Ejemplo: Veamos como funciona la demostracion anterior en el caso en

que m
1
= 3 y m
2
= 5. En este caso:
Z
3
= 1, 2, Z
5
= 1, 2.3.4
y podemos tomar = 2, = 1, de modo que:
Notas de

f(a
1
en Z
3
, a
2
en Z
5
) = 5a
1
+ 6a
2
en Z
15
La tabla de los valores de f es:
f(1, 1) = 1 f(2, 1) = 4 = 11
f(1, 2) = 7 f(2, 2) = 4 = 2
f(1, 3) = 13 f(2, 3) = 8
f(1, 4) = 19 = 4 f(2, 4) = 14
de modo que efectivamente f es una biyeccion entre Z
3
Z
5
y Z
15
.
Denici on A.1 Una funcion (aritmetica
27
) f : N Z (o mas generalmente
f : N C) tal que
f(mn) = f(m)f(n) si m, n son coprimos
se denomina multiplicativa. El teorema anterior arma que la funcion de
Euler es multiplicativa.
Observamos que si f es multiplicativa, es facil probar por induccion en la
cantidad de factores k que:
f(m
1
m
2
. . . m
k
) = f(m
1
)f(m
2
) . . . f(m
k
)
si los factores m
i
son coprimos dos a dos (es decir si m
i
es coprimo con m
j
para 1 i j, i ,= j).
Ejercicio: Sea P(x) = a
0
+a
1
x+. . . +a
k
x
k
un polinomio con coecientes
enteros (a
i
Z). Sea para cada n in Z, N
P
(n) el n umero de soluciones m odulo
n de la congruencia:
P(x) 0 (m od n)
probar que N
P
es una funci on multiplicativa.
La importancia del teorema (A.1) radica en que nos permitir a calcular
facilmente el valor de (n) para cualquier n a partir del conocimiento de los
valores (p
k
) de para las potencias de los primos.
27
Suele denominarse funciones aritmeticas a las que tienen como dominio al conjunto de
n umeros naturales N, ya que en muchos ejemplos como la funcion de Euler, f(n) expresa
alguna propiedad aritmetica del n umero n.
Notas de

Supongamos por ejemplo que queremos calcular (360). La factorizaci on
de 360 como producto de primos es:
360 = 2
3
3
2
5
1
entonces:
(360) = (2
3
) (3
2
) (5
1
) = (2
3
2
2
)(3
2
3
1
)(5 1) = 4 6 4 = 96
Podemos enunciar esto como un teorema general:
Teorema A.2 Para todo n N, tenemos que:
(n) = n
p|n
_
1
1
p
_
donde el producto se extiende sobre los divisores primos de n.
Prueba: Consideremos la factorizacion de n como producto de primos:
n =
p|n
p
vp(n)
Notamos que las potencias de primos diferentes son coprimas entre s. En-
tonces, dado que es multiplicativa:
(n) =
p|n
(p
vp(n)
) =
p|n
_
p
vp(n)
p
vp(n)1
_
=
p|n
p
vp(n)
_
1
1
p
_
=
_
_
p|n
p
vp(n
_
_
_
_
_
p|n
_
1
1
p
_
_
_
_
=
= n
p|n
_
1
1
p
_
Notemos que la misma idea de la prueba de este teorema muestra que en

general, si una funcion es multiplicativa, para calcular su valor en cualquier
entero, basta saber hacerlo en las potencias de los primos.
Una de las razones por las que la funcion de Euler resulta importante
es porque interviene en la siguiente generalizaci on de Euler del teorema de
Fermat, para el caso de m odulos no primos:
Notas de

Teorema A.3 (Fermat-Euler) Si n N y a Z es coprimo con n, en-
tonces
a
(n)
1 (m od n)
Ejermplo 1: Si n = p es primo, (p) = p 1, y se obtiene el teorema de
Fermat.
Ejemplo 2: Si n = pq, siendo p y q primos distintos, entonces (n) =
(p 1)(q 1) y obtenemos el resultado del ejemplo que vimos al comienzo
de la secci on 12.
Prueba: Para demostrar el teorema de Fermat-Euler, consideramos la fun-
ci on f : Z
n
Z
n
dada por
f(x) = a x = ax
Armamos que f es una biyeccion. En efecto, como a es coprimo con n,
por hip otesis; a tiene un inverso a
en Z
m
(teorema 8.2). En consecuencia f
admite una inversa dada por:
f
1
(y) = a
y = a
y
(porque la operacion inversa de multiplicar por a, es multiplicar por su inverso
a
, que funciona como dividir por a).

En consecuencia, como f admite una inversa, f es una biyeccion. Se sigue
que si
Z
n
= x
1
, x
2
, . . . , x
k
(todos elementos distintos)
siendo k = (n), deducimos que
f(x
1
), f(x
2
), . . . , f(x
k
)
los son mismos elementos de Z
n
, en otro orden (pues una biyecci on no hace
m as que permutar los elementos de un conjunto).
Deducimos que si los multiplicamos todos, tendremos que:
k
i=1
x
i
=
k
i=1
f(x
i
) en Z
n
o sea:
k
i=1
x
i

k
i=1
(ax
i
) (m od n)
Notas de

Agrupando las a que aparecen como factores en el segundo miembro, tenemos
que:
k
i=1
x
i
a
k
_
k
i=1
x
i
_
(m od n)
o llamando
x =
k
i=1
x
i
tenemos que:
x a
k
x (m od n)
Pero como x es coprimo con n, podemos cancelarlo y deducir que:
a
k
= a
(n)
1 (m od n)
Otra propiedad notable de la funcion de Euler es la siguiente:

Teorema A.4 Para todo n N,
d|n
(d) = n (25)
La suma en este teorema se extiende sobre todos los divisores positivos
de n. Sumas de este tipo aparecen con frecuencia en la teora de n umeros.
Para demostrar este teorema, probaremos primero dos lemas que son de
interes independiente:
Lema A.2 Sea m = m
1
m
2
donde m
1
, m
2
N son coprimos. Entonces cada
divisor d N de m se puede escribir de manera unica en la forma d =
d
1
d
2
donde d
1
[m
1
, d
2
[m
2
y d
1
es coprimo con m
2
y d
2
es coprimo con m
1
.
Recprocamente todo divisor de m es de esta forma.
Prueba: Si d[m consideramos su descomposici on en factores primos:
d =
p|d
p
vp(d)
Notas de

y observamos que los primos que dividen a d deben ser algunos de los que
dividen a m. Pero cada primo que divide a m, debe dividir a m
1
o a m
2
(y
ambas cosas no pueden suceder simultaneamente). Luego podemos clasicar
los primos que aparcen en la factorizaci on de d en los que dividen a m
1
y los
que divide a m
2
, y escribir a d como d = d
1
d
2
siendo
d
1
=
p|dp|m
1
p
vp(d)
d
2
=
p|dp|m
2
p
vp(d)
Como para cualquier primo p que divida a m
1
tenemos que:
v
p
(d
1
) = v
p
(d) v
p
(m) = v
p
(m
1
)
deducimos que d
1
[m
1
, por el teorema 10.1. Similarmente, d
2
[m
2
Finalmen-
te, es claro que d
1
y d
2
son coprimos, pues no comparten factores primos.
Recprocamente si d = d
1
d
2
donde d
1
[m
1
y d
2
[m
2
, entonces d
1
[m
1
m
2
y
d
2
[m
1
m
2
. Por lo tanto, d
1
d
2
[m
1
m
2
= m, en virtud de la proposicion 10.4.
Corolario A.1 La funcion d(n) que cuenta el n umero de divisores

28
(posi-
tivos) de n es multiplicativa.
Lema A.3 Sea f : N Z (o mas generalmente, f : N C) una funcion
aritmetica. Si f es multiplicativa, y denimos:
g(n) =
d|n
f(d)
entonces g es as mismo multiplicativa.
Prueba: Sen m
1
, m
2
N coprimos, y sea m = m
1
m
2
entonces por el lema
A.2 tenemos que:
g(m) =
d|m
f(m) =
d
1
|m
1
d
2
|m
2
f(d
1
d
2
)
28
Introdujimos esta funcion en un ejercio de la seccion 10. Este corolario puede utilizarse
para resolver dicho ejercicio de otra manera.
Notas de

Como f es multiplicativa, vemos que esta suma es igual a
d
1
|m
1
d
2
|m
2
f(d
1
)f(d
2
) =
_
_
d
1
|m
1
f(d
1
)
_
_
_
_
d
2
|m
2
f(d
2
)
_
_
= g(m
1
)g(m
2
)
Ahora resulta f acil demostrar el teorema A.4:

Prueba: Consideremos la funcion
g(d) =
d|n
(d)
Como es multiplicativa, por el lema A.3, g es multiplicativa. En conse-
cuencia: para calcular g(n) en cualquier n N, basta saber hacerlo cuando
n = p
k
con p primo.
Pero si n = p
k
, los divisores (positivos) de n son de la forma p
j
con
0 j k, y resulta:
g(p
k
) =
k
j=0
(p
j
) = 1 +
k
j=1
(p
j
p
j1
)
Desarroll ando esta suma:
g(p
k
) = 1 + (p 1) + (p
2
p) + . . . + (p
k
p
k1
)
vemos que cada termino se cancela con el siguiente, salvo p
k
(suma telesc opi-
ca) y resulta que g(p
k
) = p
k
.
En general, dado n N, si su factorizaci on en primos es
n =
p|n
p
vp(n)
como g es multiplicativa, tendremos que:
g(n) =
p|n
g
_
p
vp(n)
_
=
p|n
p
vp(n)
= n
Ejercicio: Sean f, g : N C funciones aritmeticas, y denamos una

nueva funci on h : N C por:
Notas de

h(n) =
d|n
f(d)g
_
n
d
_
Probar que si f y g son multiplicativas, entonces h tambien lo es.
Ejercicio: Una funci on aritmetica muy emparentada con es la funcion
de Mobius denida del siguiente modo:
(n) =
_
_
_
1 si n = 1
0 si si n es divisible por el cuadrado de alg un primo
(1)
k
si n = p
1
p
2
. . . p
k
siendo los p
i
primos distintos
Por ejemplo, (12) = 0, (15) = 1, (30) = 1.
Probar las siguientes propiedades de :
1. es multiplicativa.
2.
d|n
(d) =
_
1 si n = 1
0 si n > 1
3.
(n) =
d|n
(d)
n
d
=
d|n
d
_
n
d
_
(26)
(Sugerencia: desarrollar el producto del teorema A.2, usando la propie-
dad distributiva).
4. (Formula de inversion de M obius) Si f : N C es una funcion aritmeti-
ca, y g : N C est a dada por:
g(n) =
d|n
f(d)
entonces, f se puede expresar en terminos de g de la siguiente manera:
f(n) =
d|n
g(d)
_
n
d
_
=
d|n
g
_
n
d
_
(d)
Notas de

B. El orden de un entero m odulo n
Denici on B.1 Sea a Z
n
. Denimos el orden (multiplicativo) de a en Z
n
(o el orden de a Z modulo n, siendo a coprimo con n), como el menor
expoente d N tal que
a
d
= 1 en Z
n
o lo que es lo mismo:
a
d
1 (m od n)
Observaci on B.1 En virtud del teorema de Fermat-Euler (y del principio
del mnimo entero), d esta bien denido, y se tiene que d (n).
Teorema B.1 Sea a Z
n
. Entonces la sucesion de las potencias
a
0
= 1, a, a
2
, a
3
, . . . , a
k
, . . . ,
(en Z
n
) es perodica, con perodo d, siendo d el orden de a modulo n. Es
decir que se verica que:
a
i
a
j
(m od n)
s y solo si
i j (m od d)
En particular, se tiene que
a
i
1 (m od d)
si y solo si d[i, y en consecuencia d debe ser un divisor de (n).
Prueba: Podemos suponer claramente que i j. Si i j (m od d), enton-
ces: i j = kd para alg un k N
0
. Luego:
a
i
= a
ij
a
j
= (a
d
)
k
a
j
a
j
(m od n)
Recprocamente si,
a
i
a
j
(m od n)
tendremos que:
a
ij
a
j
a
j
(m od n)
Notas de

y como a
j
es coprimo con n, por hip otesis, podremos cancelarlo, en esta
congruencia: obteniendo que:
a
ij
1 (m od n)
Efectuemos la divisi on entera de i j por d, de modo que:
i j = qd + r con 0 r < d
Si fuera r ,= 0, tendremos que:
a
ij
= (a
q
)
d
a
r
a
r
(m od n)
y consecuentemente:
a
r
1 (m od d)
Pero 1 r < d, contradiciendo la denici on de d. Consecuentemente, debe
ser r = 0, es decir que d[i j, o sea que:
i j (m od d)
Referencias
[1] R. Courant, H. Robbins, Que es la matem atica?. Editorial Aguilar,
1964. (suplemento al captulo primero)
[2] G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers,
4ta. Edicion,
[3] J.V. Upspensky, M. A. Heaslet. Elementary Number Theory. Mc Gaw
Hill, New York, 1939.
[4] I. Vinogradov, Fundamentos de la Teora de los N umeros, Editorial Mir.
Mosc u, 1977.
[5] W. Stein, Elementary Number Theory (disponible en la pagina web de
su autor, http://sage.math.washington.edu/ent/ ).
[6] J.P. Pinasco, New Proofs of Euclids and Eulers Theorems American
Mathematical Monthly, 116 (2009) 172174.
Notas de

Agradecimiento: Quiero agradecer a todos los colegas y alumnos que
aportaron correcciones o comentarios sobre estas notas; especialmente a Jorge
Guccione.

Aritmetica de Numeros Enteros

Cargado por

Copyright:

Formatos disponibles

Aritmetica de Numeros Enteros

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Aritmetica de Numeros Enteros

Cargado por

Copyright:

Formatos disponibles

Aritmetica de N umeros Enteros

Si a[b y b[a (siendo a, b ,= 0) entonces a = b.

< q. Pero q no es divisible por ninguno de los

< r, esto contradice el hecho de

, con sus correspondientes restos r y r

, y entonces por (1),

tenemos lo que queremos. Si r

(que son el mismo n umero) deben coincidir, es decir

r < n, tenemos que

r debe ser el resto (y q

q el cociente) en la divisi on enterea de b a

< r, la prueba es analoga pues b a (m od n))

Z. Pero en virtud del teorema 5.2, existen , Z tales que:

es una solucion particular de la ecuacion

Ejemplo: consideremos la ecuacion diof antica

son coprimos: en efecto, por el teorema 5.2

son coprimos como armamos. Como (7) es equi-

son coprimos (como en la seccion anterior), y todas las

que cumplan esta condicion son congruentes modulo n.

se denomina un invereso multiplicativo de a modulo n.

< p tal que:

y a son inversos modulo p.

Ejemplo: Para mostrar como funciona el proceso de agrupar cada n ume-

son inversos aditivos modulo p si a + a

< n, entonces en virtud de la hip otesis inductiva, las dos

s olo pueden diferir en el orden de los factores: es decir

< n. Y usando la hip otesis inductiva, deducimos las dos n factoriza-

es menor que n y podemos escribirlo de dos maneras:

como producto de primos es unica,

Ejercicio: Probar que si a, b N, entonces:

es otro divisor com un: entonces

[d. Como d satiface

Una nocion dual de la de m aximo com un divisor es la de mnimo com un

es divisible por m: si a[m

Ejercicio: El teorema 10.1 tambien puede emplearse para determinar la

Una observacion sobre la demostraci on anterior: En realidad el

(teorema 8.2) tal que

posibles son congruentes m odulo m). Entonces tendremos que:

Ejemplo: Veamos como funciona la demostracion anterior en el caso en

Notemos que la misma idea de la prueba de este teorema muestra que en

, que funciona como dividir por a).

Otra propiedad notable de la funcion de Euler es la siguiente:

Corolario A.1 La funcion d(n) que cuenta el n umero de divisores

Ahora resulta f acil demostrar el teorema A.4:

Ejercicio: Sean f, g : N C funciones aritmeticas, y denamos una

También podría gustarte