N umeros Enteros

Teresa Krick

Departamento de Matematica, FCEyN, UBA e IMAS, CONICET

1 Hechos generales
El conjunto de los n umeros enteros es :
= { . . . , 3, 2, 1, 0, 1, 2, 3, . . . } = {0} (donde := { n; n }).
Una de las razones de la necesidad de trabajar con estos n umeros es que en no se puede restar
(en general), y as se obtiene a partir de agregando los n umeros negativos. Mencionemos
que en la operacion + cumple las siguientes propiedades, que le dan una estructura de Grupo
Conmutativo :
Para todo o, / , o + / .
Conmutatividad : Para todo o, / , o + / = / + o .
Asociatividad : Para todo o, /, c , (o + /) + c = o + (/ + c) (y por lo tanto, se puede
escribir o + / + c sin aclarar que se suma primero).
Existencia de Elemento Neutro : Existe un elemento en ( unico) que es el 0 , que verica
que para todo o , o + 0 = o .
Existencia de Opuesto : Para todo o , existe un ( unico) elemento, que es o , tal que
o + (o) = 0 .
La razon por la que se le da un nombre a los conjuntos con una operacion que verica las 5
propiedades mencionadas, es que se observo que hay muchsimos conjuntos que, junto con una
operacion, verican esas propiedades (por ejemplo, con la suma, , , ,
2
, [A] , . . . ) y
entonces, a n de estudiar las consecuencias de esas propiedades, conviene hacerlo de una vez por
todos en el caso abstracto general y luego aplicarlo en cada caso en lugar de estudiarlas para cada
conjunto en particular.
En tambien se puede multiplicar : la operacion cumple propiedades parecidas a +, aunque
no todas :
Para todo o, / , o / .
Conmutatividad : Para todo o, / , o / = / o .
Asociatividad : Para todo o, /, c , (o /) c = o (/ c)(= o / c = o / c) .

Notas correspondientes a la parte de Enteros de la materia Algebra 1 de la Facultad de Ciencias Exactas

y Naturales, Universidad de Buenos Aires, con el apoyo de los subsidios UBACyT X-198 y CONICET 2461/01.
Version revisada en el a no 2011, con el apoyo de los subsidios CONICET PIP 2008-2011 y FonCyT PICT 2010.
1
Existencia de Elemento Neutro : Existe un elemento en ( unico) que es el 1 , que verica
que para todo o , 1 o = o .
No hay Existencia de Inverso multiplicativo : Los unicos elementos inversibles o de para
el producto, o sea que verican que existe o
1
de manera que o o
1
= 1 son el 1 y el
1 .
La propiedad siguiente relaciona el producto con la suma:
Distributividad del producto sobre la suma : Para todo o, /, c , o (/ + c) = o / + o c .
Estas propiedades de la suma y el producto en hacen que tenga una estructura de Anillo
Conmutativo (estructura que conviene estudiar en general por las mismas razones que conviene
estudiar la de Grupo).
Recordemos otras propiedades que ya conocemos de o tambien de subconjuntos de :
es un conjunto inductivo, que contiene estrictamente a y para el cual no vale as nomas
el principio de induccion ya que no tiene primer elemento por el cual empezar la induccion.
Si jamos n
0
, en
n
0
:= {: ; : n
0
} vale el principio de induccion empezando en
n
0
. Por ejemplo en
0
:= {0} vale el principio de induccion.
Equivalentemente,
n
0
y
0
son conjuntos bien ordenados, o sea, cualquier subconjunto no
vaco de
n
0
o
0
tiene primer elemento o mnimo (un elemento en el subconjunto menor
o igual que todos los demas).
2 Divisibilidad
El hecho que los n umeros enteros no son divisibles (con cociente entero) por cualquier otro n umero
entero hace interesante estudiar la nocion y consecuencias de la divisibilidad. (Este estudio no se
justica por ejemplo de la misma manera en o donde todo n umero racional o real es divisible
(con cociente racional o real) por cualquier otro n umero racional o real no nulo.)
Denicion 2.1 (Divisibilidad)
Sean o, c con c = 0 . Se dice que c divide a o (o que o es divisible por c , o que o es
m ultiplo de c ) si existe un elemento / tal que o = / c (o sea si el cociente
o
t
es un n umero
entero).
Se nota c o (con una barrra vertical, no confundir con la barra del cociente , ). O sea:
c o
def
/ : o = / c.
En caso contrario, se dice que c no divide a o , y se nota c o . Eso es cuando el cociente
o
t
, ,
o sea no existe ning un entero / tal que o = / c .
El conjunto de los divisores positivos y negativos de un entero o se notara por 1i (o) y el de los
divisores positivos por 1i
+
(o) .
(Nota : en algunos libros no se excluye el caso c = 0 pero se conviene que 0 divide unicamente al
0 . Igualmente en este curso excluiremos el caso c = 0 para no dividir por 0 .)
Ejemplos
7 56 pues 56 = 8 7 .
2
7 56 , 7 56 , 7 56 .
7 54 .
1i (12) = { 12, 6, 4, 3, 2, 1, 1, 2, 3, 4, 6, 12 } y 1i
+
(12) = { 1, 2, 3, 4, 6, 12 } .
1i (1) = { 1, 1 } .
Ejemplos generales
Todo n umero entero c = 0 satisface que c 0 pues 0 = 0 / (aqu / = 0 ). As el 0 tiene
innitos divisores : 1i (0) = {0} .
c o c o (pues o = / c o = (/) (c) ).
De la misma manera c o c o c o .
Se concluye que c o c o (donde r denota el modulo o valor absoluto de r).
En particular a cada divisor negativo de o le corresponde un divisor positivo.
Si o = 0 , c o = c o (pues o = /c con o = 0 implica / = 0 tambien, y mas a un,
/ 1 ; por lo tanto, o = /c c ).
En particular, todo n umero entero o no nulo tiene solo un n umero nito de divisores, todos
pertenecientes al conjunto
{ o, . . . , 1, 1, . . . , o }.
O sea 1i
+
(o) { 1, . . . , o } .
Ademas, por la observacion del inciso anterior, el n umero total de divisores de o es el doble
del n umero de divisores positivos.
c o y o c o = c (pues o = / c y c = , o implica que o = (/ ,) o , por lo tanto
/ y , son dos n umeros enteros que satisfacen / , = 1 , o sea, / = 1 ).
Para todo o , se tiene 1 o y 1 o , y tambien o o y o o .
As, si o = 1 , o tiene por lo menos 4 divisores distintos ( 1, o ), o 2 divisores positivos
distintos ( 1, o ).
Hay n umeros enteros que tienen unicamente esos 4 divisores, que son los asegurados, otros
tienen mas. Esto motiva la separacion de los n umeros enteros (distintos de 0 , 1 y 1 ) en
dos categoras, la de los n umeros primos y la de los n umeros compuestos :
Denicion 2.2 (N umeros primos y compuestos)
Sea o , o , { 1, 0, 1 } .
Se dice que o es primo sii o tiene unicamente 4 divisores (o 2 divisores positivos). Por
ejemplo 2, 3, 5, 7, 11, 13, . . . .
(En general los n umeros primos se notan con las letras j , ,. . . )
Se dice que o es compuesto sii o tiene mas que 4 divisores (o mas que 2 divisores positivos).
Por ejemplo 4, 6, 8, 9, 10, . . . .
Se observa que o es compuesto si y solo si tiene un divisor positivo / que satisface 2
/ o 1 (pues ya vimos que 1i
+
(o) { 1, . . . , o } y si o tiene mas que 2 divisores
positivos, tiene que haber uno en alg un lugar en el medio).
3
Mas adelante, se trabajara mucho mas con los n umeros primos, que cumplen propiedades impor-
tantsimas, y constituyen los ladrillos de base para construir todos los n umeros, en el sentido que
cualquier n umero entero (distinto de 0 y 1 ) se escribe en forma unica como producto de primos
positivos (salvo el signo).
Se ver an ahora algunas propiedades importantes de la divisibilidad :
Propiedades 2.3 Sean o, /, c , c = 0 .
c o y c / = c o + / .
(Pues si o = / c y / = , c con /, , , entonces o + / = (/ + ,) c , donde / + , .)
c o y c / = c o / .
c o + / no implica que c o y c / : Por ejemplo, 6 4 + 8 pero 6 4 y 6 8 .
Sin embargo si c o + / y se sabe que c o , entonces c / .
(Pues c (o + /) o .)
c o = c / o, / .
c o = c
2
o
2
y c
n
o
n
, n .
(Pues si o = / c , entonces o
2
= /
2
c
2
y o
n
= /
n
c
n
.)
c o / no implica c o o c / : Por ejemplo, 6 3 4 pero 6 3 y 6 4 .
Veremos mas adelante que la propiedad c o / c o o c / se cumple cuando c es un
n umero primo (es la propiedad mas importante que cumplen los n umeros primos). Si c no
es primo, siempre se pueden econtrar o y / tales que c o / pero c o y c / . Quienes?
Ejemplos
Hallar todos los o , o = 1 , tales que o 1 o
2
+ 5 .
Para resolver esto, se trata de poner a la derecha del smbolo un n umero jo, de manera
de trabajar despues con los divisores de ese n umero. Para ello se puede usar por ejemplo
que se sabe que o 1 o 1 , por lo tanto o 1 / (o 1) (para todo / ) y en particular
o 1 (o + 1)(o 1) . As se tiene o 1 o
2
+ 5 y o 1 o
2
1 , por lo tanto o 1
divide a la diferencia, es decir o 1 6 . Es decir o 1 { 1, 2, 3, 6 } . Por lo tanto
o { 5, 2, 1, 0, 2, 3, 4, 7 } , y se concluye vericando que para cada valor de ese conjunto es
cierto que o1 o
2
+5 , o bien vericando y mostrando que en realidad todas las implicaciones
usadas son equivalencias.
Probar que para todo o , o = 1 , y para todo n vale que o 1 o
n
1 .
Esto ya se puede hacer a este nivel de distintas formas (despues veremos otra incluso) :
Usando la Serie Geometrica :
n1

.=0
o
.
=
o
n
1
o 1
Por lo tanto
o
n
1 = (o 1)
n1

.=0
o
.
y dado que la sumatoria da un n umero entero (pues es una suma de potencias de enteros)
resulta que o 1 o
n
1 .
4
Usando el Binomio de Newton :
o
n
= ((o 1) + 1)
n
=
n

.=0
(
n
i
)
(o 1)
.
= 1 + n(o 1) +
(
n
2
)
(o 1)
2
+ + (o 1)
n
Por lo tanto
o
n
1 = (o 1)
(
n +
(
n
2
)
(o 1) + + (o 1)
n1
)
= / (o 1)
donde / es la sumatoria que esta dentro del gran parentesis.
Por induccion en n. La proposicion es j(n) : o 1 o
n
1
j(1) es Verdadera pues o 1 o 1 .
j() Verdadera = j( + 1) Verdadera :
HI : o 1 o

1 . Se quiere probar que o 1 o

+1
1 .
Pero o
+1
1 = o(o

1)+(o1) , y por HI, o1 o

1 , y por otro lado, o1 o1 ,

por lo tanto o 1 divide a la suma, como se quera probar.
(Las dos primeras tienen la ventaja sobre la ultima de dar tambien la expresion del cociente,
y la primera es la mas sencilla.)
Sean :, n . Probar que si : n, entonces para todo o = 1 , o
n
1 o
n
1 .
Se tiene n = / :, luego o
n
= (o
n
)
|
. Si ponemos := o
n
, por el inciso anterior se tiene
que 1
|
1 , es decir o
n
1 o
n
1 .
3 Congruencia
Se introduce ahora una notacion debida a Carl Friedrich Gauss (17771855), conocido como el
Prncipe de los matematicos, y reconocido historicamente como uno de los dos o tres gigantes de la
Matematica universal. La notacion facilita mucho la forma de escribir y trabajar con los n umeros
enteros y la divisibilidad.
Denicion 3.1 (Congruencia)
Sean o, /, c con d = 0 . Se dice que o es congruente a / modulo c sii d o / .
Se nota o / (mod c) o tambien o / (c) . O sea:
o / (mod c)
Jc}
c o /.
En caso contrario se nota o / (mod c) o o / (c) .
Ejemplos
5 3 (mod 2) , 5 1 (mod 2) , 5 1 (mod 2) , 5 2 (mod 2) , 4 0 (mod 2) ,
/ , 2/ 0 (mod 2) y 2/ + 1 1 (mod 2) .
13 8 (mod 5) y 13 3 (mod 5) .
Sean o, c con c = 0 . Entonces o 0 (mod c) c o .
5
Sean /, :, c con c = 0 , entonces / c + : : (mod c) .
Sea c con c = 0 . Se vera ahora que la relacion de congruencia modulo c en es una relacion
de equivalencia en , por lo tanto parte el conjunto de los n umeros enteros en subconjuntos de
elementos que son todos congruentes entre s, y que son por lo tanto de alguna manera considerados
iguales bajo ese concepto.
Proposicion 3.2 Sea c {0} . Sea la relacion en dada por
o / o / (mod c).
Entonces es una relacion de equivalencia.
Prueba.
Reexividad : Para todo o , o o (mod c) pues c o o .
Simetra : Hay que probar que para todo o, / tales que o / (mod c) , entonces / o
(mod c) . Pero o / (mod c) signica que c o / , y por lo tanto c (o /) = / o ,
luego / o (mod c) .
Transitividad : Hay que probar que para todo o
1
, o
2
, o
3
tales que o
1
o
2
(mod c) y
o
2
o
3
(mod c) entonces o
1
o
3
(mod c) . Pero o
1
o
2
(mod c) signica que c o
1
o
2
,
y o
2
o
3
(mod c) signica que c o
2
o
3
. Por lo tanto c (o
1
o
2
) + (o
2
o
3
) , o sea
c o
1
o
3
, es decir o
1
o
3
(mod c) .
La proposicion anterior signica que se dividen los n umeros enteros en subconjuntos de elementos
congruentes entre s, que se identican de esa manera. Por ejemplo si se toma congruencia
modulo 2, quedan por un lado los pares (que son todos congruentes entre s y tambien congruentes
a 0 modulo 2), y por otro lado los impares (que son congruentes entre s y congruentes a 1 modulo
2). Cuando se toma congruencia modulo 3, queda subdividido en 3 subconjuntos : los que son
de la forma 3 / , / , por un lado, por otro lado los que son de la forma 3 / + 1 y por ultimo
los que se escriben como 3 / + 2 . Mas adelante se vera el Algoritmo de Division, y se vera que la
congruencia modulo c clasica (e identica) los n umeros enteros seg un su resto modulo c .
A continuacion, se enuncian propiedades de la congruencia, que son muy utiles para trabajar :
Propiedades 3.3 Sea c {0} . Entonces :
o
1
/
1
(mod d) y o
2
/
2
(mod c) = o
1
+ o
2
/
1
+ /
2
(mod c) .
(Pues c o
1
/
1
y c o
2
/
2
= c (o
1
/
1
) + (o
2
/
2
) = (o
1
+ o
2
) (/
1
+ /
2
) .)
De la misma manera, se puede probar por induccion que para todo n :
o
1
/
1
(mod c), . . . , o
n
/
n
(mod c) = o
1
+ + o
n
/
1
+ + /
n
(mod c).
o / (mod c) y / = / o / / (mod c) .
o
1
/
1
(mod c) y o
2
/
2
(mod c) = o
1
o
2
/
1
/
2
(mod c) .
(Para probar esto se puede usar por ejemplo el item anterior y la transitividad : como o
1
/
1
(mod c) , entonces o
1
o
2
/
1
o
2
(mod c) (multiplicando por o
2
), y por otro lado, como
o
2
/
2
(mod c) , se tiene /
1
o
2
/
1
/
2
(mod c) (multiplicando por /
2
), y nalmente por
transitividad, se concluye que o
1
o
2
/
1
/
2
(mod c) .)
6
Por induccion, se obtiene :
o
1
/
1
(mod c), . . . , o
n
/
n
(mod c) = o
1
o
n
/
1
/
n
(mod c).
Tomando en los items anteriores o
1
, . . . , o
n
todos iguales a un mismo n umero o y /
1
, . . . , /
n
todos iguales a un mismo n umero / , se obtiene :
o / (mod c) = o
2
/
2
(mod c) y en general o
n
/
n
(mod c), n .
Las dos propiedades siguentes permiten reemplazar el modulo por un divisor o un m ultiplo:
o / (mod c) y d c = o / (mod d),
o / (mod c) y / = 0 / o / / (mod / c).
La primera vale pues si d c y c o / , entonces d o / . Pero observemos que la recproca
no es cierta en general, es decir o / (mod d) y d c no implica que o / (mod c) . Por
ejemplo 10 3 (mod 7) y 7 14 pero 10 3 (mod 14) .
La segunda armacion es un si y solo si pues c o / / c / o / / .
Resumimos las dos propiedades mas importantes por ahora:

o
1
/
1
(mod c)
.
.
.
o
n
/
n
(mod c)
=
{
o
1
+ + o
n
/
1
+ + /
n
(mod c)
o
1
o
n
/
1
/
n
(mod c)
Aplicaciones
Retomamos el ejemplo anterior : n , o {1} , vale o 1 o
n
1 :
Se tiene que o 1 (mod o 1) pues o 1 o 1 , por lo tanto o
n
1
n
(mod o 1) , es
decir, o 1 o
n
1 .
Para todo n
0
, 64 49
n
+ 16n 1 :
Se probara por induccion en n, combinado con congruencia.
j(n) : 64 49
n
+ 16n 1
j(0) es Verdadera como antes.
j() Verdadera = j( + 1) Verdadera :
HI : 64 49

+ 16 1 , o sea 49

16 + 1 (mod 64) .
Se quiere probar que 64 49
+1
+ 16( + 1) 1 .
Por HI, 49
+1
= 49 49

49 (16 + 1) (mod 64) .

Por lo tanto, 49
+1
+ 16( + 1) 1 49 (16 + 1) + 16( + 1) 1 (mod 64) .
Distribuyendo y factorizando, resulta : 49
+1
+16(+1)1 4816+64 (mod 64) . Pero
64 0 (mod 64) (pues 64 64 ) y 48 16 0 (mod 64) (pues 64 48 16), por lo tanto
4816+64 0+0 (mod 64) , y, de nuevo por transitividad, resulta 49
+1
+16(+1)1 0
(mod 64) , o sea 64 49
+1
+ 16( + 1) 1 como se quera probar.
Se concluye que 64 49
n
+ 16n 1 para todo n .
7
4 Algoritmo de division
Vamos a enunciar y demostrar ahora el bien conocido algoritmo de division entera.
Teorema 4.1 (Algoritmo de division)
Dados o, c con c = 0 , existen /, : que satisfacen
o = / c + : con 0 : < c.
Ademas, / y : son unicos en tales condiciones.
Se dice que / es el cociente y : es el resto de la division de o por c ( o es el dividendo y c el
divisor). Al resto : tambien lo notaremos :
t
(o) para distinguir que es el resto de o al dividir
por c .
Antes de pasar a la demostracion, hagamos algunos ejemplos:
Ejemplos
o = 1038, c = 14 :
1038 = 74 14 + 2 = / = 74, : = :
14
(1038) = 12 ya que 0 2 < c.
o = 1038, c = 14 :
1038 = 74 14+2 = (74) (14) +2 = / = 74, : = :
14
(1038) = 2 ya que 0 2 < c.
o = 1038, c = 14 :
1038 = 74 14 + 2 = 1038 = 74 14 2 pero 2 < 0.
Hay que corregirlo, se hace restando y sumando el (modulo del) divisor 14 :
1038 = (74 14 14) + (14 2) = 75 14 + 12 = / = 75, : = :
14
(1038) = 12
ya que 0 12 < c .
o = 1038, c = 14 :
1038 = 74 14 + 2 = 1038 = 74 (14) 2 pero 2 < 0.
Se corrige nuevamente como arriba restando y sumando el modulo del divisor 14 :
1038 = (74 (14) 14) + (14 2) = 75 (14) + 12 = / = 75, : = :
14
(1038) = 12
ya que 0 12 < c .
La conclusion como veremos en la demostracion del teorema es que para saber dividir n umeros
positivos o negativos por divisores positivos o negativos, alcanza saber hacerlo para n umeros y
divisores positivos y luego corregir cociente y/o resto en cada caso.
Prueba del Teorema 4.1.
El teorema consta de dos armaciones, la parte existencial, que requiere mostrar que existen /
y : en las condiciones del teorema, y luego la unicidad: mostrar que no puede haber dos pares
distintos de cociente y resto para o y c dados.
Existencia: Vamos a probar primero en detalle el caso o 0, c 0 , ya que, como nos sugieren los
ejemplos, los otros casos se reducen a ese.
8
Caso o 0, c 0 :
Aqu, c = c . La idea intuitiva es considerar los elementos o , o c , o 2c , o 3c , ...
hasta que caigamos en algun elemento menor que c pero a un mayor o igual que cero. Este
sera el resto. Formalizamos esta idea de la manera siguiente:
Sea el subconjunto de
0
:= {0} formado por los n umeros de la forma o , c para
alg un , , es decir:
= { o , c, , }
0
.
Claramente es un subconjunto de
0
que no es vaco ya que o = o 0 c pertenece a
(estamos considerando el caso o 0 ).
Luego, el conjunto tiene un mnimo. Llamemos : a ese mnimo. Se tiene que : por
un lado, y por otro lado : es menor que todos los demas elementos de .
Como : , existe un elemento natural o cero, llamemoslo / , que satisface que : = o/ c ,
o sea o = / c + : .
Falta probar que 0 : < c (ya que c = c en el caso que estamos considerando):
Claramente : 0 ya que pertenece a que es un subconjunto de
0
.
Si : fuese mayor o igual que c , entonces : c 0 a un. Luego se tendra que el elemento
: c = o / c c = o (/ +1) c esta tambien en el conjunto pero es menor que : ! Eso
contradice que : sea el mnimo. As, se concluye que no puede ocurrsir que : c , luego
: < c .
Caso o 0, c < 0 :
En este caso, c 0 (y por lo tanto c = c ) y se tiene que por el caso anterior, existen
/

, :

tal que o = /

(c) + :

con 0 :

< c . Se obtiene directamente o = (/

) c + :

,
luego / = /

, : = :

.
Caso o < 0 :
En este caso, tenemos o 0 , y de los casos anteriores existen /

, :

tal que o = /

c +:

con 0 :

< c . Luego o = (/

) c :

.
Si :

= 0 , :

cumple la condicion de resto y se obtiene / = /

, : = :

= 0 .
Pero si :

= 0 , hay que corregirlo restando y sumando c a la expresion:

o = (/

) c :

= ((/

) c c) + (c :

).
As, si se dene / := /

1 seg un si c < 0 o c 0 , y : := c :

, se tiene o = / c + :
con 0 < : < c , ya que
0 < :

< c = c < :

< 0 = c c < c :

< c 0 = 0 < : < c.

Unicidad: Supongamos que tenemos dos pares de cocientes y restos, / y : , y /

y :

. Vamos a
probar que entonces / = /

y : = :

.
Sin perdida de generalidad, podemos suponer que : :

, y luego:
o = / c + : = /

c + :

con 0 : :

< c.
As, (/ /

) c = :

: c :

: c :

: . Como :

: 0 por ser :

: , si :

: = 0 ,
se tiene, por lo que vimos en divisibilidad, que c :

: . Pero es facil vericar que, dado que

9
:

< c , :

: < c : < c (ya que : 0 ). Luego no puede ser :

: = 0 , es decir tiene que

ser :

= : .
Se concluye que (/ /

) c = 0 y como c = 0 , / /

= 0 , es decir / = /

tambien.
Observacion 4.2 Si 0 o < c , entonces o = 0 c + o implica / = 0 y : = :
t
(o) = o pues
o cumple la condicion que tiene que cumplir el resto (se aplica la unicidad del cociente y el resto).
La observacion siguiente relaciona el algoritmo de division con la divisibilidad (y la congruencia).
Es inmediata pero esencial:
Observacion 4.3 Sean o, c con c = 0 . Entonces
:
t
(o) = 0 c o o 0 (mod c).
Vamos a generalizar esa observacion y clasicar los n umeros seg un su resto:
Proposicion 4.4 (Congruencia y restos)
Sean o, /, c, :, :
1
, :
2
con c = 0 . Entonces
1. o :
t
(o) (mod c) .
2. o : (mod c) con 0 : < c = : = :
t
(o) .
3. :
1
:
2
(mod c) con 0 :
1
, :
2
< c = :
1
= :
2
.
4. o / (mod c) :
t
(o) = :
t
(/) .
Prueba.
1. o = / c + :
t
(o) c o :
t
(o) o :
t
(o) (mod c) .
(Se usa aqu que existen el cociente y el resto.)
2. o : (mod c) c o : o : = / c para alg un / o = / c + : .
Pero la condicion 0 : < c implica entonces que : = :
t
(o) .
(Se usa aqu la unicidad del resto.)
3. :
1
= 0 c + :
1
con 0 :
1
< c :
1
= :
t
(:
1
) .
Pero por otro lado, por (2), :
1
:
2
(mod c) con 0 :
2
< c :
2
= :
t
(:
1
) . Se concluye
que :
1
= :
2
por la unicidad del resto.
4. () : o / (mod c) por hipotesis, y por (1), o :
t
(o) (mod c), / :
t
(/) (mod c) . Por
transitividad (y simetra), se concluye que :
t
(o) :
t
(/) (mod c) . Ahora por (3), :
t
(o) =
:
t
(/) .
() : :
t
(o) = :
t
(/) :
t
(o) :
t
(/) (mod c) , y juntando por transitividad (y simetra)
con o :
t
(o) (mod c), / :
t
(/) (mod c) , resulta o / (mod c) .
10
Al dividir cualquier n umero entero por c , c = 0 , hay c restos posibles: 0, 1, . . . , c 1 . La
conclusion es entonces que la congruencia modulo c clasica los n umeros enteros seg un su resto
modulo c : dos n umeros o y / estan en la misma clase, o sea son identicados, si y solo si
tienen el mismo resto modulo c , y hay c clases distintas, la clase del 0 , o sea compuesta por
los n umeros divisibles por c , la clase del 1 , o sea compuesta por los n umeros que tienen resto 1 ,
etc... Ademas, la proposicion anterior tambien nos dice que para calcular el resto de un n umero
modulo c alcanza con poner a la derecha de la congruencia algo que cumple la condicion de resto,
es decir alg un : con 0 : < c .
Como consecuencia de lo anterior se observa facilmente lo siguiente
Consecuencia (Tablas de Restos)
Sea o, /, c con c = 0 , y sea n . Entonces
:
t
(o + /) = :
t
(
:
t
(o) + :
t
(/)
)
:
t
(o /) = :
t
(
:
t
(o) :
t
(/)
)
:
t
(o
n
) = :
t
(
:
t
(o)
n
)
La necesidad de tomar resto nuevamente (fuera de los parentesis grandes) proviene del hecho que
puede ocurrir que la suma o producto de los restos se pase de c , y entonces hay que volver
a reducir... Es por eso que puede ser mas sencillo trabajar directamente con las congruencias,
siempre reduciendo de manera de obtener a la derecha del signo un n umero que cumple con la
condicion de resto, como se hace en las aplicaciones siguientes.
Aplicaciones
Calcular el resto de dividir por 5 a 166
1328
4878 + 199999 :
Cada n umero es congruente a su resto, luego 166 1 (mod 5) , 4878 3 (mod 5) y
199999 4 (mod 5) implican
166
1328
4878 + 199999 1
1328
3 + 4 (mod 5)
7 (mod 5)
2 (mod 5)
Dado que 2 cumple la condicion de ser resto modulo 5, se concluye que 2 es el resto.
Calcular el resto de dividir por 35 a 34
17771
6
1001
:
A veces en lugar de reemplazar los n umeros por su resto conviene reemplazarlos por 1
u observar alg un comportamiento util. Aqu por ejemplo se puede usar que 6
2
= 36 1
(mod 35) y tambien que 34 1 (mod 5) . Luego:
34
17771
6
1001
= 34
17771
6
2500+1
= 34
17771
+ (6
2
)
500
6
1
(1)
17771
1
500
6 (mod 35)
1 6 (mod 35)
7 (mod 35)
28 (mod 35)
Por lo tanto el resto es 28 .
11
5 Desarrollos en base
El sistema de numeracion que utilizamos desde que seg un parece Fibonacci (1170-1250) lo
introdujo en el mundo occidental, es el sistema decimal indo-arabigo, que es un sistema que funciona
por posiciones de los dgitos (observar aqu otra aplicacion del hecho que exista el n umero 0 , para
signicar que hay una posicion vaca). As, cuando escribimos el n umero seis mil setescientos
ochenta y nueve, 6789 , nos referimos al n umero compuesto por 6 unidades de 1000 mas 7
unidades de 100 mas 8 unidades de 10 mas 9 unidades (de 1 ), o sea al n umero
6789 = 6 10
3
+ 7 10
2
+ 8 10 + 9.
El n umero natural o = :
n
:
n1
. . . :
1
:
0
(donde 0 :
.
< 10 para 0 i n y :
n
= 0 ) simboliza
entonces el n umero :
n
10
n
+ + :
1
10 + :
0
.
Consecuencia (Reglas de divisibilidad)
Sabiendo esto se explican muy facilmente las famosas reglas de divisibilidad. Por ejemplo todos
saben que para ver si un n umero es divisible por 3 , uno le suma los dgitos y se ja si esa suma es
divisible por 3 , o sea, si o = :
n
:
n1
. . . :
1
:
0
,
3 o 3 :
n
+ :
n1
+ + :
1
+ :
0
.
La explicacion es muy sencilla: Dado que 10 1 (mod 3) , que implica que 10
.
1 (mod 3) para
todo i , se tiene que
o = :
n
10
n
+ + :
1
10 + :
0
:
n
+ + :
1
+ :
0
(mod 3).
Luego 3 divide el termino de la izquierda si y solo si 3 divide el termino de la derecha. Es mas,
para conocer el resto de un n umero modulo 3 , alcanza con sumarle los dgitos y tomarle el resto
modulo 3 a esa suma.
Como ejercicio queda vericar y/o enunciar las otras reglas de divisibilidad.
Retomando, el n umero natural o = :
n
. . . :
0
corresponde al desarrollo decimal
o = :
n
10
n
+ + :
0
10
0
.
Las exigencias de un buen sistema de numeracion es que cuando vemos un n umero queremos poder
saber en forma bien determinada de que n umero estamos hablando, ademas de requerir que todo
n umero tenga un unico desarrollo que le corresponda. Esto se logra con la condicion impuesta sobre
los dgitos ( 0 :
.
< 10, 0 i n): para que un n umero este bien determinado, los dgitos tienen
que estar entre 0 y 9 , ya que el lugar de un dgito en el n umero determina a que potencia de 10
corresponde (si uno admitiera por ejemplo el 11 como un dgito, el n umero 111 : correspondera
al n umero 111 = 1 10
2
+ 1 10 + 1 o al 21 = 1 10 + 11 1 ?, y si uno admitiera el 11 pero con
otro smbolo para evitar confusiones como la de arriba, por ejemplo 1 , el n umero 11 tendra dos
escrituras distintas, una como 11 y la otra como 1 ).
Matematicamente no hay nada que haga prevalecer el n umero 10 como eleccion para la base de
numeracion: uno puede jar cualquier n umero natural c 2 como base del sistema de numeracion.
Para la buena determinacion y la unicidad, lo que se tiene que pedir ahora es que los dgitos esten
entre 0 y c 1 . Esto se justica tambien en la vida real, por ejemplo las computadoras trabajan
naturalmente en base 2 , o sea con los dgitos o bits 0 y 1 , ya que esto se corresponde con el
paso o no de electricidad.
12
Teorema 5.1 (Desarrollo en base c )
Sea c con c 2 . Todo n umero o
0
admite un desarrollo en base c de la forma
o = :
n
c
n
+ :
n1
c
n1
+ + :
1
c + :
0
,
con 0 :
.
< c para 0 i n y :
n
= 0 si o = 0 .
Ademas dicho desarrollo, con las exigencias 0 :
.
< c impuestas para los dgitos, es unico.
Se nota o = (:
n
. . . :
0
)
t
.
Observacion 5.2 En el caso de desarrollo en base 10 , (o)
10
se nota simplemente o , en la
forma que estamos acostumbrados.
Ejemplo
6789 = (6789)
10
= (1101010000101)
2
= (204124)
5
= (185)
16
(En base 16 los dgitos 10, 11, 12, 13, 14 y 15 se reemplazan respectivamente por , 1, C, 1, 1
y 1 para evitar confusiones.)
Prueba del Teorema 5.1.
Existencia del desarrollo en base c :
La idea intuitiva es ir dividiendo iteradamente el n umero o y los sucesivos cocientes por c . Para
formalizar la prueba se puede hacer por inducccion en o
0
:
Para o = 0 , se tiene 0 = (0)
t
, es decir estamos en el unico caso en que todos los dgitos son
cero.
o 1 :
La hipotesis inductiva es que todo n umero natural o cero menor que o admite un desarrollo
en base c . Queremos probar que entonces o admite tambien un desarrollo en base c .
Usando el algoritmo de division , dividimos o por c , y obtenemos un cociente / que satisface
0 / < o y un resto :
0
que satisface 0 :
0
< c : Por hipotesis inductiva, al ser 0 / < o ,
/ admite un desarrollo en base c que notamos por conveniencia en la forma:
/ = :
n
c
n1
+ + :
2
c + :
1
con 0 :
n
, . . . , :
1
< c.
Entonces
o = / c + :
0
= (:
n
c
n1
+ + :
2
c + :
1
) c + :
1
= :
n
c
n
+ + :
1
c + :
0
donde 0 :
.
< c para 0 i n como se quiere.
As, todo o admite un desarrollo en base c .
Unicidad: Es una consecuencia de la unicidad del resto y del cociente en el algoritmo de division:
:
0
es el resto de la division de o por c y por lo tanto es unico, :
1
es el resto de la division de
(o :
0
),c por c y es unico tambien, etc... Como antes, podemos formalizar esto por induccion en
o
0
.
13
Para o = 0 , el unico desarrollo es claramente 0 para todos los dgitos.
Para o 1 , supongamos que
o = :
n
c
n
+ + :
1
c + :
0
= :
n
c + + :
1
c + :
0
con 0 :
.
, :

< c para 0 i n, 0 , : y :
n
= 0 , :
n
= 0 . Ahora bien, esta claro que
:
t
(o) = :
0
= :
0
, y ademas, el cociente de dividir o por c (que es unico) es
/ = :
n
c
n1
+ + :
1
= :
n
c
n1
+ + :
1
.
Por hipotesis inductiva, el desarrollo en base c del cociente / es unico, luego n = : y
:
.
= :
.
, 1 i n.
As concluimos que para todo o
0
, el desarrollo en base c de o es unico.
6 Maximo Com un Divisor
Denicion 6.1 (Maximo Com un Divisor)
Sean o, / , no ambos nulos. El maximo com un divisor entre o y / es el mayor de los divisores
comunes de o y / .
Claramente ese n umero existe, ya que la lista de divisores comunes es no vaca ( 1 es un divisor
com un) y nita (por ser al menos uno entre o y / no nulo), y es unico (por ser el mayor). Adem as
es positivo por la misma raz on.
El maximo com un divisor entre o y / se nota mcd(o, /) o (o : /) que es la notacion que adoptamos
aqu. Es entonces caracterizado por:
(o : /) o, (o : /) / y si c o y c /, entonces c (o : /).
Notaremos en lo que sigue con 1iCo:({o, /}) el conjunto de los divisores comunes de o y / y
con 1iCo:
+
({o, /}) el conjunto de los divisores comunes positivos, es decir:
1iCo:({o, /}) := { c : c o y c / } = 1i(o) 1i(/)
1iCo:
+
({o, /}) := { c : c o y c / } = 1i
+
(o) 1i
+
(/).
Luego, el maximo com un divisor es el elemento mas grande de cualquiera de esos dos conjuntos.
Ejemplos
(12 : 18) = 6 , pues 1i
+
(12) = {1, 2, 3, 4, 6, 12}, 1i
+
(18) = {1, 2, 3, 6, 9, 18}
1iCo:
+
({12, 18}) = {1, 2, 3, 6}.
(12 : 35) = 1 ya que 1i
+
(35) = {1, 5, 7, 35} 1iCo:
+
({12, 35}) = {1} .
(o : /) = (/ : o) .
(o : /) = (o : /) = (o : /) = (o : /) = (o : /) .
Para todo o , se tiene (o : 1) = 1
Para todo o , o = 0 , se tiene (o : 0) = o .
14
/ o (o : /) = / .
Mas ejemplos
Calculo de los valores de (n
2
+ 1 : n 1) para n :
n = 1 (2 : 0) = 2 , n = 2 (5 : 1) = 1 , n = 3 (10 : 2) = 2 , n = 4 (17 : 3) = 1 ,
n = 5 (26 : 4) = 2 , n = 6 (37 : 5) = 1 , . . . .
Pareciera que da 2 o 1 seg un si n es impar o par. Vamos a demostrar esto:
Vamos a investigar los posibles divisores comunes de n
2
+1 y n1 para luego determinar
los posibles maximos:
{
c n
2
+ 1
c n 1
=
{
c n
2
+ 1
c (n + 1)(n 1)
=
{
c n
2
+ 1
c n
2
1
= c 2.
As, 1iCo:
+
({n
2
+ 1, n 1}) {1, 2} , y luego (n
2
+ 1 : n 1) {1, 2}.
(Notemos que como dedujimos que c 2 por implicaciones, tiene que pasar que c2 pero
no es obligatorio que todo divisor de 2 sea un divisor com un, o sea puede pasar que
1iCo:
+
({n
2
+1, n1}) este estrictamente contenido en el conjunto {1, 2} , como es
el caso aqu para n par.)
Investigamos ahora por separado los casos n impar, n par:
Si n es impar, n
2
+ 1 y n 1 son pares, luego 2 es un divisor com un, es decir
2 1iCo:
+
({n
2
+1, n 1}) . Por lo tanto, en este caso (n
2
+1 : n 1) = 2 (por ser
el maximo).
Si n es par, n
2
+ 1 y n 1 son impares, luego no son divisibles por 2 :
2 , 1iCo:
+
({n
2
+ 1, n 1}) y en este caso, (n
2
+ 1 : n 1) = 1 .
Calculo de los valores de (n(n 1) : 2(n + 1)) para n :
n = 1 (0 : 4) = 4, n = 2 (2 : 6) = 2, n = 3 (6 : 8) = 2,
n = 4 (12 : 10) = 2, n = 5 (20 : 12) = 4, n = 6 (30 : 14) = 2, . . .
Pareciera dar 4 o 2 seg un si n 1 (mod 4) o no. Probemoslo:
Investiguemos los posibles divisores comunes de n(n 1) y 2(n + 1) para luego deter-
minar los posibles maximos:
{
c n(n 1)
c 2(n + 1)
=
{
c 2n(n 1)
c 2n(n + 1)
=
{
c 2n
2
2n
c 2n
2
+ 2n
= c 4n.
Pero volviendo entonces al principio
{
c 4n
c 2(n + 1)
=
{
c 4n
c 2 2(n + 1)
=
{
c 4n
c 4n + 4
= c 4.
As, 1iCo:
+
({n(n1), 2(n+1)}) {1, 2, 4} , y luego por lo tanto ya podemos deducir
que (n(n 1) : 2(n + 1)) {1, 2, 4} .
Investigamos ahora por separado los casos n 0, 1, 2 o 3 (mod 4) .
Si n 0 (mod 4) , entonces 2(n + 1) 2 (mod 4) y por lo tanto 4 no puede ser un
divisor com un. Pero claramente tanto n(n 1) y 2(n + 1) son n umeros pares, por lo
tanto 2 s es un divisor com un. Luego en ese caso, (n(n 1) : 2(n + 1)) = 2 .
15
Si n 1 (mod 4) :
{
n(n 1) 1(1 1) (mod 4)
2(n + 1) 2(1 + 1) (mod 4)
=
{
n(n 1) 0 (mod 4)
2(n + 1) 0 (mod 4)
=
{
4 n(n 1)
4 2(n + 1)
As, 4 1iCo:
+
({n(n1), 2(n+1)}) , luego, en este caso, (n(n1) : 2(n+1)) = 4 .
Si n 2 (mod 4) , entonces 2(n + 1) 2 (mod 4) y estamos como en el primer caso:
(n(n 1) : 2(n + 1) = 2 .
Si n 3 (mod 4) , entonces n(n 1) 2 (mod 4) , y de nuevo, 4 no puede ser un
divisor com un. En este caso tambien (n(n 1) : 2(n + 1)) = 2 .
Se concluye que (n(n1) : 2(n+1)) = 4 si n 1 (mod 4) y que (n(n1) : 2(n+1)) = 2
si n 1 (mod 4) como se quera probar...
Observacion 6.2 (Importante!)
Sean o, / no ambos nulos, y sea , , entonces:
1iCo:({o, /}) = 1iCo:({/, o , /}) y 1iCo:
+
({o, /}) = 1iCo:
+
({/, o , /}).
En particular, para todo , , (o : /) = (/ : o , /).
Aplicando esto a :
b
(o) = o / / , se obtiene (o : /) = (/ : :
b
(o))
Prueba. Alcanza con probar la primer igualdad, la de los conjuntos 1iCo::
Pero utilizando que c o, c / c o , / y c /, c o , / c o , se tiene
c 1iCo:({o, /}) c o y c / c o , / y c / c 1iCo:({/, o , /}).
La observacion anterior provee directamente de un algoritmo para calcular el maximo com un divisor
entre dos n umeros, que no depende de calcular sus divisores. Este algoritmo fue introducido
o recopilado por Euclides ( 325 265 AC) en Los Elementos, y se lo llama directamente
Algoritmo de Euclides. Es el algoritmo mas eciente posible para calcular el maximo com un divisor
(al menos para n umeros grandes), mucho mas eciente que encontrar los divisores comunes, por
ejemplo mediante factorizacion. Lo vamos a ejemplicar primero en un caso particular.
Ejemplo Calculo de (120 : 84) :
Como (120 : 84) = (120 : 84) , calculamos este ultimo para simplicar las divisiones (esto no es
esencial para el algoritmo). Se tiene
120 = 1 84 + 36 = (120 : 84) = (84 : 36)
84 = 2 36 + 12 = (84 : 36) = (36 : 12)
36 = 3 12 + 0 = (36 : 12) = (12 : 0).
Pero (12 : 0) = 12 , luego (120 : 84) = 12 ya que
(120 : 84) = (120 : 84) = (84 : 36) = (36 : 12) = (12 : 0) = 12.
16
Algoritmo de Euclides
Entrada: o, / , no ambos nulos.
Salida: (o : /) .
Como (o : /) = (o : /) , sin perdida de generalidad podemos suponer o, / 0 , mas a un o / 0
ya que (o : /) = (/ : o) y si / = 0 , entonces (o : /) = o . Se divide o por / y luego los sucesivos
divisores por los sucesivos restos, hasta llegar a un resto nulo:
o = /
0
/ + :
1
con 0 :
1
< /
/ = /
1
:
1
+ :
2
con 0 :
2
< :
1
:
1
= /
2
:
2
+ :
3
con 0 :
3
< :
2
.
.
.
:
2
= /
1
:
1
+ :

con 0 :

< :
1
:
1
= /

+ :
+1
con :
+1
= 0.
Entonces (o : /) = :

, el ultimo resto no nulo.

Justicacion.
Siempre se llega en un n umero nito de pasos (acotado a simple vista por la cantidad / ) a un
resto nulo ya que
/ :
1
:
2
:
3
0,
y esta sucesion estrictamente decreciente de restos 0 no puede ser innita.
Cuando en el procedimiento se llega a un resto nulo, :
+1
= 0 , se tiene
(o : /) = (/ : :
1
) = (:
1
: :
2
) = = (:
1
: :

) = (:

: 0) = :

.
Aplicacion (o
n
1 : o
n
1) = o
(n:n)
1 para o , o = 1 , y :, n :
Vamos a probar que en efecto este es el ultimo resto no nulo al realizar el algoritmo de Euclides
para encontrar el mcd.
Recordemos que vimos en los primeros ejemplos de divisibilidad que: n : o
n
1 o
n
1 .
En el caso general, : = / n + : con 0 : < n, y entonces
o
n
1 = o
| n+:
1 = o
:
(o
| n
1) + (o
:
1) = /

(o
n
1) + o
:
1,
dado que n / n o
n
1 o
| n
1 . Ademas, como 0 o
:
1 < o
n
1 por ser 0 : < n
y o , o = 0 , se tiene que o
:
1 es el resto de dividir a o
n
1 por o
n
1 . Por lo tanto,
aplicando la Observacion 6.2, se obtiene
(o
n
1 : o
n
1) = (o
n
1 : o
:

(n)
1).
La conclusion se obtiene de la misma manera que se probo el algoritmo de Euclides.
Una consecuencia inmediata del algoritmo de Euclides es el importantsimo resultado siguiente:
El maximo com un divisor entre dos n umeros se puede escribir como combinacion entera de esos
n umeros, y de hecho es el n umero natural mas chico con esa propiedad.
Teorema 6.3 (mcd y combinacion entera)
Sean o, / , no ambos nulos. Entonces: :, t : (o : /) = :o + t/
17
Antes de demostrar este teorema, miremos como se pueden obtener en forma sistematica coe-
cientes enteros : y t , en el caso particular del ejemplo que calculamos antes:
Ejemplo (continuacion) (120 : 84) = 12 :
Mirando las dos divisiones que permitieron obtener a 12 como ultimo resto no nulo, pero al reves,
se tiene
84 = 2 36 + 12 = 12 = 84 2 36
120 = 1 84 + 36 = 12 = 84 2 (120 1 84)
= 3 84 2 120.
Por lo tanto, 12 = 2 120 + 3 84 = 2 120 + (3) (84) . Aqu, : = 2 y t = 3 sirven.
Prueba del Teorema 6.3.
Se miran al reves las sucesivas divisiones hasta la que da al maximo com un divisor como ultimo
resto no nulo, y, tratando los sucesivos divisores y restos como si fueran variables y reagrupando,
se obtiene una escritura entera de (o : /) como combinacion entera de o y / . (Luego, si habamos
para simplicar las divisiones cambiado los signos de los o y / originales, se modican los
signos para escribir (o : /) como combinacion entera de los o y / originales.)
:
2
= /
1
:
1
+ :

= :

= :
2
/
1
:
1
:
3
= /
2
:
2
+ :
1
= :

= :
2
/
1
(:
3
/
2
:
2
)
= (1 + /
1
/
2
):
2
/
1
:
3
.
.
.
:
1
= /
2
:
2
+ :
3
= :

= :
1
+

:
2
/ = /
1
:
1
+ :
2
= :

= :
1
+

(/ /
1
:
1
)
= ( /
1

):
1
+

/
o = /
0
/ + :
1
= :

= ( /
1

)(o /
0
/) +

/
= : o + t /.
As, (o : /) = :

= : o + t / donde claramente :, t ya que son obtenidos sumando y multipli-

cando enteros.
Observacion 6.4 Sean o, / , no ambos nulos.
Si c es tal que c = :

o + t

/ con :

, t

, entonces (o : /) c . En particular si c ,
(o : /) c .
Prueba. Dado que (o : /) o y (o : /) / , se tiene (o : /) :

o + t

/ , luego (o : /) c .
La observacion anterior nos dice que el maximo com un divisor (o : /) es el n umero natural mas
chico que se puede escribir como combinacion entera de o y / y que todas las demas combinaciones
enteras de o y / son divisibles por el.
El Teorema 6.3 tiene otra consecuencia importantsima que no es obvia a primer vista: el maximo
com un divisor no solo es el mas grande de los divisores comunes sino que tambien es divisible por
ellos.
Proposicion 6.5 (mcd y divisibilidad)
Sean o, / , no ambos nulos y sea c , con c = 0 . Entonces: c o y c / c (o : /)
18
Prueba.
() : Esta es la implicacion interesante y no trivial:
Recordemos que existen :, t tales que (o : /) = : o + t / . Ahora, dado que por hipotesis, c o
y c / , se tiene que c :o + t/ = (o : /) .
() : Esta implicacion es obvia por la transitividad de la divisibilidad.
Otra consecuencia util del Teorema 6.3, de la Observacion 6.4 y de la Proposicion 6.5 es la siguiente:
Consecuencia
Sean o, / , no ambos nulos, y sea / con / = 0 . Entonces (/ o : / /) = / (o : /)
Prueba.
Sin perdida de generalidad, podemos suponer / 0 .
Por un lado, aplicando la Proposicion 6.5, se tiene
(o : /) o y (o : /) / = / (o : /) / o y / (o : /) / / = / (o : /) (/ o : / /).
Por otro lado, por el Teorema 6.3 y la Observacion 6.4, se tiene
(o : /) = : o + t / = / (o : /) = : (/ o) + t (/ /) = (/ o : / /) / (o : /).
Como ambos terminos son positivos, se concluye que son iguales.
En realidad, los resultados que se obtuvieron permiten tres caracterizaciones equivalentes del
maximo com un divisor, que se enuncian a continuacion. La primera corresponde a la Denicion
6.1 del mcd y es la caracterizacion intuitiva, la segunda corresponde principalmente al Teorema
6.3 y la tercera a la Proposicion 6.5, y son las operativas. Se deja la prueba a cargo del lector,
mencionando simplemente que alcanza con probar (1 2), (2 3) y (3 1), ya que por
ejemplo para probar que (2 1) se usa (2 3 1).
Teorema 6.6 Sean o, / , no ambos nulos, y sea d . Son equivalentes:
1. d o, d / y si c o y c / , entonces c d .
2. d o, d / y existen :, t tales que d = :o + t/ .
3. d o, d / y si c o y c / , entonces c d .
Si un n umero d cumple cualquiera de esas 3 propiedades, entonces d = (o : /) .
Una atencion especial merecen los pares de n umeros cuyo maximo com un divisor es igual a 1 .
Juegan un papel central en lo que sigue.
Denicion 6.7 (N umeros coprimos)
Sean o, / , no ambos nulos. Se dice que o, / , no ambos nulos, son coprimos si y solo si
(o : /) = 1 , es decir si y solo si los unicos divisores comunes de o y / son 1 . En ese caso,
seguimos la notacion introducida por el matematico e informatico Donald Knuth (quien de hecho
es el creador del TeX (y LATeX), editores con los que escribimos textos matematicos que lucen tan
bonitos, en particular este texto), y escribimos o / . O sea:
o /
def
(o : /) = 1
19
Ejemplos
103 98 pero 12202 43554 .
o 0 o = 1
Para todo / , 1 / .
Para o, / coprimos, los distintos valores que puede tomar (2o + / : 3o 2/) son
exactamente el 1 y el 7 :
Investiguemos algunos valores de (2o + / : 3o 2/) con o / :
o = 1, / = 0 : (2 : 3) = 1; o = 1, / = 1 : (3 : 1) = 1; o = 3, / = 1 : (7 : 7) = 7.
Luego, efectivamente los dos valores, 1 y 7 , se obtienen. Hay que probar que son los
unicos dos posibles.
Como en los primeros ejemplos generales de calculo de mcd, investigamos los posibles
divisores comunes. Sea c un divisor com un entre 2o + / y 3o 2/ ,
{
c 2o + /
c 3o 2/
=
{
c 3(2o + /)
d 2(3o 2/)
=
{
c 6o + 3/
c 6o 4/
= c 7/.
De la misma manera:
{
c 2o + /
c 3o 2/
=
{
c 2(2o + /)
c 3o 2/
=
{
c 4o + 2/
c 3o 2/
= c 7o.
Luego c 7o y c 7/ . Aplicando la Proposicion 6.5, la Consecuencia vista arriba y el
hecho que o / , se tiene
c (7o : 7/) = 7(o : /) = 7 = c 7.
Se concluye que el maximo com un divisor, que es el mayor de estos c posibles, es o bien
1 o 7 como se quera probar (ademas efectivamente ya mostramos que haba casos en
que es 1 y casos en que es 7 ).
Observacion 6.8 (Fundamental!)
o / :, t : 1 = : o + t /
Prueba.
( ) es el hecho que el mcd es combinacion entera de los n umeros.
( ) es por la Observacion 6.4: (o : /) 1 (o : /) = 1.
La proposicion que sigue trata de propiedades esenciales de divisibilidad cuando hay n umeros
coprimos de por medio. No se podran demostrar estas propiedades si no se tuviera la Observacion
6.8.
Proposicion 6.9 (Propiedades esenciales de divisibilidad con coprimalidad)
Sean o, /, c, d con c = 0 y d = 0 . Entonces
1. c o, d o con c d = c d o .
20
2. c o / con c o = c / .
Observemos que estas armaciones no son ciertas si no se piden las propiedades de coprimalidad.
Por ejemplo 6 12 y 4 12 pero 24 12 , y 6 2 3 6 2 o 6 3 . Por otro lado, las recprocas
siempre valen: c d o c o y d o , y c / c d o / . Luego podemos resumir la Proposicion en:
Si c d , entonces: c o, d o c d o , y si c o , entonces: c o / c /
Prueba de la Proposicion 6.9.
1. c d 1 = : c + t d o = : (c o) + t (d o) , pero d o c d c o y c o c d d o ,
luego c d : (c o) + t (d o) = o .
2. d o 1 = : d + t o , luego / = (: /) d + t (o /) , pero d o / , y d d . Por lo tanto,
d (: /) d + t (o /) = / .
Ejemplo Calculo de los o, / coprimos tales que
2
o
+
o
/
es entero.
2
o
+
o
/
=
2/ + o
2
o/
o/ 2/ + o
2
.
Pero al ser o / , o/ 2/ + o
2
o 2/ + o
2
y / 2/ + o
2
.
Pero, dado que o o
2
, o 2/ + o
2
o 2/ , y, dado que o / , o 2/ o 2 . Es decir, o
{1, 2} .
De la misma forma, dado que / 2/ , / 2/ + o
2
/ o
2
, y, dado que / o
2
(pues o / ),
/ o
2
1 / 1 , o sea / {1} .
Se obtienen luego los 8 pares o = 1, / = 1 y o = 2, / = 1 .
Otra consecuencia muy util de la Proposicion 6.8, ya que se trata siempre de reducirse a pares
coprimos para poder aplicar proposiciones como la anterior, es la siguiente:
Proposicion 6.10 (Coprimizando)
Sean o, / , no ambos nulos. Entonces
o
(o : /)

/
(o : /)
.
Por lo tanto: o = (o : /) o

y / = (o : /) /

con o

, /

coprimos
Prueba.
Se sabe que (o : /) = : o + t / . Luego, dividiendo por (o : /) , se obtiene 1 = :
o
(o : /)
+ t
/
(o : /)
,
es decir
o
(o:b)
y
b
(o:b)
son coprimos.
De hecho esta propiedad de cocientes coprimos permite presentar otra caracterizacion del maximo
com un divisor, como las propuestas en el Teorema 6.6:
Observacion Sean o, / , no ambos nulos. Sea d un n umero que satisface que
d o, d / y
o
d

/
d
.
21
Entonces d = (o : /) .
(Esto vale por ejemplo porque o,d /,d :, t con 1 = :o,d + t/,d , lo que implica que
d = :o + t/ , la caracterizacion (2) del Teorema 6.6.)
Otras consecuencias son las siguientes:
Consecuencias Sean o, /, c , no nulos.
1. o / y o c o / c
2. o / o
n
/
n
, para todo :, n .
3. (o
n
: /
n
) = (o : /)
n
.
(Ojo! el mismo exponente para o y / . Si no, no es cierto: dar un ejemplo.)
Prueba.
1. ( ) 1 = : o + t / y 1 = :

o + t

c =
1 = (: o+t /)(:

o+t

c) = : :

o
2
+: t

o c+t :

o /+t t

/ c = (: :

o+: t

c+t :

/) o+t t

/ c = :

o+t

/ c,
con :

:= : :

o + : t

c + t :

/ y t

:= t t

enteros.
( ) 1 = : o + t / c = 1 = : o + (t c) / y 1 = : o + (t /) c , es decir o / y o c .
2. Se obtiene por induccion a partir de (1) : intuitivamente o / o /
2
o /
3
etc., y
en forma simetrica o /
n
o
2
/
n
o
3
/
n
etc.
3. Sea d := (o : /) . Por la Proposicion 6.10, o = d o

y / = d /

con o

. Luego
(o
n
: /
n
) = (d
n
o

n
: d
n
/

n
) = d
n
(o

n
: /

n
) = d
n
, por el inciso anterior.
Ejemplos
Para todo n , (2
n
+ 3
n
: 2
n
2 3
n
) = 1 :
Como siempre, sea c un posible divisor com un:
{
c 2
n
+ 3
n
c 2
n
2 3
n
= c 3
n
+ 2 3
n
= c 3 3
n
.
De la misma manera:
{
c 2
n
+ 3
n
c 2
n
2 3
n
=
{
c 2 2
n
+ 2 3
n
c 2
n
2 3
n
= c 2 2
n
+ 2
n
= c 3 2
n
.
Pero
c 3 3
n
y c 3 2
n
= c (3 3
n
: 3 2
n
) = 3 (3
n
: 2
n
) = 3 1 = 3.
Por lo tanto, (2
n
+ 3
n
: 2
n
2 3
n
) = 1 o 3 . Falta descartar que sea 3 . Pero claramente
3 no puede ser un divisor com un ya que 3 2
n
+ 3
n
(pues si lo dividiera, se tendra, como
3 3
n
, que 3 2
n
, pero 2
n
(1)
n
(mod 3) , es decir 2
n
1 (mod 3) ).
22
Para todo n , (n
100
: (n + 1)
150
) = 1 :
Eso es porque n n + 1 (pues c n, c n + 1 c 1) , y aplicando la Consecuencia 2 de la
Proposicion 6.10.
Para todo n , se tiene:
(n
100
: (n + 2)
150
) =

1 si n 1 (mod 2)
2
150
si n 0 (mod 4)
2
100
si n 2 (mod 4)
Pues si c n y c n+2 , entonces c 2 . Luego (n : n+2) = 1 si n es impar y (n : n+2) = 2 si
n es par. As, si n 1 (mod 2) , es decir si n es impar, (n
100
: (n+2)
150
) = 1 . Consideremos
ahora el caso n par. Si n es par, mirandolo modulo 4, se tiene n 0 (mod 4) o n 2
(mod 4) :
Caso n 0 (mod 4) : n = 4 / = 2
2
/ , luego n + 2 = 2 (2 / + 1) y
(n
100
: (n + 2)
150
) = ((2
2
/)
100
: (2(2 / + 1))
150
)
= (2
200
/
100
: 2
150
(2 / + 1)
150
) = 2
150
(2
50
/
100
: (2 / + 1)
150
).
Ahora bien, 2 2 / + 1 2
50
(2 / + 1)
150
, y / 2 / + 1 (probarlo!) /
100

(2 / + 1)
150
. Se concluye aplicando la Consecuencia 1 de la Proposicion 6.10.
Caso n 2 (mod 4) : n = 4 / + 2 = 2 (2 / + 1) , luego n + 2 = 2
2
(/ + 1) y
(n
100
: (n+2)
150
) = (2
100
(2 /+1)
100
: 2
300
(/+1)
150
) = 2
100
((2 /+1)
100
: 2
200
(/+1)
150
).
Ahora bien, 2 2 / + 1 2
200
(2 / + 1)
100
, y / + 1 2 / + 1 (probarlo!)
(/ + 1)
150
(2 / + 1)
100
. Se concluye aplicando la Consecuencia 1 de la Proposicion
6.10.
(o : /) = 6 = (o / : 6 o 6 /) = 36 :
Coprimizando, se tiene o = 6 o

, / = 6 /

con o

, luego
(o / : 6 o 6 /) = (36 o

: 36o

36/

) = (36 o

: 36(o

)) = 36(o

: o

).
Para concluir falta probar entonces que o

:
Como siempre, sea c un posible divisor com un:
{
c o

c o

=
{
c o

c o

(o

)
=
{
c o

c o

2
o

= c o

2
De la misma manera:
{
c o

c o

=
{
c o

c /

(o

)
=
{
c o

c o

2
= c /

2
Obtuvimos c o

2
y c /

2
. Luego c (o

2
: /

2
) . Pero, como vimos arriba, o

2
, es decir (o

2
: /

2
) = 1 . O sea c 1 . As se prueba que los unicos divisores comunes de
o

y o

son 1 , luego o

como queramos probar.

23
(o : 8) = 4 = (o
2
+ 5 o + 32 : 80) =? :
La condicion (o : 8) = 4 implica que o = 4 o

. Como 8 = 4 2 , si se tuviera 2 o

entonces
se tendra 8 (o : 8) . Luego no puede ser 2 o

, o sea se tiene o

impar. Por lo tanto:

(o
2
+5 o+32 : 80) = (16 o
2
+20 o

+32 : 80) = (4 (4 o
2
+5o

+8) : 4 20) = 4 (4o

2
+5o

+8 : 20),
donde o

es impar. Ahora bien, (4o

2
+5o

+8 : 20) { 1, 2, 4, 5, 10, 20 } , y como claramente

2 4o
2
+ 5o

+ 8 pues o

es impar, 2 no es un divisor com un (no divide al mcd). Luego

(4o
2
+ 5o

+ 8 : 20) { 1, 5 } .
Falta averiguar si puede ser 5 : pero 4 o
2
+5 o

+8 4 o
2
+3 (mod 5) y es facil ver, seg un
los posibles restos de o

modulo 5 , que ese n umero nunca es divisible por 5 .

Luego (4o
2
+ 5o

+ 8 : 20) = 1 y por lo tanto (o

2
+ 5 o + 32 : 80) = 4 .
7 Ecuaciones Diofanticas
Vamos a aplicar ahora lo visto a la resolucion de ciertas ecuaciones en enteros, que se llaman
Ecuaciones Diofanticas. Se llaman as las ecuaciones con coecientes enteros de las cuales se
buscan las soluciones enteras. El nombre se puso por Diofanto de Alejandra ( 200 284) quien
fue quien desarrollo ese tipo de ecuaciones en su obra La Aritmetica. Las ecuaciones diofanticas
mas sencillas son las ecuaciones de la forma o A + / Y = c con o, /, c , donde o y / no son
ambos nulos, de las cuales se buscan los pares de soluciones enteras. Observemos que una ecuacion
de este tipo es la ecuacion de una recta en
2
, que sabemos resolver en
2
, y que nos estamos
preguntando por que puntos de coordenadas ambas enteras pasa esa recta.
El problema es entonces el siguiente: encontrar todos los pares (r, j)
2
que son solucion de la
ecuacion
o A + / Y = c,
donde o, /, c son enteros dados, o, / no ambos nulos.
Como primer paso queremos decidir si existe al menos una solucion entera (r
0
, j
0
) .
Observacion Si o = 0 o / = 0 (pongamos / = 0 ), el problema se vuelve un problema de
divisibilidad: o A +0 Y = c tiene solucion entera si y solo si o c , y en ese caso las soluciones son
todos los pares (c,o, ,), , . Luego en lo que sigue podemos suponer o y / no nulos.
Ejemplos
5 A + 9 Y = 1 tiene por ejemplo como solucion entera r
0
= 2, j
0
= 1 .
5 A + 9 Y = 10 tiene como solucion entera r
0
= 10 2 = 20, j
0
= 1 10 = 10 .
4 A+6 Y = 7 no tiene solucion entera porque el resultado de lo de la izquierda es claramente
siempre par. De hecho recordamos que si un n umero se escribe como combinacion entera de
o y / , entonces tiene que ser un m ultiplo de (o : /) .
4 A +6 Y = 2 tiene solucion ya que 2 = (4 : 6) y sabemos que el mcd es combinacion entera
de los n umeros. Se puede elegir aqu r
0
= 1, j
0
= 1 .
18 A 12 Y = 2 no tiene solucion entera pues (18 : 12) = 6 y 6 2 .
24
18 A12 Y = 60 tiene solucion pues (18 : 12) 60 : por ejemplo escribimos 6 = 18 112 1
y as obtenemos 60 = 10 6 = 18 10 12 10 , es decir r
0
= 10, j
0
= 10 .
Concluimos la siguiente proposicion:
Proposicion 7.1 Sean o, /, c con o, / no nulos.
Entonces la ecuacion diofantica o A +/ Y = c admite soluciones enteras si y solo si (o : /) c . Es
decir:
(r, j)
2
: o r + / j = c (o : /) c
Prueba.
( ): Sea (r
0
, j
0
)
2
una solucion entera, entonces, como siempre, dado que (o : /) o y
(o : /) / , se concluye que (o : /) o r
0
+ / j
0
= c , es decir, (o : /) c .
( ): Sabemos que existen :, t tales que (o : /) = : o + t / . Luego, dado que (o : /) c ,
existe / tal que c = / (o : /) , y por lo tanto se tiene que c = o (/ :) +/ (/ t) . Podemos tomar
r
0
:= / :, j
0
:= / t .
Corolario 7.2 Sean o, /, c con o, / no nulos y coprimos.
Entonces la ecuacion diofantica o A + / Y = c tiene soluciones enteras.
La proposicion da ademas una forma de conseguir una solucion (r
0
, j
0
) particular (si existe),
cuando no se consigue mas facilmente (por ejemplo a ojo) podemos aplicar el algoritmo de Euclides
para escribir el mcd como combinacion entera. Y luego de all obtener la combinacion entera que
da c como en la demostracion anterior. Pero siempre es mas facil trabajar directamente con la
ecuacion coprimizada:
Observacion Sean o, /, c con o, / no nulos tales que (o : /) c .
Entonces la ecuacion diofantica oA + /Y = c es equivalente a (es decir tiene exactamente las
mismas soluciones enteras que) la ecuacion diofantica coprimizada:
o

A + /

Y = c

, donde o

:=
o
(o : /)
, /

:=
/
(o : /)
y c

:=
c
(o : /)
.
Adoptamos la notacion para ecuaciones diofanticas equivalentes, es decir con las mismas
soluciones y resumimos lo anterior en
Si (o : /) c, entonces o A + / Y = c
o
(o : /)
A +
/
(o : /)
Y =
c
(o : /)
.
Siempre resulta mas simple hacer este proceso de coprimizacion de entrada para encontrar una
solucion particular: se escribe el 1 como combinacion entera de o

y /

: 1 = :o

+ t/

y luego
haciendo c

= c

:o

+ c

t/

se obtiene por ejemplo r

0
= c

: e j
0
= c

t .
El paso siguiente es, dada una ecuacion diofantica que admite al menos una solucion entera,
encontrarlas todas.
25
Vamos a tratar primero en detalle un caso particular, el caso c = 0 , es decir el caso de una ecuacion
diofantica de tipo
o A + / Y = 0
que siempre tiene solucion pues (o : /) 0 . Miramos primero un ejemplo.
Ejemplo Soluciones enteras de 18 A + 27 Y = 0 :
La solucion mas simple es r
0
= 0, j
0
= 0 . O tambien se tiene r
1
= 27, j
1
= 18 . As que la
solucion no es unica. Tambien por ejemplo r
2
= 27, j
2
= 18 o r
3
= 3, j
3
= 2 sirven. Vamos
a probar que son innitas. Como se consiguen todas ?
Por lo mencionado arriba, la ecuacion original es equivalente a la euacion coprimizada:
18 A + 27 Y = 0 2 A + 3 Y = 0.
Ahora bien, sea (r, j)
2
solucion:
2 r + 3 j = 0 2 r = 3 j
= 2 3 j y 3 2 r
= 2 j (pues 2 3) y 3 r (pues 3 2)
= j = 2 , y r = 3 /.
Volviendo al primer renglon, resulta:
2 (3 /) = 3 (2 ,) = , = /.
Es decir: r = 3 / e j = 2 / para alg un / .
Hemos probado: (r, j) solucion entera = existe / tal que r = 3 / e j = 2 / .
Veriquemos la recproca: Si r = 3 / e j = 2 / para el mismo / , entonces (r, j) es
solucion de la ecuacion. Efectivamente, se tiene 2 r + 3 j = 2 (3 /) + 3 (2 /) = 0 .
Luego, hemos probado que el conjunto de soluciones enteras de esta ecuacion es el conjunto:

0
= { (r, j) : r = 3 /, j = 2 /; / }.
(Observemos que si nos olvidamos de coprimizar la ecuacion y nos quedamos, usando la misma
estructura, con las soluciones de tipo r = 27 /, j = 18 /, / , perdemos soluciones ya que se
nos escapa por ejemplo la solucion de antes r
3
= 3, j
3
= 2 .)
Este procedimiento se puede generalizar sin problemas:
Proposicion 7.3 Sean o, / , no nulos.
El conjunto
0
de soluciones enteras de la ecuacion diofantica o A + / Y = 0 es

0
= { (r, j) : r = /

/, j = o

/; / }, donde o

:=
o
(o : /)
y /

:=
/

(o : /)
.
Prueba.
Se tiene
o A + / Y = 0 o

A + /

Y = 0,
donde o

= o,(o : /) y /

= /,(o : /) son coprimos.

26
Ahora bien, sea (r, j)
2
solucion:
o

r + /

j = 0 o

r = /

j
= o

j y /

r
=
o

j y /

r
= j = o

, y r = /

/.
Volviendo al primer renglon, resulta:
o

(/

/) = /

(o

,) = , = /.
Es decir: r = /

/ e j = o

/ para alg un / .
Hemos probado: (r, j) solucion entera = existe / tal que r = /

/ e j = o

/ .
Veriquemos la recproca: Si r = /

/ e j = o

/ para el mismo / , entonces (r, j) es

solucion de la ecuacion. Efectivamente, se tiene o

r + /

j = o

(/

/) + /

(o

/) = 0 .
Para resolver completamente una ecuacion general o A + / Y = c , que admite al menos una
solucion particular (r
0
, j
0
)
2
, nos podemos reducir al caso anterior observando que, dado que
o r
0
+ / j
0
= c , se tiene que para (r, j)
2
,
o r + / j = c o r + / j = o r
0
+ / j
0
o (r r
0
) + / (j j
0
) = 0.
Es decir (r, j) es solucion de o A+/ Y = c si y solo si (rr
0
, jj
0
) es solucion de o A+/ Y = 0 .
Luego, aplicando la Proposicion 7.3, obtenemos el Teorema siguiente:
Teorema 7.4 Sean o, /, c , con o, / no nulos.
El conjunto de soluciones enteras de la ecuacion diofantica o A + / Y = c es:
= , si (o : /) c .
= { (r, j) : r = r
0
+ /

/, j = j
0
o

/; / } , donde (r
0
, j
0
) es una solucion
particular, o

:=
o
(o : /)
, /

:=
/
(o : /)
, si (o : /) c .
Resumimos el algoritmo que se obtiene a partir del Teorema en el cuadro siguiente:
Resolucion completa de la ecuacion diofantica o A + / Y = c
1. Tiene solucion la ecuacion ?
(a) no si (o : /) c . En ese caso = .
(b) s si (o : /) c . En ese caso:
2. Coprimizo la ecuacion:
o

A + /

Y = c

, con o

:=
o
(o : /)
, /

:=
/
(o : /)
y c

:=
c
(o : /)
.
27
3. Busco una solucion particular (r
0
, j
0
)
2
(a ojo o aplicando el algoritmo de Euclides).
4. Todas las soluciones son:
= { (r, j) : r = r
0
+ /

/, j = j
0
o

/; / }.
Ejemplos
Soluciones enteras de 18 A + 27 Y = 90 :
Hay soluciones pues (18 : 27) = 9 90 .
Coprimizo: 2 A + 3 Y = 10 .
Solucion particular: (r
0
, j
0
) := (5, 0) .
Entonces = { (r, j) : r = 5 + 3/, j = 2/, / } .
Soluciones naturales de 175 A + 275 Y = 3000 :
Hay soluciones enteras pues (125 : 50) = 25 3000 .
Coprimizo: 7 A + 11 Y = 120 .
Solucion particular?
11 = 1 7 + 4, 7 := 1 4 + 3, 4 = 1 3 + 1
1 = 4 3 = 4 (7 4) = 2 4 7 = 2 (11 7) 7 = 2 11 3 7
120 = 7 (360) + 11 240
(r
0
, j
0
) = (360, 240).
Soluciones enteras: r = 360 + 11 /, j = 240 7 /, / .
Soluciones naturales:
r 0 e j 0 =
360 + 11 / 0 y 240 7 / 0 =
11 / 360 y 240 7 / =
/ (360,11) = 32, 7... y / < (240,7) = 34, 2...
Por lo tanto / {33, 34} : hay dos pares de soluciones naturales, r
1
:= 360 + 11 33 =
3, j
1
:= 240 7 33 = 9 y r
2
:= 360 + 11 34 = 14, j
2
:= 240 7 34 = 2 .
Entonces

= { (3, 9), (14, 2) } .

8 Ecuaciones de Congruencia
El analisis realizado para las ecuaciones diofanticas se aplica directamente a ciertas ecuaciones
lineales de congruencia. Mas especicamente a las ecuaciones de la forma
o A c (mod /),
donde o, /, c , con o y / no nulos, de las cuales se buscan las soluciones enteras.
Veremos ahora que la ecuacion de congruencia o A c (mod /) admite al menos una solucion en
si y solo si la ecuacion diofantica o A / Y = c admite al menos una solucion en
2
, y por lo
visto en el Teorema 7.4, esto es si y solo si (o : /) = (o : /) c .
28
Proposicion 8.1 Sean o, /, c , con o, / no nulos. Entonces:
La ecuacion de congruencia o A c (mod /) admite soluciones enteras si y solo si (o : /) c .
En ese caso la ecuacion es equivalente a la ecuacion de congruencia coprimizada
o

A c

(mod /

) donde o

:=
o
(o : /)
, /

:=
/
(o : /)
y c

:=
c
(o : /)
.
Para probar la segunda armacion, es util aislar la propiedad siguiente, que es inmediata:
Proposicion 8.2 Sean o, /, c, / , con o, /, / = 0 . Entonces, para r , se tiene:
o r c (mod /) (/ o) r / c (mod (/ /)).
Prueba.
/ or c / (o r c) = / / (/ o) r / c.
Prueba de la Proposicion 8.1.
Si (o : /) c , entonces la ecuacion diofantica oA/Y = c admite al menos una solucion particular
(r
0
, j
0
)
2
. Es decir, or
0
/j
0
= c , o equivalentemente or
0
c = /j
0
. Por lo tanto /or
0
c ,
o lo que es lo mismo, or
0
c (mod /) : r
0
es una solucion particular de la ecuacion de
congruencia o A c (mod /) .
Recprocamente, si r
0
es una solucion particular de la ecuacion de congruencia o A
c (mod /) , entonces existe j
0
tal que or
0
c = /j
0
, por lo cual la ecuacion diofantica
oA /Y = c admite la solucion particular (r
0
, j
0
)
2
. Por lo visto en la seccion anterior, esta
ecuacion diofantica tiene solucion si y solo si (o : /) c .
Finalmente, cuando (o : /) c , la ecuacion o

A c

(mod /

) sigue teniendo todos sus coecientes

enteros, y se aplica la proposicion anterior para d := (o : /) , o := d o

, / := d /

y c := d c

.
Adoptamos la notacion para ecuaciones de congruencia equivalentes, o sea con las mismas
soluciones, y resumimos lo anterior en
Si (o : /) c, entonces o A c (mod /)
o
(o : /)
A
c
(o : /)
(mod
/
(o : /)
).
Corolario 8.3 Sean o, /, c , con o, / no nulos y coprimos. Entonces, la ecuacion de
congruencia o A c (mod /) tiene soluciones enteras.
El paso siguiente es (como en el caso de las ecuaciones diofanticas) dada una ecuacion de congru-
encia que admite al menos una solucion entera, encontrarlas todas:
Teorema 8.4 Sean o, /, c con o, / no nulos.
La ecuacion de congruencia o A c (mod /)
no tiene soluciones cuando (o : /) c .
29
tiene soluciones cuando (o : /) c ; en ese caso
o A c (mod /) A r
0
(mod
/
(o : /)
)
donde r
0
es una solucion particular.
Prueba.
El primer inciso es la Proposicion 8.1. Para probar la equivalencia del segundo inciso, tenemos que
probar que las dos ecuaciones de congruencia tienen las mismas soluciones.
Si r es una solucion cualquiera de la ecuacion de congruencia original or c (mod /) ,
entonces existe j tal que (r, j) es solucion de la ecuacion diofantica o A / Y = c . Por el
Teorema 7.4, existe una solucion particular (r
0
, j
0
) de la ecuacion diofantica y / tales que
r = r
0
+(/

)/ e j = j
0
o

/ . En particular /

rr
0
, es decir r r
0
(mod /

) como se quera
probar.
Reciprocamente, si r r
0
(mod /

) entonces o

r o

r
0
(mod /

) . Como r
0
es una
solucion particular de la ecuacion original, se tiene o

r
0
c

(mod /

) (dada la equivalencia de
la ecuacion de congruencia original y la coprimizada) y por lo tanto, por transitividad, o

r c

(mod /

) como se quera probar,

Antes de resumir el algoritmo que se obtiene a partir del Teorema, hagamos algunos ejemplos.
Ejemplos
La ecuacion 9 A 2 (mod 15) no tiene solucion pues (9 : 15) 2 .
La ecuacion 9 A 6 (mod 15) :
9 A 6 (mod 15) 3 A 2 (mod 5) A 4 (mod 5).
(Aqu, r
0
:= 4 es una solucion particular.)
La ecuacion 3 A 2 (mod 4) :
3 A 2 (mod 4) A 2 (mod 4).
La ecuacion 12 A 6 (mod 10) tiene solucion pues (12 : 10) = 2 6 . Pero es a un mas facil
simplicar todo lo que se puede en la ecuacion antes, como 12 2 (mod 10) , se tiene:
12 A 6 (mod 10) 2 A 6 (mod 10) A 3 (mod 5).
La ecuacion 120 A 60 (mod 250) tiene solucion pues (120 : 250) = 10 60 .
120 A 60 (mod 250) 12 A 6 (mod 25) 2 A 1 (mod 25) A 13 (mod 25) :
Aqu la observacion crucial fue que para cada r, 6 (2 r) 6 1 (mod 25) y 6 25 implica
que se puede simplicar el 6 , es decir implica 2 r 1 (mod 25) . Esto se generaliza en la
siguiente observacion:
30
Observacion 8.5 Sean o, /, c, / con o, /, / no nulos.
Si se cumple que / y / son coprimos, entonces se tiene la siguiente equivalencia de ecuaciones de
congruencia
o A c (mod /) (/ o) A / c (mod /).
Prueba. Hay que probar que tienen las mismas soluciones r:
( ): Vale siempre.
( ): Esto es porque / / (o r c) y / / implica / o r c .
Resolucion completa de la ecuacion de congruencia o A c (mod /)
1. Antes que nada reemplazo o por :
b
(o) y c por :
b
(c) sin cambiar las soluciones, ya que
o :
b
(o) (mod /) y c :
b
(c) (mod /) , o por alg un otro n umero conveniente que sea
congruente, por ejemplo 1 . As, de entrada se tiene que los coecientes de la ecuacion de
congruencia son los mas simples posibles.
2. Tiene solucion la ecuacion ?
(a) no si (o : /) c .
(b) s si (o : /) c . En ese caso:
3. Coprimizo la ecuacion:
o

A c

(mod /

), con o

:=
o
(o : /)
, /

:=
/
(o : /)
y c

:=
c
(o : /)
.
4. Si puedo, ahora que o

, simplico todos los factores comunes entre o

y c

aplicando
la Observacion 8.5. Esto me simplica la b usqueda de la solucion particular.
5. Busco una solucion particular r
0
que satisface que o

r
0
c

(mod /

) (a ojo o encon-
trando una solucion particular de la ecuacion diofantica o

A /

Y = c

asociada).
6. Se concluye que
o A c (mod /) A r
0
(mod /

).
Es decir, todas las soluciones son los r que satisfacen la ecuacion de congruencia
A r
0
(mod /

).
9 Primos y Factorizaci on
Recordemos que un n umero j es primo si y solo si es = 0, 1 y tiene unicamente 4 divisores,
o, lo que es lo mismo, si y solo si tiene unicamente 2 divisores positivos. Tambien, que un n umero
o es compuesto si y solo si es = 0, 1 y existe c con 1 < c < o tal que c o .
Los n umeros primos juegan un papel fundamental en el conjunto de los n umeros enteros, y su
estudio es la base de la teora de n umeros o Aritmetica.
Una de las propiedades esenciales que distingue a los n umeros primos de los n umeros compuestos
es que todo n umero es divisible por alg un primo:
31
Proposicion 9.1 Sea o , o = 0, 1 . Entonces existe un primo (positivo) j tal que j o .
Prueba.
La demostracion intuitiva de si o es primo, ya esta pues es divisible por el mismo, y si no, es
compuesto, entonces es divisible por alg un / mas chico, si ese / es primo, ya esta, si no es divisible
por alg un c mas chico, etc... se formaliza por induccion en o :
Claramente alcanza probar la proposicion para o positivo, es decir para o 2 (pues o = 0, 1 ).
La proposicion es entonces: j(o) : j primo positivo : j o .
o = 2 : j(2) es verdadera pues j := 2 2 .
o 2 :
Si o es primo, j(o) es verdadera pues j := o o .
Si o no es primo, entonces es compuesto, y por lo tanto existe c con 1 < c < o tal que
c o . Por hipotesis inductiva, como 1 < c < o , existe un primo positivo j tal que j c . Se
concluye que j o por transitividad de la divisibilidad.
As, todo n umero distinto de 0, 1 es divisible por alg un primo positivo.
Una consecuencia de este hecho es que hay innitos primos distintos. (El hecho que haya innitos
n umeros naturales no garantiza de por s que haya innitos primos ya que los innitos n umeros
podran obtenerse multiplicando de distintas formas y a distintas potencias nitos primos.) La
demostracion que damos a continuacion fue hecha por Euclides alrededor el a no 300 AC. Hay
muchas otras demostraciones de este hecho (por ejemplo otra conocida se basa en que la serie
armonica diverge).
Consecuencia Existen innitos primos positivos distintos.
Prueba. Supongamos que no es as y que hay solo un n umero nito de primos positivos.
O sea que el conjunto de primos positivos es = { j
1
, . . . , j

} . Consideremos el siguiente
n umero natural ` :
` := j
1
j
2
j

+ 1.
Dado que ` 2 pues 2 , existe por la proposicion anterior un primo positivo j
.
que
divide a ` . Pero
j
.
` y j
.
j
1
j
2
j

= j
.
1,
contradiccion que proviene de suponer que hay solo nitos primos.
Otra consecuencia de este hecho es la famosa Criba de Eratostenes de Cirene ( 276 194 AC),
que construye recursivamente la lista de todos los primos hasta un n umero dado. Por ejemplo aqu
la lista de primos hasta 57 :
Criba de Eratostenes (hasta 57)
Se escribe la lista de todos los n umeros del 2 al 57 :
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, , 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57 .
32
Se tachan los m ultiplos estrictos del primero de la lista:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, , 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57 .
El primero que sobrevivio, en este caso el 3 , es claramente primo, ya que sino tendra que
ser divisible por un primo mas chico que el.
Se tachan los m ultiplos estrictos (no tachados en la lista) del 3 :
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, , 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57 .
El primero que sobrevivio, en este caso el 5 , es claramente primo, ya que sino tendra que
ser divisible por un primo mas chico que el.
Se repite el procedimiento con el 5 :
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, , 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57 .
Se repite el procedimiento con el 7 :
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, , 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57 .
Se puede probar que alcanza hacer esto hasta que se alcanzo el ultimo primo j

57 , es
decir hasta el primo j = 7 , pues todo n umero compuesto n es divisible por alg un primo
menor o igual que su raz cuadrada (probarlo). Luego la lista que quedo de n umeros no
tachados son todos los primos menores o iguales que 57 , es decir:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53.
Digresion sobre Complejidad (1) Dado un n umero o , hay un algoritmo muy natural para
establecer si o es primo o no: simplemente se divide a o por todos los n umeros c menores que
el (o por todos los primos menores que el, produciendolos por ejemplo con la criba, o en realidad
alcanza con dividirlo por todos los primos menores que

o , por que?) y si nunca da resto 0, es
que o es primo. Pero este algoritmo no es muy satisfactorio ya que la cantidad de candidatos a
divisores c se asemeja a

o (mas precisamente a

o, ln(o) como consecuencia del teorema de

distribucion de primos conjeturado por Adrien-Marie Legendre en 1798, renado posteriormente
por Carl-Fiedrich Gauss, y demostrado independientemente por Jacques Hadamard y Charles-Jean
de la Vallee Poussin en 1896): es comunmente aceptado que para que un algoritmo sea eciente, el
n umero de cuentas que realiza tiene que ser lineal en el tama no de la entrada, en este caso log
2
(o) ,
o a lo sumo acotado por una potencia ja de ese tama no (esto es lo que se llama un algoritmo
polinomial, o que pertenece a la clase P).
Hasta muy recientemente, el mejor algoritmo para decidir si un n umero o es primo realizaba
log
2
(o)
t log log log(o)
para una constante ja c , o sea era casi polinomial.
En el a no 2002, el informatico indio, Manindra Agrawal, y dos de sus alumnos que estaban iniciando
su tesis doctoral, Neeraj Kayal y Nitin Saxena, mostraron que Primos esta en P, es decir que se
puede establecer si un n umero entero o es primo (o no) haciendo una cantidad de cuentas acotada
por una potencia ja de log
2
(o) .
Este test de primalidad (comunmente denominado test de primalidad AKS) no es en realidad
33
eciente en la practica: para ello se siguen usando tests probabilistas que dan una evidencia
seria de primalidad cuando no pueden probar que un n umero es compuesto, y son sucientes a
efectos practicos. Sin embargo, el resultado de Agrawal, Kayal y Saxena es fantastico, no solo
por lograr nalmente un objetivo teorico de clasicacion buscado por mucha gente durante mucho
tiempo, sino por la simplicidad y elegancia de sus metodos. As fue reconocido por la comunidad
matematica: fue publicado en el a no 2004 en la revista Annals of Mathematics (considerada la
mejor revista matematica del mundo) y le valio a sus autores numerosos premios (y a los dos
jovenes excelentes trabajos).
Para terminar esta disgresion, el n umero primo mas grande conocido hoy (pero hoy 11 de Octubre
de 2011, puede cambiar ma nana!) es el primo de Mersenne 2
43112609
1 , que tiene 12978189
dgitos seg un el sitio web [Link]
Digresion sobre Complejidad (2) Un problema de otra ndole, y cuya resolucion hara muy
famoso a cualquiera, es el problema de, dado un n umero o compuesto, encontrarle ecientemente
un factor c no trivial. El mejor algoritmo a la fecha realiza una cantidad de cuentas lineal en
3

o log
2
(o)
23
, y el n umero mas grande que se logro factorizar (anunciado en el 2010), usando
cientos de computadoras que trabajaron durante mas de 2 a nos, tiene 232 dgitos. Se sabe que
este problema esta en NP, lo que hablando sin precision, signica que si un oraculo me provee
de un candidato a factor c , se puede vericar haciendo una cantidad polinomial (en log(o) ) de
cuentas, si c es efectivamente un factor o no de o . Se cree que este problema es dicil, o sea que
no pertenece a la clase P. De hecho la mayora de los protocolos criptogracos (para transmision
de datos en forma segura y secreta) que se utilizan hoy en da estan basados en la dicultad de
factorizar n umeros compuestos grandes (o de problemas relacionados), as que mejor que as sea!
La propiedad esencial de los n umeros primos Si j es un n umero primo (positivo), y o
es cualquiera, entonces 1i
+
(j) = {1, j} y por lo tanto 1iCo:
+
({j, o}) {1, j} : es igual a
{1, j} si j o y es igual a {1} si j o . Por lo tanto el maximo com un divisor entre j y o , es
igual a j cuando j o y es igual a 1 cuando j o :
(j : o) =
{
j si j o
1 si j o
y j o j o.
En particular, observemos que si j y son primos positivos distintos, entonces
j y j
n

n
, :, n .
Volvamos a la Proposicion 6.9 (2) para j y o . En este caso, ella dice: j o / y j o = j / , o
equivalentemente:
j o / j o o j /
Esta es la propiedad mas importante que cumplen los n umeros primos (comparar con el ultimo
inciso de las Propiedades 2.3). Mas a un, esta propiedad caracteriza los n umeros primos: j es
primo si y solo si cada vez que j divide a un producto divide a alguno de los factores. Y la
propiedad se generaliza inmediatamente a
Proposicion 9.2 Sean o, o
1
, . . . , o
n
n umeros enteros, y j un primo. Entonces
j o
1
o
n
j o
.
para alg un i, 1 i n, y j o
n
j o.
34
Estamos ahora en condiciones de demostrar completamente el famoso Teorema Fundamental de
la Aritmetica, piedra angular de toda la teora de n umeros, acerca de la factorizacion unica de
los n umeros como producto de primos. Este teorema era ya conocido por los griegos de la epoca
de Pitagoras (S. VI ac), y es el que justica el interes de los matematicos por conocer mejor el
comportamiento de los primos: como se distribuyen, como conseguirlos, etc.
Teorema 9.3 (Teorema Fundamental de la Aritmetica)
Sea o , o = 0, 1 . Entonces o se escribe en forma unica como producto de primos, (o se
factoriza en forma unica como producto de primos,) es decir
o = j
u
1
1
j
u
2
2
j
u

n
donde los j
|
son primos positivos distintos, y
|
para 1 / n, y la escritura es unica
salvo permutacion de los primos.
Prueba.
Existencia: Nuevamente, alcanza con probar el teorema para o positivo, y se formaliza por in-
duccion en o , o 2 :
j(o) : o admite una factorizacion como producto de primos.
o = 2 : j(2) es verdadera pues 2 = +2
1
.
o 2 :
Si o es un primo j , j(o) es verdadera pues o = j = +j
1
.
Si o no es primo, entonces es divisible por alg un primo positivo j mas chico que el, y por
lo tanto el cociente c = o,j satisface 2 c o 1 . Por hipotesis inductiva, c admite una
factorizacion como producto de primos, en la forma c = j
u
1
1
j
u

n
. Por lo tanto o admite
la factorizacion
o = +jj
u
1
1
j
u

n
.
As, todo n umero distinto de 0, 1 admite una factorizacion como producto de primos.
Unicidad: Supongamos que o = j
u
1
1
j
u

n
=
u
1
1

u

n
en las condiciones del enunciado.
Queremos probar que entonces los signos, los primos y los exponentes coinciden.
Claramente los signos coinciden, as que podemos suponer o positivo.
En la expresion j
u
1
1
j
u

n
=
u
1
1

u

n
, simpliquemos todos los primos comunes que aparecen
a la menor potencia a la que aparecen.
Si al hacer eso no sobra nada, o sea obtenemos 1 = 1 , es que todos los primos y las potencias
coincidan.
Si no pasa eso y sobra algo de alg un lado al menos, obtenemos una expresion igual pero donde
j
.
=

para todos los que sobraron. Podemos suponer sin perdida de generalidad que del lado
izquierdo sobro un j
.
. Entonces tenemos que j
.
divide a lo que sobro del lado derecho o al 1 si
no sobro nada. O sea j
.
1 (lo que es absurdo) o j
.

u
1
1

u

n
, luego existe , tal que j
.

pero j
.
y

son primos distintos. Contradiccion, que proviene de suponer que sobro un primo de
alg un lado.
Remarquemos que un hecho fundamental que se desprende del teorema (y que de hecho aparecio
en la demostracion de la unicidad) es que j o si y solo si j aparece en la factorizacion en primos
35
de o . Luego cualquiera sea o , o = 0 , o es divisible por solo un n umero nito de primos
distintos.
Mas arriba observamos que primos distintos son coprimos entre s, y mas a un, potencias de primos
distintos son coprimas entre s tambien. Luego, aplicando recursivamente la Proposicion 6.9 (1), se
obtiene lo siguiente para j
1
, . . . , j
n
primos distintos dos a dos ,
1
, . . . ,
n
y o arbitrario:
j
u
1
1
j
u
2
2
j
u

n
o

j
u
1
1
o
j
u
2
2
o
.
.
.
j
u

n
o
Introducimos ahora una notacion para simplicar la escritura en el Teorema Fundamental de la
Aritmetica y poder enunciar claramente muchas propiedades que son consecuencia de ese teorema.
Notacion Dado o , o = 0 , y j primo positivo, vamos a notar con

(o) el exponente
exacto de j que aparece en la factorizacion de o como producto de primos. Por ejemplo
2
(24) =
3 ,
3
(24) = 1 y

(24) = 0 para todo j = 2, 3 pues 24 = 2

3
3 . Se observa que entonces
24 = 2
u
2
(24)
3
u
3
(24)
. No exclumos aca los casos o = 1 , pues

(1) = 0 para todo primo j .

Tambien vamos a utilizar la funcion signo, de {0} en {1, +1} :
sg(o) :=
{
1 si o < 0
+1 si o 0
y nalmente notar por el conjunto de los primos positivos, es decir,
:= { j : j primo positivo }.
Con estas convenciones podemos escribir para o , o = 0 :
o = sg(o)

j
u

(o)
,
donde este producto innito esta bien denido ya que hay solo un n umero nito de factores a la
derecha que son distintos de 1 (pues un n umero o = 0 es divisible por solo un n umero nito de
primos distintos).
Siguiendo esta notacion, dado que c =

j
u

()
, la propiedad en el recuadro anterior se
reescribe entonces:
c o j
u

(t)
o, j
Consecuencias Sean o, /, c , no nulos. Entonces
1.

(o) 0 (y es entero) para todo j .

2.

(o) 1 j o , y

(o) j
u
o .
Mas a un,

(o) = j
u
o y j
u+1
o .
36
3.

(o /) =

(o) +

(/) y

(o
n
) = n

(o) para todo j y para todo n .

(Pues si o = sg(o)

j
u

(o)
y / = sg(/)

j
u

(b)
, entonces
o/ = sg(o)sg(/)

j
u

(o)
j
u

(b)
= sg(o)sg(/)

j
u

(o)+u

(b)
.)
4. c o

(c)

(o) para todo j

(combinando la propiedad del recuadro y la propiedad del Inciso 2).
5. c o c
n
o
n
(pues c o

(c)

(o), j n

(c) n

(o), j

(c
n
)

(o
n
), j c
n
o
n
).
Ojo! Tiene que ser el mismo n de los dos lados, si no no vale: por ejemplo c
2
o
3
c o
como lo muestra 8
2
4
3
pero 8 4 .
6.
1i(o) = {c :

(c)

(o), j } y #1i
+
(o) =

(o) + 1),
donde este producto innito esta bien denido pues

(o) + 1 = 1 j o .
7.
(o : /) =

j
min{u

(o),u

(b)}
. (1)
Esto es por lo siguiente: llamemos d al n umero de la derecha de la igualdad (1). Vamos a
ver que d (o : /) y (o : /) d .
Por un lado, como para todo j , min{

(o),

(/)}

(o) y min{

(o),

(/)}

(/) ,
se tiene, aplicando el inciso 4, que d o y d / . Luego d (o : /) .
Pero por otro lado, (o : /) o y (o : /) / implica, aplicando la otra implicacion del inciso
4, que para todo j ,

((o : /))

(o) y

((o : /))

(/) , luego

((o : /))
min{

(o),

(/)} . As, nuevamente, (o : /) d .

8. o / si y solo si

(o) y

(/) no son simultaneamente positivos, cualquiera sea j .

Un comentario sobre el calculo del maximo com un divisor entre dos n umeros via la formula (1):
puede parecer mas simple a primera vista factorizar los n umeros y aplicar esta formula antes que
aplicar el Algoritmo de Euclides. Sin embargo en el caso general, para n umeros muy grandes,
es mas veloz el calculo mediante el algoritmo de Euclides (la cantidad de cuentas a realizar de-
pende polinomialmente del logaritmo en base 2 de los n umeros considerados) que pasando por la
factorizacion, dada la disgresion sobre complejidad (2).
Ejemplos
1i(2
3
5
4
) = { 2
.
5

, 0 i 3, 0 , 4 } , y por lo tanto, 2
3
5
4
tiene (3 + 1)(4 + 1) = 20
divisores positivos distintos, y 2 20 = 40 divisores enteros, positivos y negativos.
1i(10
10
) = { 2
.
5

, 0 i, , 10 } , y por lo tanto, 10
10
tiene (10 + 1)(10 + 1) = 11
2
divisores positivos distintos, y 2 11
2
divisores enteros, positivos y negativos.
37
En general j
u
1
1
j
u

n
tiene (
1
+ 1) (
n
+ 1) divisores positivos y el doble de positivos y
negativos.
Suma de los divisores positivos de 10
10
:

0.,10
2
.
5

=
10

.=0
(
10

=0
2
.
5

) =
10

.=0
(2
.
10

=0
5

) = (
10

=0
5

)(
10

.=0
2
.
)
=
5
11
1
5 1

2
11
1
2 1
= (2
11
1)
5
11
1
4
.
El menor n umero natural n con 12 divisores positivos es el 60 :
Por (5) arriba,

(n) +1) = 12 = 6 2 = 4 3 = 3 2 2 implica que n es de alguna de las

formas siguientes: n = j
11
o n = j
5
o n = j
3

2
o n = j
2
: . Ahora, en cada una de
estas formas el n umero mas chico es 2
11
= 2048 , 2
5
3 = 96 , 2
3
3
2
= 72 y 2
2
3 5 = 60 .
Por lo tanto el menor es n = 60 .
5 o
2
5 o porque 5 es primo. Mas a un, se puede deducir que 25 o
2
5 o :
: 25 o
2
implica en particular que 5 o
2
(por ser un factor de 25 ) y por lo tanto 5 o por
lo visto arriba.
: Esta claro que si 5 o entonces 25 o
2
.
4 o
2
4 o pues por ejemplo 4 2
2
pero 4 2 .
10 o
2
10 o aunque 10 no es primo, pero por ser un producto de primos distintos:
10 o
2

25
2 o
2
y 5 o
2

2,5 primos
2 o y 5 o
25
10 = 2 5 o.
Pero mas a un, 100 o
2
10 o :
: 100 o
2
10 o
2
, y por lo visto arriba, se deduce que 10 o .
: Claramente 10 o 100 o
2
.
32 o
2
8 o , pues:
2
5
o
2
=
2
(2
5
)
2
(o
2
) = 5
2
(2) 2
2
(o) =
5
2

2
(o) =
u
2
(o)
0
3
2
(o) = 2
3
o.
Mas a un, lo que vale claramente es 8 o 64 o
2
, ya que si el primo 2 aparece con
exponente 3 en o , aparece con exponente 2.3 en o
2
, y recprocamente si el primo 2 aparece
con exponente 6 en o
2
, aparece con exponente
6
2
en o .
2
4
3
3
5
7
o
3
= 2
2
3 5
3
o , pues:
2
4
3
3
5
7
o
3
2
4
o
3
y 3
3
o
3
y 5
7
o
3
=
2
(2
4
)
2
(o
3
) y
3
(3
3
)
3
(o
3
) y
5
(5
7
)
5
(o
3
)
= 4 3
2
(o) y 3 3
3
(o) y 7 3
5
(o)
= 2
2
(o) y 1
3
(o) y 3
5
(o)
= 2
2
o y 3 o y 5
3
o
= 2
2
3 5
3
o
38

2 , :
Supongamos

2 :

2 =
o
b
, con o, / . Luego

2 / = o = 2 /
2
= o
2
. Entonces,

2
(2 /
2
) =
2
(o
2
) , es decir, 1 +2
2
(/) = 2
2
(o) . Absurdo comparando la paridad de ambos
n umeros.
Existen o, / tales que 12 o
2
= /
4
?
En tal caso se tiene
2
(12 o
2
) =
2
(/
4
) y
3
(12 o
2
) =
3
(/
4
) , es decir 2 +2
2
(o) = 4
2
(/) y
1 + 2
3
(o) = 4
3
(/) .
La primer armacion no presenta contradiccion pero la segunda s, por comparacion de
paridades. Luego no existen.
Cual es el mnimo n tal que 1200 n es un cubo?
2
4
3 5
2
n = o
3
implica que los exponentes del termino de la izquierda tienen que ser
m ultiplos de 3 . La forma mas economica de lograrlo es tomando n = 2
2
3
2
5 = 180 .
Divisores positivos n de 1260 que satisfacen que (n : 150) = 10 :
Por la forma de los divisores positivos de 1260 = 2
2
3
2
5 7 , se tiene que n = 2
.
3

5
|
7

con 0 i, , 2 y 0 /, 1 . Por otro lado (n : 2 3 5

2
) = 10 = 2 5 implica que:
min{i, 1} = 1, min{,, 1} = 0, min{/, 2} = 1, min{, 0} = 0,
es decir, i = 1 o 2 , , = 0 , / = 1 y = 0 o 1 . Los posibles valores de n son entonces:
2 5 = 10 , 2
2
5 = 20 , 2 5 7 = 70 y 2
2
5 7 = 140 .
Posibles valores de (o / (o + /) : o
2
+ /
2
) para o / :
Si aqu buscamos como siempre la forma de un divisor com un d operando con las expresiones
o / (o + /) y o
2
+ /
2
, no podemos nunca independizarnos de o o de / . Pero podemos
aprovechar la propiedad de caracterizacion de los primos para trabajar de la forma siguiente:
Sea d := (o / (o + /) : o
2
+ /
2
) , y sea j un primo. Se tiene
j d j o / (o + /) y j o
2
+ /
2
.
Ahora bien:
j o / (o + /) j o o j / o j o + /.
Miremos cada combinacion de casos posibles por separado:
j o y j o
2
+ /
2

primo
j o
2
y j o
2
+ /
2
j o
2
y j /
2

primo
j o y j /,
es una contradiccion pues o / por hipotesis: no puede haber ning un primo que divida a
ambos a la vez. De la misma forma:
j / y j o
2
+ /
2

primo
j /
2
y j o
2
+ /
2
j /
2
y j o
2

primo
j / y j o,
contradiccion. Finalmente:
j o+/ y j o
2
+/
2
j (o/)(o+/) y j o
2
+/
2
j o
2
/
2
y j o
2
+/
2
j 2o
2
y j 2/
2
.
Luego j (2o
2
: 2/
2
) = 2(o
2
: /
2
) = 2 por ser o
2
/
2
al ser o / por hipotesis.
Se concluye que el unico primo posible que puede dividir al mcd d es el primo 2 . Luego
d = 2
|
para alg un / 0 .
39
Vamos a analizar ahora que valores posibles puede tomar / . Dado que solo interviene el
primo 2 , que tiene que ver con la paridad, podemos por ejemplo distinguir los casos o par,
/ impar; o impar, / par; y o y / impares, es decir o / 1 (mod 2) (dado que el caso
o y / pares no se puede dar por ser o / ).
o 1 (mod 2) y / 0 (mod 2) o
2
+ /
2
1 (mod 2) , luego 2 no es un divisor
com un, es decir, 2 d en este caso. Por lo tanto d = 1 .
o 0 (mod 2) y / 1 (mod 2) es igual al caso anterior: d = 1 .
o / 1 (mod 2) o + / 0 (mod 2) y o
2
+ /
2
0 (mod 2) , luego 2 o/(o + /)
y 2 o
2
+ /
2
, es decir 2 d y en este caso d = 2
|
con / 1 .
Pero al ser o y / impares, se tiene que 2
|
o y 2
|
/ , luego 2
|
o/(o + /) implica
2
|
o +/ . Junto con 2
|
o
2
+/
2
, el mismo analisis hecho arriba implica que 2
|
2 (o
2
:
/
2
) = 2 , es decir / 1 . Por lo tanto en este caso d = 2 .
10 Mnimo Com un M ultiplo
Denicion 10.1 (Mnimo Com un M ultiplo)
Sean o, / , no nulos. El mnimo com un m ultiplo entre o y / es el menor de los m ultiplos
comunes positivos de o y / .
Claramente ese n umero existe, ya que hay que buscarlo entre los m ultiplos comunes positivos
menores o iguales que o / , y es unico, por ser el menor.
El mnimo com un m ultiplo entre o y / se nota mcm(o, /) o [o : /] que es la notacion que
adoptamos aqu. Es entonces caracterizado por:
[o : /] , o [o : /], / [o : /] y si : es tal que o : y / :, entonces [o : /] :.
Ejemplos
[o : /] = [o : /] = [o : /] = [o : /] = [o : /] .
Para todo o , se tiene [o : 1] = o
/ o [o : /] = o .
Pero el mnimo com un m ultiplo tambien tiene una caracterizacion conocida en terminos de los
factores primos de los n umeros o y / :
Observacion 10.2
[o : /] =

j
max{u

(o),u

(b)}
. (2)
Prueba. Llamemos c al n umero de la derecha de la igualdad (2). Vamos a ver que [o : /] c
y c [o : /] .
Por un lado, como para todo j ,

(o) max{

(o),

(/)} y

(/) max{

(o),

(/)} , se
tiene que o c y / c . Luego [o : /] c .
Pero por otro lado, o [o : /] y / [o : /] implica que para todo j ,

(o)

([o : /]) y

(/)

([o : /]) , luego max{

(o),

(/)}

([o : /]) . As c [o : /] , y, al ser ambos positivos,

c [o : /] .
40
De la misma forma que se probo que si o [o : /] y / [o : /] , entonces c [o : /] en la demostracion
anterior, se prueba que si : no nulo es tal o : y / :, entonces c :, pero c es el mnimo
com un m ultiplo! Luego:
Consecuencia 10.3 Sean o, /, : no nulos. Entonces:
o : y / : = [o : /] :.
Ejemplo Sean o = 2
7
5
2
7
6
13 y / = 2
5
3
4
7
6
13
2
19 . Entonces
(o : /) = 2
5
7
6
13 y [o : /] = 2
7
3
4
5
2
7
6
13
2
19.
Observemos que
o / = 2
7+5
3
0+4
5
2+0
7
6+6
13
1+2
19
0+1
= 2
5+7
3
0+4
5
0+2
7
6+6
13
1+2
19
0+1
= (o : /) [o : /].
Este hecho se generaliza ya que para todo j , se tiene que

(o) +

(/) = min{

(o),

(/)}+
max{

(o),

(/)} :
Proposicion 10.4 Sean o, / , no nulos, entonces
o / = (o : /) [o : /].
En particular, si o / , entonces [o : /] = o / .
Esto da una alternativa para calcular el mnimo com un m ultiplo cuando uno no conoce la fac-
torizacion de los n umeros. De hecho esta forma de calcular el mnimo com un m ultiplo es para
n umeros grandes mas veloz que factorizar los n umeros para luego aplicar la formula (2), ya que
calcular el maximo com un divisor por el algoritmo de Euclides es para n umeros grandes mas veloz
que factorizar.
Ejemplo Determinacion de todos los pares de n umeros o, / que satisfacen que
(o : /) = 2
2
3 17 y [o : /] = 2
5
3 5
2
17
2
:
Una forma: Se tiene que o / = (o : /)[o : /] = 2
7
3
2
5
2
17
3
, es decir o = 2
.
3

5
|
17

y
/ = 2
.

5
|

17

, con
i + i

= 7, min{i, i

} = 2, max{i, i

} = 5
, + ,

= 2, min{,, ,

} = 1, max{,, ,

} = 1
/ + /

= 2, min{/, /

} = 0, max{/, /

} = 2
+

= 3, min{,

} = 1, max{,

} = 2
Se deduce que i = 2, i

= 5 o i = 5, i

= 2 , , = ,

= 1 , / = 0, /

= 2 o / = 2, /

= 0 y
= 1,

= 2 o = 2,

= 1 . Todos los pares posibles o, / son entonces:

o = 2
2
3
1
5
0
17
1
, / = 2
5
3
1
5
2
17
2
o = 2
5
3
1
5
0
17
1
, / = 2
2
3
1
5
2
17
2
o = 2
2
3
1
5
2
17
1
, / = 2
5
3
1
5
0
17
2
o = 2
2
3
1
5
0
17
2
, / = 2
5
3
1
5
2
17
1
o = 2
5
3
1
5
2
17
1
, / = 2
2
3
1
5
0
17
2
o = 2
5
3
1
5
0
17
2
, / = 2
2
3
1
5
2
17
1
o = 2
2
3
1
5
2
17
2
, / = 2
5
3
1
5
0
17
1
o = 2
5
3
1
5
2
17
2
, / = 2
2
3
1
5
0
17
1
41
Otra forma: (tal vez mas sencilla) es pensando en coprimizar: recordemos que o = (o : /) o

y
/ = (o : /) /

con o / . Luego (o : /)
2
o

= o/ = (o : /)[o : /] , es decir
o

=
[o : /]
(o : /)
=
2
5
3 5
2
17
2
2
2
3 17
= 2
3
5
2
17, con o

.
Al ser o

no puede aparecer un mismo primo simultaneamente en o

y /

, y por lo tanto las

posibilidades son (eligiendo cuales son los primos que aparecen en o

y luego los restantes estaran

en /

):
o

= 1, /

= 2
3
5
2
17
o

= 2
3
, /

= 5
2
17
o

= 5
2
, /

= 2
3
17
o

= 17, /

= 2
3
5
2
o

= 2
3
5
2
, /

= 17
o

= 2
3
17, /

= 5
2
o

= 5
2
17, /

= 2
3
o

= 2
3
5
2
17, /

= 1.
Multiplicando estos n umeros por (o : /) = 2
2
3 17 se obtienen todos los pares (que obviamente
coinciden con los que obtuvimos con la otra forma de resolver el problema).
11 El Peque no Teorema de Fermat (PTF)
Este teorema es uno de los tantos que debemos al abogado y matematico frances Pierre de Fermat
(16011665). Fermat, el mayor matematico amateur de todos los tiempos, dejo una obra impor-
tantsima en Teora de N umeros, ademas de ser un pionero en Teora de Probabilidades, Calculo
Variacional y Geometra Analtica. Posea la traduccion latina de la Aritmetica de Diofanto, re-
alizada por Bachet a nes del Siglo XVI, y tena la particularidad de escribir en los margenes de
ese libro enunciados matematicos y comentarios, la mayora de las veces sin demostraciones. El
Peque no Teorema fue luego demostrado y generalizado por el matematico suizo Leonhard Euler
(17071783). Euler demostro la casi totalidad de los resultados enunciados por Fermat, con la
excepcion de la armacion inspirada en el teorema de Pitagoras conocida como el Ultimo
Teorema de Fermat:
Cualquiera sea n 2 , no existen o, /, c tales que o
n
+ /
n
= c
n
.
Este fue probado recien en los a nos 19931994 por el matematico ingles Andrew Wiles, con la
ayuda parcial de su discpulo R. Taylor.
Teorema 11.1 (Peque no Teorema de Fermat)
Sean o y j un primo positivo. Entonces
1. o

o (mod j)
2. j o = o
1
1 (mod j)
Observaciones
El teorema es falso en general si j no es primo: por ejemplo 3
4
= 81 3 (mod 4) .
42
Sin embargo existen n umeros n no primos para los cuales vale el enunciado del peque no
teorema: o
n
o (mod n) para todo o . Esos n umeros se suelen llamar seudoprimos
o primos de Carmichael (por mas que no sean primos) seg un el matematico que descubrio
en 1909 el mas chico de ellos, el n umero n := 561 = 3 11 17 . En 1995 se probo que existen
innitos seudoprimos.
Las dos armaciones del teorema son equivalentes:
(1 2): Por hipotesis, o

o (mod j) . Si j o , es decir o j , se puede simplicar un

o de los dos lados (justicar!) y queda o
1
1 (mod j) .
(2 1): Hay que probar que para o cualquiera, o

o (mod j) . Si j o , por
(2) vale que o
1
1 (mod j) , luego multiplicando por o se obtiene o

o (mod j) .
Mientras que si j o , entonces tanto o como o

son congruentes con 0 modulo j (pues j

los divide, as, o

0 o (mod j) tambien.
Prueba del Teorema 11.1.
Por la observacion anterior, para probar el Teorema alcanza con probar el caso (2) en que j o ,
es decir o j , que es el caso interesante y no trivial.
Fijamos o tal que j o y denimos la siguiente funcion:
: {1, 2, . . . , j 1} {1, 2, . . . , j 1}
/ :

(/ o)
Por ejemplo, (1) = :

(o), (2) = :

(2 o), (3) = :

(3 o) , etc. (Observemos en particular que

(/) = :

(/ o) / o (mod j) .)
Veamos primero que esta funcion esta bien denida (es decir que la imagen Im() de la funcion
realmente esta includa en el codominio) y luego que es biyectiva.
Im() {1, 2, . . . , j 1} :
Por denicion de resto modulo j , esta claro que Im() {0, 1, 2, . . . , j1} . Hay que probar
que nunca se obtiene el 0 , es decir que no existe / {1, . . . , j 1} tal que (/) = 0 . Pero
(/) = 0 :

(/ o) = 0 j / o
primo
j / o j o,
lo que es absurdo pues por hipotesis j o y j / por ser / {1, . . . , j 1} mas chico que
j .
Para probar que es biyectiva, dado que es una funcion de un conjunto nito en s mismo,
alcanza con probar que es inyectiva:
Supongamos que para 1 , / j 1 , se tiene que (/) = (,) , queremos probar que
entonces / = , . Pero de la misma forma que probamos la buena denicion,
(/) = (,) :

(/ o) = :

(, o) j / o , o = (/ ,) o
primo
j / , o j o,
lo que se cumple unicamente si j / , pues j o . Ahora bien, como 1 , / j 1 ,
se tiene que / , {0, . . . , j 1} , luego
j / , / , = 0 / = ,.
43
Por lo tanto es biyectiva, es decir suryectiva tambien. As
Im() = {1, 2, . . . , j 1} = (1) (2) (j 1) = 1 2 (j 1) =
:

(o) :

(2 o) :

((j 1) o) = 1 2 (j 1) =
o 2 o (j 1) o 1 2 (j 1) (mod j) =
(j 1)! o
1
(j 1)! (mod j) = o
1
1 (mod j),
pues se puede simplicar (j1)! en el ultimo renglon dado que j (j1)! (ya que j (j1)!
si y solo si existe i con 1 i j 1 tal que j i ).
Consecuencia 11.2 Sean o , n y j primo positivo. Si j o , entonces n :
(mod (j 1)) = o
n
o
:
(mod j) . En particular:
j o = o
n
o
:
1
(n) (mod j)
Prueba.
n = / (j 1) + : = o
n
= o
|(1)+:
= (o
(1)
)
|
o
:

PTF
1
|
o
:
o
:
(mod j).
Ejemplos
:
11
(27
2154
) :
Como 27 5 (mod 11) , 27
2154
5
2154
(mod 11) , y como 11 5 , se tiene que
2154 4 (mod 10) = 5
2154
5
4
25
2
3
2
9 (mod 11).
Por lo tanto :
11
(27
2154
) = 9.
:
11
(24
13
1521
) :
24
13
1521
2
13
1521
(mod 11) y 11 2 = 13
1521
? (mod 10)
13
1521
3
1521
(3
2
)
760
3 (1)
760
3 3 (mod 10) =
2
13
1521
2
3
8 (mod 11).
Por lo tanto :
11
(24
13
1521
) = 8.
Determinacion de los n tales que 4
n
1 (mod 7) :
4
n
4
:
(mod 7) si n : (mod 6) , por el PTF ya que 7 4 . Luego alcanza con investigar
los valores de 4
:
con 0 : < 6 :
n 0 (mod 6) = 4
n
4
0
1 (mod 7),
n 1 (mod 6) = 4
n
4
1
4 (mod 7),
n 2 (mod 6) = 4
n
4
2
2 (mod 7),
n 3 (mod 6) = 4
n
4
3
4
2
4 2 4 1 (mod 7),
n 4 (mod 6) = 4
n
4
4
4
3
4 1 4 4 (mod 7),
n 5 (mod 6) = 4
n
4
5
4
3
4
2
1 2 2 (mod 7).
Se concluye que 4
n
1 (mod 7) n 1 (mod 6) o n 3 (mod 6) , es decir:
4
n
1 (mod 7) n 0 (mod 3).
44
n , 7 o
360
o
60
:
Aqu para usar la version mas rapida del PTF, hay que separar los casos en que 7 o y 7 o :
7 o = o
360
0 (mod 7) y o
60
0 (mod 7) = o
360
o
60
(mod 7),
7 o = o
360
1 (mod 7) y o
60
1 (mod 7) = o
360
o
60
(mod 7).
Por lo tanto, en ambos casos, o
360
o
60
(mod 7) .
12 Teorema Chino del Resto (TCR)
Este teorema, sobre la resolucion simultanea de varias congruencias, se encontraba ya en su forma
original (sin demostracion) en un libro de matematica chino en el Siglo III A.C. En el captulo
8 aprendimos a resolver ecuaciones de congruencia: para cada ecuacion de la forma oA c
(mod /) sabemos producir la ecuacion equivalente (es decir con las mismas soluciones) mas simple
posible, que es de la forma A r
0
(mod /

) . Ahora se trata de resolver sistemas de ecuaciones

de congruencia de la forma

A c
1
(mod /
1
)
A c
2
(mod /
2
)
.
.
.
A c
n
(mod /
n
)
(3)
donde c
1
, . . . , c
n
y /
1
, . . . , /
n
no nulos. Aqu resolver signica obtener una descripcion
equivalente via una ecuacion de congruencia simple (que tenga las mismas soluciones) de la forma
A r
0
(mod /).
Adoptamos como en el Captulo 8 la notacion para sistemas de ecuaciones de congruencia
equivalentes, o sea con las mismas soluciones.
Se utilizaran sistematicamente las propiedades siguientes, que ya fueron mencionadas, ademas del
hecho que ya sabemos resolver una ecuacion de congruencia:
Propiedades 3.3: Dados r, c, /, d, / con /, d, / no nulos, se tiene
r c (mod /) y d / = r c (mod d) ,
r c (mod /) / r / c (mod (/ /)) .
Lo que implica que A c (mod /) / A / c (mod (/ /)) .
Como consecuencia de la Proposicion 6.9 (1): Dados c, /
1
, /
2
, . . . , /
n
con /
.
/

para i = , ,
se tiene

A c (mod /
1
)
A c (mod /
2
)
.
.
.
A c (mod /
n
)
A c (mod /
1
/
2
/
n
) (4)
Ejemplos

A 3 (mod 22)
A 3 (mod 5)
A 3 (mod 21)
A 3 (mod 22 5 21),
por la Propiedad (4), pues 22 = 2 11, 5 y 21 = 3 7 son coprimos dos a dos.
45
De la misma forma:
A 50 (mod 22521)

A 50 (mod 22)
A 50 (mod 5)
A 50 (mod 21)

A 6 (mod 22)
A 0 (mod 5)
A 8 (mod 21)
.

{
A 3 (mod 22)
A 4 (mod 11)

A 3 (mod 2)
A 3 (mod 11)
A 4 (mod 11)

A 1 (mod 2)
A 3 (mod 11)
A 4 (mod 11)
,
y luego el sistema no tiene solucion (es incompatible) pues la segunda y la tercer ecuacion a
la derecha no pueden satisfacerse simultaneamente.

{
A 3 (mod 22)
A 4 (mod 8)

A 1 (mod 2)
A 3 (mod 11)
A 4 (mod 8)
y luego es incompatible pues la tercer ecuacion a la derecha implica que si hubiera una solucion
r, entonces satisfacera tambien r 4 (mod 2) (aplicando una de las propiedades recor-
dadas mas arriba), es decir r 0 (mod 2) , que es claramente incompatible con satisfacer la
primer ecuacion.

{
A 1 (mod 4)
A 5 (mod 8)
A 5 (mod 8)
pues si r cumple la segunda ecuacion, cumple automaticamente la primera:
r 5 (mod 8) = r 5 (mod 4) = r 1 (mod 4) . La otra implicacion es obvia.

A 3 (mod 22)
A 5 (mod 8)
A 17 (mod 20)

A 1 (mod 2)
A 3 (mod 11)
A 5 (mod 8)
A 1 (mod 4)
A 2 (mod 5)

A 5 (mod 8)
A 3 (mod 11)
A 2 (mod 5)
pues si r satisface r 5 (mod 8) , entonces r 5 (mod 4) y r 5 (mod 2) , es decir
r 1 (mod 2) y r 1 (mod 4) (si en el medio se cumple la tercer ecuacion se cumplen
automaticamente la primera y la ultima).
En estos ejemplos se ve que cuando el sistema no es incompatible, se reduce a resolver un sistema
(3) pero con la condicion de que los /
.
son coprimos dos a dos. En esa situacion vale el
teorema siguiente:
Teorema 12.1 (Teorema Chino del Resto)
Sean c
1
, . . . , c
n
y /
1
, . . . , /
n
no nulos, con /
.
/

para i = , . Entonces el sistema de

ecuaciones de congruencia

A c
1
(mod /
1
)
A c
2
(mod /
2
)
.
.
.
A c
n
(mod /
n
)
46
tiene soluciones.
Mas a un,

A c
1
(mod /
1
)
A c
2
(mod /
2
)
.
.
.
A c
n
(mod /
n
)
A r
0
(mod /
1
/
2
/
n
) ,
donde r
0
es una solucion particular.
Finalmente, existe un unico r
0
as con 0 r
0
< /
1
/
2
/
n
.
Prueba.
Supongamos que ya mostramos que el sistema tiene soluciones. Entonces, sea r
0
una solucion
particular, es decir r
0
satisface

r
0
c
1
(mod /
1
)
r
0
c
2
(mod /
2
)
.
.
.
r
0
c
n
(mod /
n
)
.
En ese caso, por transitividad y aplicando la propiedad descrita en la Formula (4), tendremos para
una solucion cualquiera r:

r c
1
(mod /
1
)
r c
2
(mod /
2
)
.
.
.
r c
n
(mod /
n
)

r r
0
(mod /
1
)
r r
0
(mod /
2
)
.
.
.
r r
0
(mod /
n
)
r r
0
(mod /
1
/
2
/
n
),
O sea probamos la equivalencia enunciada en el Teorema.
El unico r
0
que satisface 0 r
0
< /
1
/
n
se obtiene reemplazando la solucion particular elegida
por :
b
1
b

(r
0
) .
Para probar que existen soluciones (y hallar una solucion particular r
0
), vamos a subdividir el
sistema (3) en n sistemas mas simples y probar que cada uno de ellos tiene soluciones. Estos
sistemas o
1
, o
2
, . . . , o
n
son:
o
1
:

A c
1
(mod /
1
)
A 0 (mod /
2
)
A 0 (mod /
3
)
.
.
.
A 0 (mod /
n
)
y
o
2
:

A 0 (mod /
1
)
A c
2
(mod /
2
)
A 0 (mod /
3
)
.
.
.
A 0 (mod /
n
)
y . . . y
o
n
:

A 0 (mod /
1
)
A 0 (mod /
2
)
.
.
.
A 0 (mod /
n1
)
A c
n
(mod /
n
)
Supongamos que podemos probar que cada uno de estos sistemas o

, 1 n tiene soluciones,
y encontramos para cada uno una solucion particular r

, es decir:
o
1
:

r
1
c
1
(mod /
1
)
r
1
0 (mod /
2
)
r
1
0 (mod /
3
)
.
.
.
r
1
0 (mod /
n
)
y
o
2
:

r
2
0 (mod /
1
)
r
2
c
2
(mod /
2
)
r
2
0 (mod /
3
)
.
.
.
r
2
0 (mod /
n
)
y . . . y
o
n
:

r
n
0 (mod /
1
)
r
n
0 (mod /
2
)
.
.
.
r
n
0 (mod /
n1
)
r
n
c
n
(mod /
n
)
47
Entonces si denimos
r
0
:= r
1
+ r
2
+ r
3
+ + r
n
,
se satisface que

r
1
+ r
2
+ r
3
+ + r
n
c
1
+ 0 + 0 + + 0 (mod /
1
)
r
1
+ r
2
+ r
3
+ + r
n
0 + c
2
+ 0 + + 0 (mod /
2
)
.
.
.
r
1
+ r
2
+ r
3
+ + r
n
0 + 0 + + 0 + c
n
(mod /
n
)
=

r
0
c
1
(mod /
1
)
r
0
c
2
(mod /
2
)
.
.
.
r
0
c
n
(mod /
n
)
es decir, r
0
es una solucion (particular) del sistema original, y en particular el sistema original
tiene soluciones.
Aplicando lo que se hizo en el Captulo 8, vamos a ver que todos los sistemas o

, 1 n,
admiten soluciones y vamos a elegir para cada uno de ellos una solucion particular r

.
Miremos el sistema o
1
: Como /
2
, /
3
, . . . , /
n
son todos coprimos entre s, si ponemos 1
1
:=
/
2
/
3
/
n
, se tiene la equivalencia descrita en la formula (4):

A c
1
(mod /
1
)
A 0 (mod /
2
)
A 0 (mod /
3
)
.
.
.
A 0 (mod /
n
)

{
A c
1
(mod /
1
)
A 0 (mod 1
1
)
.
La segunda ecuacion a la derecha indica que cualquier solucion r tiene que satisfacer que r = 1
1
j
para alg un j , y luego para cumplir con la primer ecuacion, se tiene que satisfacer 1
1
j c
1
(mod /
1
) , o sea hay j es una solucion de la ecuacion
1
1
Y c
1
(mod /
1
). (5)
Se observa que 1
1
/
1
, por ser 1
1
= /
2
/
n
y los /
.
coprimos dos a dos. Por lo tanto,
por el Corolario 8.3, la ecuacion (5) tiene soluciones. Si j
1
es una solucion particular, entonces
claramente r
1
:= /
1
j
1
es una solucion particular del sistema o
1
.
Veamos de forma analoga que para todo , 1 n, el sistema
o

A 0 (mod /
1
)
.
.
.
A 0 (mod /
1
)
A c

(mod /

)
A 0 (mod /
+1
)
.
.
.
A 0 (mod /
n
)
admite soluciones y por lo tanto se puede elegir para el una solucion particular r

.
Denamos 1

:=

=
/

y repitamos lo que se hizo arriba para o

1
. Se tiene 1

por ser
todos los /
.
coprimos dos a dos. Luego, por el Corolario 8.3, la ecuacion de congruencia
1

Y c

(mod 1

)
48
tiene soluciones, y si j

es una solucion particular, entonces, como arriba, r

:= 1

es una
solucion particular del sistema o

.
Ejemplos

A 4 (mod 8)
A 10 (mod 35)
A 1 (mod 3)
Como 8, 35 y 3 son coprimos 2 a 2, por el Teorema 12.1, el sistema tiene soluciones y es
equivalente a A r
0
(mod 8 35 3) , es decir A r
0
(mod 840) , donde r
0
es una solucion
particular.
Para hallar una solucion particular r
0
, se consideran los tres sistemas mas simples:
o
1
:

A 4 (mod 8)
A 0 (mod 35)
A 0 (mod 3)
,
o
2
:

A 0 (mod 8)
A 10 (mod 35)
A 0 (mod 3)
,
o
3
:

A 0 (mod 8)
A 0 (mod 35)
A 1 (mod 3)
.
Solucion particular para o
1
:

A 4 (mod 8)
A 0 (mod 35)
A 0 (mod 3)

{
A 4 (mod 8)
A 0 (mod 35 3)
Es decir una solucion r satisface r = 105 j donde j es solucion de la ecuacion 105 Y 4
(mod 8) , o sea de la ecuacion Y 4 (mod 8) . Una solucion particular es j
1
= 4 , y por lo
tanto r
1
= 105 j
1
= 420 es una solucion particular del sistema o
1
.
Solucion particular para o
2
:

A 0 (mod 8)
A 10 (mod 35)
A 0 (mod 3)

{
A 10 (mod 35)
A 0 (mod 8 3)
.
Es decir una solucion r satisface r = 24 j donde j es solucion de la ecuacion 24 Y 10
(mod 35) . Aplicando el algoritmo de Euclides se obtiene que
1 = 11 35 16 24 = 24 (16) 1 (mod 35)
= 24 (160) 10 (mod 35) = 24 15 10 (mod 35).
Luego, una solucion particular es j
2
= 15 , y por lo tanto r
2
= 24 j
2
= 360 es una solucion
particular del sistema o
2
.
Solucion particular para o
3
:

A 0 (mod 8)
A 0 (mod 35)
A 1 (mod 3)

{
A 1 (mod 3)
A 0 (mod 8 35)
.
49
Es decir una solucion r satisface r = 280 j donde j es solucion de la ecuacion 280 Y 1
(mod 3) , o sea de la ecuacion Y 1 (mod 3) . Una solucion particular es j
3
= 1 , por lo
tanto r
3
= 280 j
3
= 280 es una solucion particular de o
3
.
Por lo tanto, aplicando la construccion del Teorema 12.1,
r
0
:= r
1
+ r
2
+ r
3
= 240 + 360 + 280 = 1060
es una solucion particular del sistema original, y este es equivalente a A 1060 (mod 840) .
Claramente se puede achicar r
0
utilizando que 1060 220 (mod 840) , y de esa manera se
obtiene 0 r
0
< 840 : se tiene entonces la equivalencia

A 4 (mod 8)
A 10 (mod 35)
A 1 (mod 3)
A 220 (mod 840).
(Y r
0
= 220 es la unica solucion particular del sistema que satisface 0 r
0
< 840 .)

A 3 (mod 10)
A 1 (mod 11)
A 3 (mod 7)
Nuevamente, 10, 11 y 7 son coprimos 2 a 2, luego por el teorema el sistema tiene soluciones
y es equivalente a A r
0
(mod 10 11 7) , es decir A r
0
(mod 770) , donde r
0
es una
solucion particular. Ahora bien, por el Corolario 8.3, la primer y tercer ecuacion se pueden
juntar en la ecuacion A 3 (mod 70) , al ser 10 y 7 coprimos. Por lo tanto para hallar
una solucion particular, es suciente aqu considerar los dos sistemas:
o
1
:
{
A 3 (mod 70)
A 0 (mod 11)
,
o
2
:
{
A 0 (mod 70)
A 1 (mod 11)
.
Solucion particular para o
1
:
Una solucion particular r
1
satisface r
1
= 11 j
1
donde j
1
es solucion particular de la
ecuacion 11 Y 3 (mod 70) . Por ejemplo j
1
= 13 , y por lo tanto r
1
= 11 13 = 143 .
Solucion particular para o
2
:
Una solucion particular r
2
satisface r
2
= 70 j
2
donde j
2
es solucion particular de la
ecuacion 70 Y 1 (mod 11) , o sea 4 Y 1 (mod 11) . Por ejemplo j
2
= 3 , y por lo tanto
r
2
= 70 j
2
= 210 .
As, r
0
:= r
1
+ r
2
= 143 + 210 = 353 es solucion particular del sistema original, y se tiene
la equivalencia

A 3 (mod 10)
A 1 (mod 11)
A 3 (mod 7)
A 353 (mod 770).
Ejemplos
50
Retomemos el segundo ejemplo arriba:
{
A 3 (mod 70)
A 1 (mod 11)
.
Sabemos que el sistema tiene solucion y es equivalente a A r
0
(mod 770) donde r
0
es
la unica solucion particular del sistema con 0 r
0
< 770 . Veamos si podemos encontrar
ese r
0
a ojo. Para ello investiguemos los valores entre 0 y 770 que cumplen la primer
ecuacion. Estos son:
3, 73, 143, 213, 283, 353, 423, 493, ....
Entre ellos, cual es el unico que cumple tambien la segunda ecuacion?
3, 73, 143, 213, 283, 353 , . . .
Ya esta! encontramos uno, entonces ese es r
0
y el sistema es equivalente a la ecuacion
A 353 (mod 770) !
Volvamos al ultimo ejemplo antes del enunciado del TCR:

A 3 (mod 22)
A 5 (mod 8)
A 17 (mod 20)

A 5 (mod 8)
A 3 (mod 11)
A 2 (mod 5)
Como 8, 11 y 5 son coprimos dos a dos, sabemos que el sistema es equivalente a
A r
0
(mod 8 11 5 = 440)
donde r
0
, es la unica solucion del sistema con 0 r
0
< 440 . Empecemos por investigar los
que cumplen las dos ecuaciones con el modulo mas grande. Para ello escribimos primero los
los n umeros entre 0 y 11 8 = 88 que cumplen la ecuacion con el modulo 11 :
3, 14, 25, 36, 47, 58, 69, . . .
Cual cumple la condicion con el modulo 8 ?
3, 14, 25, 36, 47, 58, 69 , 80, . . .
Luego los que resuelven esas dos ecuaciones son r 69 (mod 88) . Ahora, escribimos los
n umeros entre 0 y 440 que cumplen esa condicion e investigamos cual es el que cumple la
ecuacion con el modulo 5 :
69, 157 , . . .
Ya esta!

A 3 (mod 22)
A 5 (mod 8)
A 17 (mod 20)
A 157 (mod 440).
Un ejemplo donde las ecuaciones iniciales no estan en la forma A c

(mod /

) :

3 A 2 (mod 7)
7 A 5 (mod 8)
6 A 8 (mod 10)
.
51
Primero se puede simplicar todo lo que se puede (por ejemplo un factor com un en la tercer
ecuacion), y luego como los modulos resultan coprimos dos a dos, resolver cada ecuacion en
la forma A c

(mod /

) para aplicar el TCR:

3 A 2 (7)
7 A 5 (8)
6 A 8 (10)

3 A 2 (7)
7 A 5 (8)
3 A 4 (5)

A 3 (7)
A 3 (8)
A 3 (5)
A 3 (280),
pues 7, 8 y 5 son coprimos dos a dos.
Sea r tal que :
9
(4 r) = 2, :
14
(3 r) = 5 y :
20
(3 r) = 1 . Calcular los posibles restos de
dividir a r por 9 14 20 = 2520 :
Se tiene que r es solucion del sistema

4 A 2 (9)
3 A 5 (14)
3 A 1 (20)

2 A 1 (9)
3 A 5 (2)
3 A 5 (7)
3 A 1 (4)
3 A 1 (5)

A 5 (9)
A 1 (2)
A 4 (7)
A 3 (4)
A 2 (5)

A 5 (9)
A 4 (7)
A 3 (4)
A 2 (5)
pues si r 3 (4) , automaticamente se cumple que r 1 (2) . Al resolver este sistema con
el metodo dado por el TCR, se obtiene que el sistema original es equivalente a
A 1607 (9 7 4 5 = 1260) A 347 (1260)
Luego el resto de dividir a r por 1260 es 347 , pero si se quieren los posibles restos de dividir
a r por 2520 = 2 1260 , estos son 347 y 347 + 1260 = 1607 , los dos n umeros entre 0 y
2520 que son congruentes con 347 modulo 1260 .
13 Miscelanea
En esta seccion se dan ejemplos que conectan varios de los resultados vistos. En la medida de lo
posible se enuncia en cada paso el resultado que se aplica y se justica que se esta en las condiciones
para aplicarlo. Se recomienda controlar en detalle cada uno de esos pasos y efectuar las cuentas
que faltan.
Resto de dividir n := 3
2
25
por 390 :
Como 390 = 2 3 5 13 es un producto de primos distintos, se puede averiguar el resto de
dividir n por cada uno de esos primos (aplicando si necesario el PTF) y luego combinar los
resultados por medio del TCR.
:
2
(n) :
3
2
25
1
2
25
1 (mod 2).
:
3
(n) :
3
2
25
0
2
25
0 (mod 3).
:
5
(n) :
52
Por el PTF (Consecuencia 11.2), ya que 5 es primo,
3
2
25

5 3
3
:
4
(2
25
)

4 2
25
3
0
1 (mod 5).
:
13
(n) :
Como 13 3 , para aplicar el PTF, necesitamos conocer :
12
(2
25
) . Para ello alcanza con
conocer :
3
(2
25
) y :
4
(2
25
) y luego aplicar el TCR.
2
25

PTF,3 2
2
:
2
(25)
2
1
2 (mod 3) y 2
25
0 (mod 4) =
TCR
2
25
8 (mod 12).
As,
3
2
25
3
:
12
(2
25
)
3
8
(3
3
)
2
3
2
9 (mod 13)
:
390
(n) :

n 1 (mod 2)
n 0 (mod 3)
n 1 (mod 5)
n 9 (mod 13)

TCR
n 321 (mod 390)
Se concluye que :
390
(3
2
25
) = 321 .
Determinacion de todos los o tales que (12 o
41
o
31
o : 55) = 11 :
Como 55 = 5 11 , para / cualquiera, el valor de (/ : 55) puede ser en principio 1 , 5 ,
11 o 55 . Por lo tanto se observa que
(/ : 55) = 11 11 / y 5 /.
Determinamos entonces para que valores de o , 11 12 o
41
o
31
o y 5 12 o
41
o
31
o :
Para el 11 :
11 12 o
41
o
31
o = o (12 o
40
o
30
1)
11 primo
11 o o 11 12 o
40
o
30
1.
Pero si 11 o , por el PTF, o
n
o
:
10
(n)
(mod 11) . Luego en ese caso,
12 o
40
o
30
1 1 o
0
o
0
1 1 (mod 11) = 11 o
40
o
30
1.
Por lo tanto
11 12 o
41
o
31
o 11 o.
Para el 5 :
5 12 o
41
o
31
o = o (12 o
40
o
30
1)
5 primo
5 o o 5 12 o
40
o
30
1.
Pero si 5 o , entonces, por el PTF, 12 o
40
o
30
1 2 o
0
o
2
1 1 o
2
(mod 5) .
Mirando las posibles congruencias de o
2
(mod 5) , se tiene
1 o
2
0 (mod 5) o
2
1 (mod 5) o 1 o 4 (mod 5).
53
Por lo tanto
5 12 o
41
o
31
o o 0 o 1 o 4 (mod 5),
5 12 o
41
o
31
o o 2 o 3 (mod 5).
Se concluye aplicando el TCR:
(12 o
41
o
31
o : 55) = 11
{
o 0 (mod 11)
o 2 o 3 (mod 5)
o 22 o 33 (mod 55).
Determinacion de todos los o tal que o 1 (mod 4) y (11 o+3 2
150
: 3 o2
151
) = 31 :
Veamos primero cuales son los posibles valores del mcd para ver las condiciones que necesi-
tamos. Sea c un divisor com un. Entonces:
{
c 11 o + 3 2
150
c 3 o 2
151
=
{
c 33 o + 9 2
150
c 33 o 11 2
151
= c 31 2
150
.
{
c 11 o + 3 2
150
c 3 o 2
151
=
{
c 22 o + 3 2
151
c 9 o 3 2
151
= c 31 o.
Ahora bien, c 31 2
150
y c 31 o c (31 2
150
: 31 o) = 31 (2
150
: o) = 31 pues o 1
(mod 4) implica que o es impar, por lo tanto coprimo con 2
150
.
Por lo tanto, el mcd puede ser 1 o 31 . Para que sea 31 nos tenemos que asegurar que
31 11 o +3 2
150
y que 31 3 o 2
151
. Pero por el PTF, al ser 31 primo que no divide a 2 ,
se tiene:
31 11 o + 3 2
150
11 o + 3 2
150
0 (mod 31)
11 o + 3 0 (mod 31) o 11 (mod 31).
Hay que vericar entonces que si o 11 (mod 31) , se tiene que 3 o 2
151
0 (mod 31) :
o 11 (mod 31) =
PTF
3 o 2
151
3 11 2
:
30
(151)
33 2 0 (mod 31).
Se concluye el ejercicio con el TCR:
{
o 1 (mod 4)
o 11 (mod 31)
o 73 (mod 124).
Determinacion de :
315
(5 o
18
+ 7 /
115
+ 8
40
) sabiendo que (5 o : 7 /) = 15 .
Como 315 = 3
2
5 7 , conviene encontrar los restos modulo 3
2
, 5 y 7 para luego aplicar el
TCR.
Para el 3
2
: Como (5 o : 7 /) = 15 , se tiene
15 5 o 3 o y 15 7 /
157
15 /.
En particular, 3 / , y por lo tanto 3
2
o
18
y 3
2
/
115
:
5 o
18
+ 7 /
115
+ 8
40
8
40
(1)
40
1 (mod 9).
54
Para el 5 : Por lo visto arriba, 5 / , y as:
5 o
18
+ 7 /
115
+ 8
40
3
40

PTF
1 (mod 5).
Para el 7 : La condicion (5 o : 7 /) = 15 dice en particular que 7 o (pues sino, como 7 7 / ,
se tendra que 7 divide al mcd). Por lo tanto
5 o
18
+ 7 /
115
+ 8
40

PTF
5 1 + 1
40
6 (mod 7).
Se concluye aplicando el TCR:

5 o
18
+ 7 /
115
+ 8
40
1 (mod 9)
5 o
18
+ 7 /
115
+ 8
40
1 (mod 5)
5 o
18
+ 7 /
115
+ 8
40
6 (mod 7)
5 o
18
+ 7 /
115
+ 8
40
181 (mod 315)
Por lo tanto :
315
(5 o
18
+ 7 /
115
+ 8
40
) = 181 .
Valores de o para los cuales (3 o
98
5 o
50
+ 28 : 140 o) = 14 .
Pongamos / := 3 o
98
5 o
50
+ 28 . Se tiene que 140 = 2
2
5
2
7 y 14 = 2 7 . Luego, por
denicion del mcd, se tiene que cumplir que para todo j primo positivo,

(2 7) = min{

(/),

(2
2
5
2
7 o)}.
Es decir
1 = min{
2
(/),
2
(2
2
5
2
7 o)} = min{
2
(/), 2 +
2
(o)}
2
(/) = 1;
1 = min{
7
(/),
7
(2
2
5
2
7 o)} = min{
7
(/), 1 +
7
(o)}
7
(/) 1,
y si
7
(o) 1 entonces
7
(/) = 1;
0 = min{
5
(/),
5
(2
2
5
2
7 o)} = min{
5
(/), 2 +
5
(o)}
5
(/) = 0;
0 = min{

(/),

(2
2
5
2
7 o)} = min{

(/),

(o)}

(/)

(o) = 0 j = 2, 5, 7.
Miremos la ultima condicion: quienes son los primos que pueden dividir a la vez a / y a o ?
j o y j 3 o
98
5 o
50
+ 28 = j 28 = j = 2 o 7.
Por lo tanto ning un primo distinto de 2 y 7 divide a la vez a / y a o : la ultima condicion
se cumple siempre. Reescribiendo las otras condiciones, se tiene entonces:
(3 o
98
5 o
50
+ 28 : 140 o) = 14

2 3 o
98
5 o
50
+ 28,
pero 2
2
3 o
98
5 o
50
+ 28;
7 3 o
98
5 o
50
+ 28,
pero si 7 o entonces 7
2
3 o
98
5 o
50
+ 28;
5 3 o
98
5 o
50
+ 28.
Para el 2 : 3 o
98
5 o
50
+28 o
98
o
50
0 (mod 2) independientemente de o ya que o
98
y o
50
tienen la misma paridad.
Para el 4 : o 0 (mod 2) 3 o
98
5 o
50
+ 28 0 (mod 4) (pues 2 o 4 o
2
), y o 1
(mod 2) o
2
1 (mod 4) (hacerlo!) 3 o
98
5 o
50
+ 28 3 1
49
1
25
2 (mod 4) .
Se concluye que
2 3 o
98
5 o
50
+ 28 y 4 3 o
98
5 o
50
+ 28 o 1 (mod 2).
55
Para el 5 :
3 o
98
5 o
50
+ 28 3 o
98
+ 28
PTF
{
3 (mod 5) si 5 o
3 o
2
+ 3 (mod 5) si 5 o.
Ahora bien, por tabla, 3 o
2
+ 3 0 (mod 5) o
2
+ 1 0 (mod 5) o 2 o 3 (mod 5) .
Se concluye
5 3 o
98
5 o
50
+ 28 o 0 o 1 o 4 (mod 5).
Para el 7 :
3 o
98
5 o
50
+ 28 3 o
98
5 o
50

{
0 (mod 7) si 7 o
3 o
2
5 o
2
2 o
2
0 (mod 7) si 7 o.
Se concluye que 7 o y por lo tanto, hay que averiguar si puede pasar que 7
2
3 o
98
5 o
50
+28 .
Pero
7 o = 7
2
o
2
= 3 o
98
5 o
50
+ 28 28 0 (mod 7
2
).
Se concluye entonces
7 3 o
98
5 o
50
+ 287 o 0 (mod 7), y en ese caso 7
2
3 o
98
5 o
50
+ 287.
Se concluye aplicando el TCR:

o 1 (mod 2)
o 0 (mod 7)
o 0 o 1 o 4 (mod 5)
o 35 o 21 o 49 (mod 70).
14 Apendice: El Teorema de Euler
La demostracion del Peque no Teorema de Fermat presentada en estas notas fue dada por Euler,
quien en forma natural la generalizo para n umeros n , n 2 , cualesquiera. Se dio cuenta
que la misma demostracion funciona si la funcion esta denida en el conjunto de los n umeros
naturales i n coprimos con n (esta claro que si j es primo, el conjunto {1, 2, . . . , j1} coincide
con el conjunto de los n umeros menores o iguales que j coprimos con j , y que j1 es el cardinal
de ese conjunto). As, para n dado, se denen dos objetos, el conjunto
n
de los n umeros
naturales menores o iguales que n coprimos con el, y la cantidad ,(n) , que es el cardinal de ese
conjunto, es decir ,(n) cuenta la cantidad de n umeros naturales menores o iguales que n que son
coprimos con el:
Denicion 14.1 Sea n dado, se dene

n
:= { / , 1 / n : / n} y ,(n) := #
n
.
Por ejemplo,
1
= {1} y ,(1) = 1 ,
6
= { 1, 5 } y ,(6) = 2 ,
8
= { 1, 3, 5, 7 } y ,(8) = 4 ,

15
= { 1, 2, 4, 7, 8, 11, 13, 14 } y ,(15) = 8 . Ademas si j es primo,

= { 1, 2, . . . , j 1 } y
,(j) = j 1 .
La asignacion , : dene una funcion, la funcion , de Euler, que tiene una gran importancia
en Teora de N umeros, no solo desde el punta de vista teorico sino tambien desde el punto de vista
de la dicultad de su calculo. Nos referimos a ella con mas detalle despues.
56
Teorema 14.2 (Teorema de Euler)
Sean o y n , n 2 . Entonces
o n = o
(n)
1 (mod n)
Prueba.
Vamos a imitar paso por paso la demostracion hecha del peque no teorema de Fermat.
Sea o tal que o n. Denimos la funcion:
:
n

n
/ :
n
(/ o)
(Observemos en particular que (/) = :
n
(/ o) / o (mod n) .)
Veamos primero que esta funcion esta bien denida (es decir que la imagen Im() de la funcion
realmente esta includa en el codominio) y luego que es biyectiva.
Im()
n
:
Por denicion de resto modulo n, esta claro que Im() {0, 1, 2, . . . , n 1} . Falta probar
entonces que para todo /
n
, es decir / n, se tiene que (/) n para garantizar que
(/)
n
. Pero
(/) n :
n
(/ o) n
()
/ o n
on
/ n,
donde () resulta de que : n / o = , n + : n (considerando posibles divisores
comunes).
Para probar que es biyectiva, dado que es una funcion de un conjunto nito en s mismo,
alcanza con probar que es inyectiva:
Supongamos que para / ,
n
, se tiene que (/) = (,) , queremos probar que entonces
/ = , . Pero de la misma forma que probamos esto en el PTF,
(/) = (,) :
n
(/ o) = :
n
(, o) n / o , o = (/ ,) o
no
n / ,.
Ahora bien, como 1 , / n 1 , se tiene que / , {0, . . . , n 1} , luego
n / , / , = 0 / = ,.
Por lo tanto es biyectiva, es decir suryectiva tambien. As
Im() =
n
=

(/) =

/ =

:
n
(/ o) =

/ =

(/ o)

/ (mod n) = (

/) o
(n)

/ (mod n) =o
(n)
1 (mod n),
pues se puede simplicar

/ en el ultimo renglon dado que n es coprimo con ese

termino (al ser coprimo con cada uno de sus factores).
Se obtiene la consecuencia correspondiente, como en el caso del PTF. Se recomienda demostrarla.
57
Consecuencia 14.3 Sean o , n, : . Si n o , entonces : : (mod ,(n)) =
o
n
o
:
(mod n) . En particular:
n o = o
n
o
:
()
(n)
(mod n)
Para aplicar este resultado, es importante poder calcular el valor de ,(n) para n , ademas en
lo posible sin tener que listar todos los elementos de
n
.
Ejemplos
Sea j primo, entonces ,(j) = j 1 .
Sea j primo y n , entonces ,(j
n
) = j
n
j
n1
= (j 1) j
n1
.
Pues en este caso el conjunto

se obtiene del conjunto { 1, 2, . . . , j

n
} quitando todos
los elementos no coprimos con j
n
, es decir divisibles por j . Pero en ese conjunto hay
exactamente j
n1
elementos divisibles por j , estos son: j = 1j, 2j, 3j, . . . , j
n1
j = j
n
.
Vamos a probar ahora un resultado importante que permite calcular el valor de ,(n) conociendo
la factorizacion de n.
Proposicion 14.4 Sean n, : coprimos. Entonces ,(n :) = ,(n) ,(:) .
Prueba.
Esto es una consecuencia del Teorema Chino del Resto! Vamos a denir una biyeccion entre
nn
y
n

n
. Por lo tanto los dos conjuntos tienen el mismo cardinal, es decir ,(n:) = ,(n),(:) .
Denimos
:
nn

n

n
o (:
n
(o), :
n
(o))
La funcion esta bien denida, es decir su imagen esta efectivamente contenida en el
codominio, pues
o n: o n y o : :
n
(o) n y :
n
(o) :.
es suryectiva: Para todo para (o
1
, o
2
)
n

n
, por el Teorema Chino del Resto, dado
que n :, existe o , 0 o n: tal que o o
1
(mod n) , o o
2
(mod :) , es decir
o
1
= :
n
(o) , o
2
= :
n
(o) . Falta vericar que o n: pero eso es por el mismo argumento
que usamos para probar la buena denicion.
es inyectiva ya que si o, o

nn
son tales que (o) = (o

) , es decir, :
n
(o) = :
n
(o

) y
:
n
(o) = :
n
(o

) , entonces o o

(mod n) y o o

(mod :) y por lo tanto, al ser n :,

o o

(mod n:) , luego o = o

pues 1 o, o

n:1 .
Consecuencia 14.5 Sean j
1
, . . . , j
n
primos distintos y
1
, . . . ,
n
. Entonces
,(j
u
1
1
j
u
2
2
j
u

n
) = ,(j
u
1
1
) ,(j
u
2
2
) ,(j
u

n
) = (j
1
1) j
u
1
1
1
(j
2
1) j
u
2
1
2
(j
n
1) j
u

1
n
.
58
Esta formula permite calcular el valor de ,(n) para cualquier n , via su factorizacion. Por
ejemplo ,(400) = ,(2
4
5
2
) = (2 1) 2
3
(5 1) 5 = 160 . Hasta la fecha no se conoce ninguna otra
forma de calcular en general ,(n) , que sea esencialmente mas rapida que esta, que pasa por la
factorizacion. Este hecho fundamenta el interes y la importancia hoy en da de la aplicacion a la
criptografa siguiente:
Aplicacion (El sistema RSA de Criptografa)
Este sistema criptograco, que fue introducido en 1978 por R.L. Rivest, A. Shamir y L. Adleman, es
un sistema de clave p ublica-clave privada y de rma digital, que se basa en el teorema de Euler para
el caso de n = j producto de dos primos distintos. En ese caso, ,(n) = ,(j ) = (j 1)( 1)
y el Teorema arma:
o n = o
(1)(g1)
1 (mod n).
La aplicacion va a ser descrita en forma muy resumida aqu, y no va a contemplar los aspectos
de implementacion sino simplemente tener en cuenta los aspectos teoricos matematicos. Para mas
informacion se recomienda buscar en Internet.
Cual es el objetivo de la criptografa ? Mandar mensajes en forma secreta y segura... Codicar
informacion (un mensaje) de manera que solo el receptor al cual va dirigido el mensaje lo pueda
decodicar (entender) y ninguna otra persona que llegue a interceptar el mensaje lo pueda entender.
Convenimos que un mensaje es un n umero o , por ejemplo simplement asignandole a cada letra del
alfabeto un valor numerico y yuxtaponiendo esos valores. Tambien podemos convenir en que ese
n umero o es menor o igual que cierto n umero n, recortando el mensaje o original en bloquecitos
si hace falta.
Que se entiende por clave p ublica-clave privada ? Una persona, Bob, va a poseer una clave
privada, conocida solamente por ella, y va a hacer p ublica la clave p ublica asociada a su clave
privada. Tanto la clave p ublica como la privada sirven para codicar o decodicar mensajes, pero
una sola de ellas no puede hacer las dos cosas a la vez. Si Bob mantiene secreta su clave privada
y le distribuye al resto del mundo su clave p ublica, el sistema RSA sirve para lo siguiente:
Cualquier personal del resto del mundo, por ejemplo Alice, le puede mandar un mensaje
encriptado a Bob usando la clave p ublica. Bob es el unico que puede decodicar el mensaje,
usando su clave privada. Ninguna otra persona del resto del mundo puede decodicar ese
mensaje.
Bob le puede mandar al resto del mundo un mensaje encriptado usando su clave privada.
Cualquiera del resto del mundo, al usar la clave p ublica de Bob, puede decodicar y luego
entender ese mensaje, y por lo tanto, como el mensaje tiene sentido, tiene garanta que el
emisor (el rmante) del mensaje fue realmente Bob.
Como funciona ?
Clave privada de Bob: (n, c) , clave p ublica de Bob: (n, d) , que satisfacen
n = j es el producto de dos primos distintos j y grandes, solo conocidos por Bob.
c coprimo con (j 1)( 1) , elegido por Bob.
d , calculado por Bob mediante el algoritmo de Euclides, cumple la condicion
d c + t (j 1)( 1) = 1
(existen d y t en esas condiciones pues c (j 1)( 1) ).
59
Dado que o
(1)(g1)
1 (mod n) , esta eleccion de c y d implica que
o
Jc
o
Jc
o
| (1)(g1)
o
1
o (mod n)
(modulo un peque no detalle para vericar...)
Mecanismo: Dado un mensaje o , 0 o < n, C(o) denotara el mensaje encriptado.
Caso 1 : Alice le manda un mensaje encriptado a Bob:
C(o) o
J
(mod n) con 0 C(o) < n.
Para decodicarlo, Bob aplica la aplicacion inversa que consiste en elevar a la c y tomar resto
modulo n. Se tiene
C(o)
c
(o
J
)
c
o
Jc
o (mod n),
luego el resto modulo n de C(o)
c
coincide con el mensaje o .
Caso 2 : Bob le quiere mandar un mensaje rmado por el al resto del mundo:
C(o) o
c
(mod n) con 0 C(o) < n.
Para decodicarlo, el resto del mundo aplica la aplicacion inversa que consiste en elevar a la d
y tomar resto modulo n. Se tiene
C(o)
J
(o
c
)
J
o
Jc
o (mod n),
luego el resto modulo n de C(o)
J
coincide con o .
60