DIVISIBILIDAD

Lic. Walter Otoniel Campos Granados

1. DIVISIBILIDAD
1.1. Lema de la Division
Los siguientes resultados nos ayudaran a establecer el teorema principal
de esta seccion, sus pruebas son sencillas y las omitiremos.
Teorema 1.1 Si x es cualquier n umero real distinto de uno, entonces
n1

i=0
x
i
= 1 + x + x
2
+ . . . + x
n1
=
x
n
1
x 1
Corolorario 1.1 Si m y n son enteros positivos y m > 1, entonces m
n
n
Teorema 1.2 (Teorema de Representacion de Bases) Sea k cualquier
entero mayor que uno. Entonces, para cada entero positivo n, existe una
representacion
n = a
0
k
s
+ a
1
k
s1
+ . . . + a
s
donde a
0
,= 0, y cada a
i
es no negativo y menor que k. Ademas, esta
representacion es unica; llamada la representacion de n en la base k.
Demostracion:
Sea P
k
(n) el n umero de representaciones de n en la base k. Se debe probar
que P
k
(n) siempre es igual a 1.
Notese que algunos de los a
i
en una representacion particular pueden ser
cero. Sin afectar dicha representacion, se pueden excluir dichos terminos.
As supogase que
n = a
0
k
s
+ a
1
k
s1
+ . . . + a
st
k
t
,
1
Lic. Walter Otoniel 2
donde ahora ni a
0
ni a
st
son iguales a cero. Entonces
n 1 = a
0
k
s
+ a
1
k
s1
+ . . . + a
st
k
t
1
= a
0
k
s
+ a
1
k
s1
+ . . . + (a
st
1)k
t
+ k
t
1
= a
0
k
s
+ a
1
k
s1
+ . . . + (a
st
1)k
t
+
t1

i=0
(k 1)k
i
1
en el ultimo renglon se ha utilizado el Teorema 1.1 con x = k. De aqu se
deduce que para cada representacion de n en la base k, se puede encontrar
una representacion para n 1. As
P
k
(n) P
k
(n 1)
donde la ultima desigualdad es cierta a un si n no tiene representacion ya que
P
k
(n) = 0 P
k
(n 1) en dicho caso. Si n tiene otra representacion en la
base k, por el mismo proceso se establecera otra representacion para n 1.
De manera que
P
k
(n + 2) P
k
(n + 1) P
k
(n),
P
k
(n + 3) P
k
(n + 2) P
k
(n + 1) P
k
(n),
y, de manera general, si m n + 4,
P
k
(m) P
k
(m 1) P
k
(m 2) . . . P
k
(n + 1) P
k
(n)
por ser k
n
> n y por tener k
n
al menos una representacion (cual?), se tiene
que
1 P
k
(k
n
) P
k
(n) P
k
(1) = 1
Una vez una base k > 0 ha sido escogida, se puede representar cualquier
entero positivo n unicamente como sumas de potencias de k:
n = a
0
k
s
+ a
1
k
s1
+ . . . + a
s
donde los a
0
, a
1
, . . . , a
s
son enteros no negativos menores que k. Esta repre-
sentacion es usualmente denotada por el smbolo a
0
a
1
. . . a
s
.
Es com un que para bases menores o iguales que diez, los a
i
son escogidos de
los smbolos 0, 1, 2,..., 9 con su signicado usual, sin embargo, si k es mayor
que diez, se deben inventar smbolos de manera que se tengan k smbolos
diferentes.
Lic. Walter Otoniel 3
Ejemplo 1.1 En base dos (23)
10
(10111)
2
; la base 16 es bastante com un,
aqui se acostumbra tomar A = 10, B = 11, C = 12, D = 13, E = 14,
F = 15, en esta base (543)
10
(21F)
16
, ya que 543 = 116
2
+216
1
+1516
0
.
Las bases 2, 8, 16 son muy importantes en Ciencia Computacional.
Nota: Para obtener los coecientes en la expansion, basta con hacer divi-
siones sucesivas del n umero en base diez, entre la base k, luego se toma el
ultimo cociente y todos los residuos partiendo del ultimo hasta el primero,
en ese orden.
Denicion: Dados dos n umeros enteros a, b, con a ,= 0, se dice que a divide
a b (lo cual se denota por a[b) si existe un entero x tal que b = ax.
Si a no divide a b se escribe a ,[ b.
Si a divide a b, tambien se dice que b es m ultiplode a, que a es divisor b, que
a es un factor de b o que b es divisible por a.
Notese que seg un la anterior denicion 2[4, 5[30, 3[24, 11[242, 7 ,[18, 4 ,[27.
Algunas Propiedades Basicas:
1. Si a[b entonces a[bc para todo entero c.
2. Si a[b y b[c entonces a[c.
3. Si a[b y a[c entonces a[bx + cy, para todo par de enteros x, y.
4. Si a[b y b[a entonces a = b
5. Si a[b, a > 0, b > 0, entonces a b
No es difcil probar las propiedades anteriores, basta tener en cuenta la deni-
cion de divisibilidad.
1. Si a[b existe un entero x tal que
b = ax
bc = (ax)c
bc = a(xc)
de donde se deduce que a[bc.
2. Si a[b y b[c entonces existen enteros x, y tales que: b = ax, c = by, de
Lic. Walter Otoniel 4
donde
c = by
= (ax)y
= a(xy)
as a[c.
3. Si a[b y a[c entonces por 1. a[bx, a[cy, de manera que existen enteros u, v
tales que:
bx = au
cy = av
sumando miembro a miembro ambas igualdades se tiene:
bx + cy = au + av
bx + cy = a(u + v)
de donde es claro que a[bx + cy.
Observacion: De la propiedad anterior es claro que a[b c, es decir si un
entero divide a otros dos, divide tambien a su suma y diferencia.
4. Si a[b y b[a, entonces existen enteros x, y tales que: b = ax, a = by, de
donde
b = (by)x = b(yx)
asi yx = 1, de manera que necesariamente x = y = 1 o x = y = 1, por lo
tanto a = b.
5. Si a[b, entonces b = ax para alg un entero x. ya que a > 0 y b > 0, x debe
ser positivo; es decir, x 1, de donde a b.
Notese que si se divide 18 entre 5 se obtiene un cociente 3 y un residuo 3,
as: 18 = 5 3 + 3, este resultado se formaliza en el siguiente teorema.
Teorema 1.3 [Lema de la Division de Euclides] : Dados dos enteros a y b,
con b > 0, existen enteros q, r tales que a = bq + r, con 0 r < b.
Demostracion: Considere el conjunto S = a + bx : x Z.
si a 0, entonces a +b 0 y a +b S; si a < 0, entonces a +b(a) 0
y es un elemento de S, as en ambos casos S contiene enteros no negativos,
por lo tanto por el principio de buena oredenacion, contiene un menor entero
no negativo, digamos r. Supongase que r sucede en S cuando x = q, asi se
tiene que
0 r = a bq
Lic. Walter Otoniel 5
si r b, entonces a bq b, de donde se tiene que
0 a + b(q 1) < a bq.
pero lo anterior es imposible ya que a bq es el menor entero no negativo de
S. De aqu b > r y existen enteros q y r que establece el teorema.
Para probar la unicidad, se asume que existen enteros q, q
1
, r, r
1
, tales que
a = bq + r, 0 r < b
a = bq
1
+ r
1
, 0 r
1
< b
Sin perdida de generalidad se puede asumir que q < q
1
. Entonces
0 r
1
= a bq
1
a b(q + 1) = r b < 0,
lo cual constituye una contradiccion. Similarmente si se hubiese supuesto
q
1
< q. De aqu q = q
1
, y
r
1
= a bq
1
= a bq = r.
Notese que el Lema de la division de Euclides no es mas que el establec-
imiento riguroso del hecho elemental de que la division de un entero por
otro, produce un cociente entero y un entero no negativo llamado residuo, el
cual es menor que el divisor.
Ejercicios 1.1
1. Pruebe que cada entero distinto de cero puede ser representado de
manera unica en la forma
n =
s

i=0
c
i
3
i
,
donde c
s
,= 0, y cada c
i
es igual a -1, 0, o 1.
2. Pruebe que si
n = a
0
k
s
+ a
1
k
s1
+ . . . + a
s
es una representacion de n en la base k, entonces 0 < n k
s+1
1.
Lic. Walter Otoniel 6
3. Pruebe usando induccion matematica que si a[b
1
, a[b
2
, . . . a[b
n
, entonces
a[b
1
x
1
+b
2
x
2
+. . .+b
n
x
n
para todo conjunto x
1
, x
2
, . . . , x
n
de n umeros
enteros.
4. Si a ,= 0, muestre que el conjunto d : d[a es nito.
5. Supongase a, b, n Z y [a b[ < [n[. Pruebe que es imposible que n
divida a ambos a y b, a ,= b.
6. Sean a, b, c Z y supongase c ,= 0. Muestre que ac[bc implica a[b.
7. Pruebe que la relacion [ es una relacion de orden parcial sobre Z.
8. Sean n un natural, y a, b enteros cualesquiera, entonces:
a) a b[a
n
b
n
b) si n es impar, se tiene que a + b[a
n
+ b
n
c) si d es un divisor de n, entonces a
d
b
d
[a
n
b
n
1.2. El Maximo Com un Divisor
Denicion: Si a y b son enteros, ambos distintos de cero, entonces el
maximo com un divisor (mcd) de a y b es un entero d que cumple:
(i) d > 0,
(ii) d es un com un divisor de a y b, y
(iii) cada entero m que es un divisor de a y b, tambien es un divisor de d.
El maximo com un divisor de a y b es representado por muchos autores como
mcm(a, b) o simplemente (a, b), que es la notacion que aqu se usara.
El siguiente teorema prueba la existencia y unicidad de (a, b), ademas, pro-
porciona un algoritmo para encontrarlo, antes de enunciarlo y probarlo se da
el siguiente ejemplo que describe el algoritmo.
Ejemplo 1.2 Encontrar el (108, 46).
Lic. Walter Otoniel 7
No es difcil establecer que (a, b) = 2. Lo que se hara aqu es que se aplicara el
lema de la division repetidamente, de tal manera que el ultimo residuo no
nulo cocidira con (a, b).
108 = 42 2 + 16
46 = 16 2 + 14
16 = 14 1 + 2
14 = 2 7 + 0
Efectivamente el ultimo residuo distinto de cero es 2. Esto no es una mera
cocidencia y se formaliza en el siguiente
Teorema 1.4 Si a y b Son enteros, ambos distintos de cero, entonces (a, b)
existe y es unico.
Demostracion:
Notese que (a, b) no es afectado por los signos de a y b. As sin perdida de
generalidad se puede suponer que a b > 0.
Por el Teorema 1.3, existen enteros q
1
, r
1
(0 r
1
< b) tales que
a = bq
1
+ r
1
.
Si r
1
> 0, existen enteros q
2
, r
2
(0 < r
2
r
1
) tales que
b = r
1
q
2
+ r
2
Si r
2
> 0, existen enteros q
3
, r
3
(0 < r
3
r
2
) tales que
r
1
= r
2
q
3
+ r
3
Este proceso se puede continuar mientras r
i
,= 0. Ya que
b > r
1
> r
2
> r
3
> . . . > 0,
Usando induccion matematica se ve que 0 r
i
b i. Por lo tanto, en a lo
sumo b pasos se obtendra un r
n
igual a cero.
De manera que en alg un momento se tendra
r
n2
= r
n1
q
n
+ 0
es decir r
n
= 0. Se probara que r
n1
= (a, b), para esto basta recorrer la
secuencia de ecuaciones de abajo hacia arriba e inversamente, de arriba hacia
Lic. Walter Otoniel 8
abajo.
En efecto, de la ultima ecuacion se tiene que r
n1
[r
n2
, r
n1
[r
n3
,. . . , r
n1
[r
1
,
r
n1
[b, de donde r
n1
[a. Finalmente si m es un divisor com un de a y b lo es
tambien de r
1
, de r
2
, y as sucesivamente de r
n1
. (aqu es claro que se ha
usado induccion matematica). De aqu r
n1
satisface todas las condiciones
de la denicion. Este metodo para calcular el mcd, es llamado el Algoritmo
de Euclides.
Corolorario 1.2 (Propiedad Lineal del mcd) : Si d = (a, b), entonces
existen enteros u, v tales que
au + bv = d
Demostracion: Tomando las n ecuaciones usadas en la prueba del Teorema
1.4 y usando el principio de induccion matematica, se probara en primer
lugar que existen enteros u
i
, v
i
tales que
av
i
+ bv
i
= r
i
(1)
para i = 1, 2, . . . , n 1.
Cuando i = 1, basta tomar u
1
= 1, v
1
= q
1
. Asumiendo que las soluciones
enteras de (1) han sido encontradas para todo i menor o igual que k, (k <
n 1). se sabe que
r
k1
= r
k
q
k+1
+ r
k+1
; (2)
luego por hipotesis inductiva,
(au
k1
+ bv
k1
) (au
k
+ bv
k
)q
k+1
= r
k+1
. (3)
Se puede escribir la ecuacion (3) en la forma
(u
k1
u
k
q
k+1
)a + (v
k1
v
k
q
k+1
)b = r
k+1
. (4)
De aqu, u
k+1
= u
k1
u
k
q
k+1
y v
k+1
= v
k1
v
k
q
k+1
son soluciones de la
ecuacion (1) cuando i = k + 1.
Queda pues la formula (1) establecida para i = 1, 2, . . . , n 1. En particular
si i = n 1 en la ecuacion (1), se obtiene la relacion
au
n1
+ bv
n1
= r
n1
= (a, b)
Lic. Walter Otoniel 9
Demostracion alternativa:
Considerese el conjunto A = ax + by : x, y Z
Notese que Acontiene n umeros positivos y negativos (tambien al cero, toman-
do x = y = 0). Por el principio de buena ordenacion se sabe que existe un
menor elemento positivo d en A.
Sea d = au + bv, se probara que d es un divisor com un de a y b. Si d ,[a, de
acuerdo con el Teorema 1.3 existen enteros q y r tales que
a = dq + r, 0 < r < d
pero entonces se tiene que
r = a dq
= a (au + bv)q
= a auq bvq
= a(1 uq) + b(vq)
de donde r esta en A, y 0 < r < d, lo cual es una contradiccion. de manera
similar si se supone que d ,[b, por lo tanto d es un com un divisor de a y b.
Ahora bien, si m > 0 y m[a y m[b, por las propiedades de divisibilidad
m[au + bv = d, as que m d. De manera que d = (a, b).
De lo anterior es claro que para que d sea el mcd de a y b, es necesario y
suciente que d se pueda escribir como combinacion lineal de a y b.
Ejemplo 1.3 Dado que 2 = (108, 46), encontrar los u, v tales que 2 = 108u+
46v
Lo que se hace es tomar las ecuaciones obtenidas en el Algoritmo de Euclides
e ir despejando en retroceso, as:
2 = 16 14 1
= 16 (46 16 2)
= 16 46 2 + 16 2
= 3 16 46
= 3(108 46 2) 46
= 3 108 6 46 46
= 3 108 7 46
Teorema 1.5 Sean a, b, m n umeros enteros, entonces (ma, mb) = [m[(a, b).
Lic. Walter Otoniel 10
Demostracion:
(ma, mb) =
Denicion: Si (a, b) = 1, se dice que los enteros a y b son primos relativos.
De los resultados anteriores es facil darse cuenta que si (a, b) = 1, entonces
existen entros u, v tales que 1 = au + bv. Este resultado se conoce como
Relacion de Bezout.
Si en conjunto de n enteros, se tiene que cada par de ellos son primos rela-
tivos entre s, se dice que los n umeros son primos relativos dos a dos.
Teorema 1.6 Sean a, b, c n umeros enteros, si c[ab y (b, c) = 1 entonces c[a.
Demostracion: Dado que (b, c) = 1, existen enteros u, v tales que
bu + cv = 1
abu + acv = a
de donde por hipotesis y propiedades de divisibilidad se tiene que c[abu+acv
o lo que es lo mismo c[a.
1.3. El Mnimo Com un M uliplo
Denicion: Sean a, b Z, ab ,= 0. El mnimo com un m ultiplo (mcm)
de a y b, denotado por a, b), es un entero m denido por
(i) m > 0,
(ii) a[m y b[m,
(iii) si a[n y b[n, entonces m[n.
No es difcil probar que el a, b) siempre existe, para cualquier par de
enteros distintos de cero a y b, y que es efectivamente el menor entero positivo
del conjunto
M = n : n Z
+
, a[n, b[n
Primero notese que M no es vaco ya que [ab[ M, as se m el menor
entero positivo de M. Es claro que m satisface las primeras dos propiedades.
Lic. Walter Otoniel 11
Supongase ahora que a[n y b[n, para n Z. se pueden encontrar enteros
q y r tales que n = mq + r, 0 r < m. Ya que a[n, a[m, se tiene que a[r;
similarmente, b[r, de manera que r M, pero entonces r = 0. Por lo tanto
m[n, y tiene la tercera propiedad, a que m = a, b).
El siguiente Teorema establece una relacion entre el maximo com un divisor
y el mnimo com un m ultiplo de dos enteros distintos de cero.
Teorema 1.7 Sean a, b enteros tales que ab ,= 0. Entonces (a, b) a, b) = [ab[
Demostracion: Sean d = (a, b), m = a, b). La prueba consiste en establecer
que dm[ab y ab[dm.
Ya que d[a, d[ab, ademas, es claro que m[ab (por la denicion del mcm), asi
que (ab/d), (ab/m) Z
Como d[a, db[ab, similarmente, d[b, luego ad[ab, de esto se tiene que b[(ab/d)
y a[(ab/d), as por la propiedad tres del mcm se tiene que m[(ab/d) o md[ab.
Por otro lado b[m, de donde ab[am, o (ab/m[a), de manera similar, a[m, de
donde ab[bm, o (ab/m)[b, luego por la propiedad tres del mcd (ab/m)[d o
ab[dm, por lo tanto dm = ab = [ab[.
Ejercicios 1.2
1. Pruebe que si a[c, b[c, y (a, b) = 1, entonces ab[c
2. Pruebe que si (a, b) = 1 y (a, c) = 1, entonces (a, bc) = 1
3. Probar que ac, ) = [c[ a, b)
4. Muestre que si (a, b) = (a, c) y a, b) = a, c), entonces b = c
5. Sean a, b Z, con ab ,= 0. Sea D
1
= d : d[a y D
2
= d : d[b,
muestre que D
1
D
2
,= , y que (a, b) = maxD
1
D
2

6. Demuestre que (a, bc) es divisible entre (a, b).

7. Si (a, c) = 1, entonces (a, bc) = (a, b)
8. A los terminos de la siguiente sucesion recursiva dad por u
n
= u
n1
+
u
n2
, con u
1
= 1, u
2
= 1 se les llama n umeros de Fibinacci. Pruebe que
si n es divisible por m, entonces u
n
es divisible por u
m
. Que puede
decirse del recproco?
9. Pruebe que (u
m
, u
n
) = u
(m,n)
Lic. Walter Otoniel 12
1.4. N umeros Primos
Denicion: Se dice que un entero positivo p > 1 es un n umero primo si
unicamente admite dos divisores positivos: 1 y p. Un entero n > 1 que no es
primo es llamado compuesto.
Lema 1.1 Sea n > 1 un n umero entero, entonces n es un producto de
n umeros primos.
Demostracion: Se hara la prueba por contradiccion. Supongase pues que
existen enteros mayores que 1 que no son producto de primos, por el principio
de buena ordenacion, existe un menor entero positivo r que satisface tal
condicion. Notese que r no es primo, as pues r es compuesto, de manera que
existen enteros x, y tales que r = xy, donde por propiedades de divisibilidad
se tiene que x < r, y < r. Pero entonces x y y pueden ser expresados como
producto de primos,
x = q
1
q
2
. . . q
i
y = p
1
p
2
. . . p
j
donde q
1
, q
2
ldots, q
i
, p
1
, p
2
, . . . , p
j
son n umeros primos (no necesariamente
distintos), as pues r = q
1
q
2
. . . q
i
p
1
p
2
. . . p
j
lo cual contradice la eleccion de
r.
No es difcil darse cuenta que si a Z y p es primo, entonces
(a, p) =
_
p si p[a
1 si p ,[a
notese ademas que si p y q son primos mayores que 1 tales que p[q, entonces
p = q.
Lema 1.2 Si p es primo y p[ab, entonces p[a o p[b.
Demostracion: Supongase que p ,[a, entonces (a, p) = 1 por el Teorema 1.6
se tiene que p[b.
Observacion: El resultado anterior se puede generalizar al caso en que el
primo p divida al producto de m factores, es decir si p[a
1
a
2
. . . a
m
, entonces
p[a
j
, para alg un j = 1, 2, . . . n (hacer la prueba por induccion)
Teorema 1.8 (Teorema Fundamental de la Aritmetica) : Todo entero
n > 1 se puede expresar como producto de factores primos de manera unica,
salvo el orden de dichos factores.
Lic. Walter Otoniel 13
Demostracion: Se hara la prueba por contradiccion. As, supongase que
existen enteros mayores que 1 que admiten dos representaciones como pro-
ducto de factores primos, por el principio de buena ordenacion, existe un
menor entero f que cumple esta condicion. De donde
f = p
1
p
2
. . . p
k
= q
1
q
2
. . . q
r
donde los p
1
p
2
. . . p
k
, q
1
q
2
. . . q
r
son primos distintos de f. Ahora bien, es claro
que p
1
[m o lo que es lo mismo p
1
[q
1
q
2
. . . q
r
, de donde por el Lema 1.2 se tiene
que p
1
[q
i
, para alg un i = 1, 2, . . . r. Sin perdida de generalidad, se puede
suponer que p
1
[q
1
(obteniendo que p
1
= q
1
), pero entonces se tendra que
m
p
1
= p
2
. . . p
k
= q
2
. . . q
r
es decir el entero
m
p
1
< m admite dos representaciones como producto de
factores primos, contradiciendo la eleccion de m.
Cuando se aplica el teorema fundamental de la aritmetica a un entero n > 1
este se escribe como
n = p
m
1
1
p
m
2
2
. . . p
m
j
j
,
donde los p
i
, i = 1, 2, . . . , j son primos distintos, y m
i
indica el n umero de
veces que el primo p
i
aparece en la factorizacion. La anterior representacion
se conoce como forma canonica del entero n.
Puede surgir la inquietud sobre si el conjunto de n umeros primos es ni-
to o innito, Eucldes hace mucho tiempo tamben se hizo esta pregunta y
logro demostrar el siguiente resultado
Teorema 1.9 (Eucldes) : Existen innitos n umeros primos.
Demostracion: Se hara la prueba por contradiccion. As, supongase que el
conjunto E = p
1
, p
2
, . . . , p
k
constituye el conjunto de todos los primos. Se
construye el siguiente n umero m = p
1
p
2
. . . p
k
+ 1, notese que no es primo,
entonces es compuesto, as existe un primo p tal que p[m, p / E, ya que de
lo contrario se tendra que p[p
1
p
2
. . . p
k
y como p[n, se tendra tambien que
p[1. En ambos casos se llega a una contradiccion.
Ejemplo 1.4
74 = 2 37, 108 = 2
2
3
3
, 900 = 2
2
3
2
5
2
.
Lic. Walter Otoniel 14
Ejemplo 1.5
Aunque el conjunto de n umeros primos es innito, surge una cuestion bas-
tante interesante, esta consiste en que dado cualquier entero k > 0 se pueden
encontrar k enteros compuestos consecutivos, para probar esto, basta obser-
var que el conjunto C = (k +1)! +2, (k +1)! +3, (k +1)! +4, . . . , (k +1)! +
(k + 1) cumple tal condicion. El lector podra preguntarse si existe alguna
ley de formacion de los n umeros primos, desgraciadamente la respuesta es
no. Fermat conjeturo que F
n
= 2
2
n
+ 1 para n entero positivo es un n umero
primo, sin embargo, Euler Probo que para n = 5 se obtiene un n umero com-
puesto, F
5
= 2
2
5
+1 = 2
32
+1 = 4294967297 = 6416700417. Solo se conocen
5 primos de fermat que suceden para n = 1, 2, 3, 4, 5. Encuentralos!.
Ejercicios 1.3
1. Supongase que a =
k

i=1
p
m
i
i
, b =
s

i=1
p
t
i
i
estan representados en su forma
canonica. Pruebe que (a, b) = p
n
1
1
p
n
2
2
. . . p
nr
r
, donde n
i
= minm
i
, t
i

2. Sean a, b como en el ejercicio anterior. Pruebe que a, b) = p

c
1
1
p
c
2
2
. . . p
c
j
j
,
donde c
i
= maxm
i
, t
i
, j = maxk, s
3. Encontrar todas las parejas [a, b] de n umeros enteros positivos tales que
ab 3a 2b = 6.
4. Cuantos n umeros de tres dgitos xyz son tales que x+3y+z es m ultilpo
de 3 (x ,= 0)?.
5. Pruebe que si a
n
1 es primo, entonces a = 2 y n es primo.
6. Muestre que para nig un entero positivo n, 2
n
+ 1 es un cubo.
7. Probar que existen innitos primos de la forma 4k + 1; de la forma
4k + 3.
8. Sea a
n
= 11 . . . 1
. .
n veces
. Probar que si a
n
es primo entonces n es primo.
9. Un entero T se dice tico si la suma de sus dgitos es m ultiplo de 2007.
Pruebe que existe un entero T, tal que T, 2T, 3T, . . . 2007T son ticos.
Lic. Walter Otoniel 15
2. LAS CONGRUENCIAS EN Z
Al lector le parecera que en esta seccion se sigue hablando de divisibili-
dad, y efectivamente as es. El concepto de congruencia no es mas que una
forma muy elegante de tratar el concepto de divisibilidad, aunque con muchas
ventajas, en este sentido, muchos resultados sobre divisibilidad se obtienen
de manera muy simple ocupando la notacion de congruencia.
Denicion: Sean a, b, m Z, con m ,= 0. se dice que a es congruente con b
modulo m, lo cual se denota a b(m), si m[a b.
Ejemplo 2.1
8 2(3), 15 1(2), 17 2(3)
Como es de esperar si m ,[a b, se dice que a , b(m).
Observacion: Notese que m[ab m[ab, por lo tanto basta considerar
a m > 0, as que de aqu en adelante solo se considerara m positivo.
Teorema 2.1 Supongase que a = q
1
m+r
1
, b = q
2
m+r
2
. a b(m) r
1
=
r
2
.
Demostracion: Notese que si
a = q
1
m + r
1
, donde 0 r
1
< m,
b = q
2
m + r
2
, donde 0 r
2
< m,
entonces a b = m(q
1
q
2
) + (r
1
r
2
), pero como m[a b, se debe tener
que m[r
1
r
2
, donde [r
1
r
2
[ < m, as que por propiedades de divisibilidad,
debe ser r
1
r
2
= 0, es decir r
1
= r
2
.
Por el otro lado (recprocamente), si a = q
1
m + r, b = q
2
m + r se tiene
que a b = m(q
2
q
1
), de donde m[a b, de manera que a b(m). Es ya
sabido que al dividir cualquier n umero entero por m los posibles restos son
0, 1, 2, 3, . . . , m1, as de lo anterior se deduce facilmente que cualquier entero
es congruente modulo m con uno y solo uno de los enteros 0, 1, 2, 3, . . . , m1
Lo anterior nos indica algo muy importante, esto es, que al dividir por m los
enteros quedan divididos en m clases:
Lic. Walter Otoniel 16
. . . , 3m, 2m, m, 0, m, 2m, 3m, . . . 0(m),
. . . , 3m + 1, 2m + 1, m + 1, m + 1, 2m + 1, 3m + 1, . . . 1(m),
. . . , 3m + 2, 2m + 2, m + 2, m + 2, 2m + 2, 3m + 2, . . . 2(m),
.
.
.
. . . , 3m1, 2m1, m1, 1, m1, 2m1, 3m1, . . . m1(m).
Observacion: La denicion de congruencia en algunos libros se enuncia
diciendo que a b(m) si y solo s existe un k Z tal que a b = mk.
Notese que esta es equivalente a la que se ha dado aqui.
El lector puede darse cuenta que de alguna manera las propiedades que se
enuncian a continuacion son analogas a las que se dieron para el caso de
divisibilidad.
Propiedades
1. a a(m),
2. a b(m), entonces b a(m),
3. a b(m) y c d(m), entonces a c b d(m),
4. a b(m) y c d(m), entonces ac bd(m)
5. Si a b(m) y d[m, con d > 0, entonces a b(d)
Las demostraciones de cada una de estas propiedades se deducen facilmente
de la denicion de congruencia. 1. Notese que m[a a = 0
2. Si m[a b, entonces m[(a b)(1), as que m[b a, de donde b a(m)
3. Si m[a b y m[c d entonces m[[(a b) (c d)] de lo cual se deduce
que m[[(a c) (b d)]
4. Se tiene que m[a b y m[c d, de aqu m[(a b)c y m[(c d)b, entonces
m[[(a b)c + (c d)b] de lo cual se deduce que m[ac bd, por lo tanto
ac bd(m).
5. Es claro que si m[a b y d[m entonces d[a b
Teorema 2.2 Si f es un polinomio con coecientes enteros, y si a b(m),
entonces f(a) f(b)(m)
Lic. Walter Otoniel 17
Demostracion: Sea f(x) = c
n
x
n
+ c
n1
x
n1
+ . . . + c
1
x + c
0
un polinomio
arbitrario con coecientes enteros.
f(a) = c
n
a
n
+c
n1
a
n1
+. . . +c
1
a+c
0
, f(b) = c
n
b
n
+c
n1
b
n1
+. . . +c
1
b+c
0
.
por las propiedades anteriores, se tiene que: c
i
a
i
c
i
b
i
, para i = 1, 2, . . . , n,
as que
c
n
a
n
+ c
n1
a
n1
+ . . . + c
1
a + c
0
c
n
b
n
+ c
n1
b
n1
+ . . . + c
1
b + c
0
de donde
f(a) f(b)(m)
Ejemplo 2.2
Encontrar la cifra en que termina 2
300
Pareciera ser que las congruencias se comportan como igualdades, sin em-
bargo debe tenerse mas cuidado al dividir una congruencia entre un n umero
entero a, vease el teorema siguiente.
Teorema 2.3
(a) ax ay(m) x y
_
m
(a, m)
_
.
(b) Si ax ay(m) y (a, m) = 1, entonces x y(m).
(c) ax ay(m
i
), para i = 1, 2, . . . , r si y solo s x y (m
1
, m
2
, . . . , m
r
)).
Demostracion:
(a) Si ax ay(m) entonces ax ay = mk, para alg un entero k. De esto se
tiene
a
(a, m)
(x y) =
m
(a, m)
k
ahora bien, recuerdese que
_
a
(a, m)
,
m
(a, m)
_
= 1, asi que por el Teorema 1.6
m
(a, m)
[x y, de donde x y
_
m
(a, m)
_
(b) Notese que este no es mas que un caso particular de (a), se ha escrito
aparte por su relevancia.
(c) Como x y(m
i
), se tiene que m
i
[(xy), para i = 1, 2, . . . , r, es decir xy
es un m ultiplo com un de m
1
, m
2
; . . . , m
r
por tanto m
1
, m
2
, . . . , m
r
) [(xy),
Lic. Walter Otoniel 18
lo cual implica que x y (m
1
, m
2
, . . . , m
r
)).
Por otro lado, si x y (m
1
, m
2
, . . . , m
r
)), como m
i
[ (m
1
, m
2
, . . . , m
r
)), en-
tonces x y(m
i
) por la propiedad 5.
Al conjunto 0, 1, 2, 3, . . . , m 1 de restos posibles cuando se trabaja
con congruencias modulo m se le llama sistema completo de restos modulo
m, esta cuetion se generaliza en la siguiente denicion.
Teorema 2.4 Si x y(m) entonces (x, m) = (y, m)
Demostracion: Se tiene que m[xy, es decir xy = mk, para alg un entero
k. Ahora bien (x, m)[x y (x, m)[m, asi se debe tener que (x, m)[y, de donde
(x, m)[(y, m). Por otro lado (y, m)[y, (y, m)[m, de donde (y, m)[x, asi que
(y, m)[(x, m). Por lo tanto (x, m) = (y, m).
Denicion: Si x y(m) entonces y recibe el nombre de residuo (resto)
de x modulo m. Un conjunto x
1
, x
2
, x
3
, . . . , x
m
es un sistema completo de
residuos modulo m si para todo entero y existe un unico x
j
, tal que y x
j
(m)
Es claro que existen innitos sistemas completos de residuos modulo m, sien-
do el ejemplo mas familiar 0, 1, 2, 3, . . . , m 1. Notese ademas que un
conjunto forma un sistema completo de residuos modulo m si y solamente si
no se tienen en el conjunto dos enteros que sean congruentes entre s modulo
m.
Denicion: Un sistema reducido de residuos modulo m es un conjunto
de enteros r
i
, tales que (r
i
, m) = 1, r
i
, r
j
(m), si i ,= j y tales que todo x
coprimo con m es congruente modulo m con alg un r
i
del conjunto.
De todo lo anterior se puede ver que al trabajar con congruencias modulo
m, se pueden reemplazar los enteros en las congruencias por elementos del
conjunto 0, 1, 2, . . . , m 1. Tal sustitucion frecuentemente gua a la sim-
plicacion de problemas un tanto complicados.
Ejemplo 2.3
Encontrar un entero z que satisfaga la congruencia 325z 11(3).
Ya que
325 1(3)
Lic. Walter Otoniel 19
y
11 2(3)
se debe encontrar un entero z tal que
z 2(3)
aqui es claro que dicho entero puede ser 2.
A partir del teorema anterior es claro que un sistema reducido de restos
modulo m se puede obtener a partir de un sistema completo de restos modu-
lo m, eliminando de este aquellos miembros que no son coprimos con m.
Tambien notese que todos los sistemas reducidos de restos modulo m ten-
dran el mismo n umero de miembros, esta funcion se denota por (m) y recibe
el nombre de Funcion de Euler. Al aplicar la denicion de (m) al sistema
completo de residuos 0, 1, 2, . . . , m 1, se obtiene el siguiente teorema:
Teorema 2.5 El n umero (m) es el n umero de enteros positivos menores o
iguales que m y primos relativos con m.
Teorema 2.6 Si (c, m) = 1, y r
1
, r
2
, . . . , r
n
es un sistema completo (o bien
reducido) de residuos modulo m, entonces cr
1
, cr
2
, . . . , cr
n
tambien lo es.
Demostracion: Es claro que (cr
i
, m) = 1, ademas se sigue teniendo el mismo
n umero de miembros en el conjunto. As pues basta probar que cr
i
, cr
j
(m),
si i ,= j. Pero si cr
i
cr
j
(m) el Teorema 2.3 (b) implicara que r
i
r
j
(m)
algo que no puede pasar.
Los siguientes teoremas son historicos en la teora de n umeros.
Teorema 2.7 (Euler) Si (a, m) = 1, entonces a
(m)
1(m)
Demostracion: Sea r
1
, r
2
, . . . , r
(m)
un sistema reducido de restos modulo
m, entonces ar
1
, ar
2
, . . . , ar
(m)
tambien lo es. De donde a cada ar
i
le corre-
sponde un unico r
j
tal que ar
i
r
j
(m). por lo tanto
(m)

i=1
(ar
i
)
(m)

i=1
(r
i
)(m)
a
(m)
(m)

i=1
(r
i
)
(m)

i=1
(r
i
)(m)
Lic. Walter Otoniel 20
ahora bien, notese que
_
_
(m)

i=1
(r
i
), m
_
_
= 1, as por el Teorema 2.3b
a
(m)
1(m).
Es evidente que si m es primo, entonces (m) = m1, as pues el siguiente
corolario es un resultado inmediato del teorema de Euler.
Corolorario 2.1 Si p es un primo tal que (a, p) = 1, entonces
a
p1
1(p)
El anterior corolario es conocido en el medio matematico como el peque no
teorema de Fermat.
Al multiplicar la congruencia a
p1
1(p) por a, se tiene que a
p
a(p), la
cual es cierta para todos los valores de a, a un si p[a.
A partir del teorema de Euler se deduce el siguiente corolario.
Corolorario 2.2 Si (a, m) = 1, entonces ax b(m) tiene una solucion x
1
.
Ademas todas las soluciones estaran dadas por x = x
1
+ km, k entero.
Demostracion: Basta tomar x
1
= a
(m)1
b. Por otro lado si x
1
satisface
la congruencia, entonces todos los enteros de la forma x
1
+ km son tambien
soluciones, ya que
a(x
1
+ km) = ax
1
+ akm ax
1
b(m)
Teorema 2.8 (Wilson) Si p es un primo, entonces (p 1)! 1(p).
Demostracion: Si p = 2 o p = 3 el resultado es evidente.
supongase pues que p 5. La clave de la desmostracion es la siguiente: se
consideran todos los enteros cuyo producto es (p 1)! y se trata de parearlos
de tal manera que el producto de cada par sea congruente con 1 modulo p.
Dado un entero j que satisfaga 1 j p 1, entonces (j, p) = 1, y por el
Corolario 2.2 existe un unico entero i tal que ji 1(p) con 1 i p 1.
As ociese a cada j el correspondiente entero i. Ahora bien, dado que ij
ji 1(p), se veque j es el entero asociado con i. 1 se asocia con si mismo, al
igual que p 1.Ahora considerese 2 j p 2. Para estos j se tiene que
(j 1, p) = (j + 1, p) = 1, por lo que j
2
1 = (j 1)(j + 1) , 0(p). Por lo
Lic. Walter Otoniel 21
tanto cada uno de estos j se asocia con un i ,= j, 2 i p 2 y el asociado
de i es el propio j. As que los enteros 2, 3, . . . , p 2 pueden parearse, j y su
asociado i con ji 1(p). Multiplicando todos estos pares se obtiene
2 3 4 . . . (p 2) 1(p)
y ya que
1 (p 1) 1(p)
se tiene la conclusion del teorema de Wilson
1 2 3 . . . (p 1) 1(p)
. A partir de los teoremas de Wilson y Fermat se obtiene el siguiente resul-
tado:
Teorema 2.9 Si p es primo x
2
1(p) tiene soluciones si y solo s p = 2
o bien p 1(4).
Demostracion: Si p = 2 basta tomar x = 1.
Ahora bien si p es un primo distinto de 2, el teorema de Wilson puede es-
cribirse en la forma
_
1 2 . . . j . . .
p 1
2
__
p + 1
2
. . . (p j) . . . (p 2)(p 1)
_

1(p).
El producto del primer miembro se ha dividido en dos partes, cada una con
el mismo n umero de actores. Pareando los j de la primera mitad con los pj
de la segunda mitad, puede escribirse la congruencia en la forma
(p1)/2

j=1
j(p j) 1(p).
Pero j(p j) j
2
(p) as pues, si p 1(4),
(p1)/2

j=1
j(p j)
(p1)/2

j=1
(j
2
) (1)
(p1)/2
_
_
(p1)/2

j=1
j
_
_
2

_
_
(p1)/2

j=1
j
_
_
2
(p)
de donde se obtiene la solucion

(p1)/2
j=1
j, de x
2
1(p).
Ahora si p ,= 2 y p , 1(4), entonces p 3(4). En este caso, si para alg un en-
tero x, x
2
1(p), entonces se tiene que x
p1
(x
2
)
(p1)/2
(1)
(p1)/2

Lic. Walter Otoniel 22

1(p), ya que (p 1)/2 1(p). Evidentemente p ,[ x y as por el Teorema
2.1, se tiene que x
p1
1(p). esta contradiccion demuestra que x
2
1(p)
no tiene solucion en este caso.
Ejercicios 2.1
1. Hacer una lista de todos los entero x en el intervalo [1, 100] que satisfa-
gan x 7(17).
2. Mostrar un sistema completo de restos modulo 17 compuesto entera-
mente por m ultiplos de tres.
3. Encuentre enteros x tales que.
a) 5x 4(3).
b) 7x 6(5).
c) 9x 8(7).
4. Existe alg un cuadrado perfecto n
2
tal que
n
2
1(p)
para p = 3, p = 5, p = 7, p = 11, p = 13, p = 17, p = 19?. puede
caracterizar los primos p para los cuales la congruencia anterior tenga
solucion?.
5. Encuentre una congruencia que sea equivalente al par de congruencias
x 1(4), x 2(4).
6. Probar que si p es un primo y a
2
b
2
(p), entonces p[(a + b) o bien
p[(a b).
7. Probar que cualquier n umero que sea un cuadrado debe terminar en
alg un dgito de los siguientes: 0, 1, 4, 56, 9.
8. Encuentre un sistema reducido de restos modulo 24 y modulo 30.
Lic. Walter Otoniel 23
3. RESOLUCI

ON DE CONGRUENCIAS
3.1. Congruencias Lineales
Un problema muy simple sobre congruencias puede ser planteado como
sigue: si a, b, m Z, se puede encontrar un entero x tal que
ax b(m) (5)
Notese que si x satisface esta congruencia, entonces todos los enteros de
la forma x + km tambien son soluciones, ya que
a(x + km) = ax + akm ax b(m)
Ejemplo 3.1
Si a = 5, b = 3 y m = 8, se tiene que 7 es solucion de la congruencia
5x 3(8)
Realmente, cada uno de los n umeros . . . , 17, 9, 1, 7, 15, 23, 31, . . . es
una solucion.
Observese pues que si se encuentra una solucion de la congruencia (5) se
pueden entonces construir innitas soluciones a partir de esta. Sin enbargo,
todas las soluciones as construidas son congruentes a x modulo m, esto da
lugar a la siguiente interrrogante: Cuantas soluciones no conguentes entre
s existen de la congruencia (5)?.
Para responder esta pregunta se hara uso de los conocimientos sobre ecua-
ciones Diofantinas Lineales.
En concreto, intentar resolver la congruencia (5) es equivalente a encontrar
enteros x y k tales que ax b = km o
ax + (m)k = b (6)
Aqu ya se sabe que la ecuacion (6) tiene solucion si y solo s d[b, donde
d = (a, m). (ver Teorema 4.1).
de manera que la congruencia (5) tiene una solucion x si y solo s d[b, con
d = (a, m).
Ahora bien por el Teorema 4.1 cada solucion de (6) es de la forma
x = u
0
+
m
d
t, k = v
0

a
d
t, t Z (7)
Lic. Walter Otoniel 24
donde u
0
, v
0
constituyen una solucion particular de (6).
Entre los diferentes valores de x descritos en (7) observese que los d valores
u
0
, u
0
+m/d, u
0
+ 2m/d, . . . , u
0
+ (d 1)m/d no son congruentes modulo m
dos a dos, ya que la diferencia absoluta entre cualesquiera dos de ellos es
menor que m. si x = u
o
+mt/d es cualquier otro valor , se escribe t = qd+r,
donde 0 r < d, y se ve que
x = u
0
+ m(qd + r)/d
= u
0
+ mq + mr/d
u
0
+ mr/d(m)
De aqu, toda solucion x de (6) y por lo tanto de (5) es congruente a uno
de los d valores dados arriba. As pues, existen d = (a, m) soluciones no
congruentes entre s modulo m, si existe alguna.
Con todo lo anterior se ha probado el siguiente Teorema.
Teorema 3.1 Si d = (a, m), entonces la congruencia
ax b(m)
no tiene solucion si d ,[b, y tiene exactamente d soluciones no congruentes
entre s modulo m si d[b.
Ejemplo 3.2
Ya que (15, 12) = 3 y 3[9, la congruencia
15x 9(12)
tiene exactamente 3 soluciones no congruentes entre s modulo 12. Por simple
inspeccion, se ve que x = 3 es una solucion. Por lo tanto todas las soluciones
estan dadas por
x = 3 + (12/3)t = 3 + 4t t = . . . , 2, 1, 0, 1, 2, . . .
Para t = 0, 1, 2 se obtienen tres soluciones no congruentes entre s modulo
12: 3, 7, y 11.
Denicion: Se dice que una solucion x de una congruencia de la forma
ax b(m) es unica modulo m si cualquier solucion x
0
de esta es congruente
a x modulo m.
Denicion: si nx 1(m), se dice que x es el inverso de n modulo m.
Lic. Walter Otoniel 25
Corolorario 3.1 Si (a, m) = 1, entonces a tiene un inverso, y este es unico
modulo m.
Demostracion: Si (a, m) = 1, el Teorema 3.1 implica que
ax 1(m)
tiene una solucion q, y esta es unica modulo m.
Ejemplo 3.3
Ya que 5
2
= 25 1(8), se ve que 5 es su propio inverso modulo 8. Oservese
que -3 y 13 tambien son inversos de 5 modulo 8; esto no constituye una
inconsistencia ya que 3 5 13(8).
Hasta aqu se ha trabajado una unica congruencia lineal, sin embargo, como
el caso de ecuaciones tambien se puede trabajar un sistema de congruencias
lineales, que es lo que se hara enseguida.
Una solucion del sistema de congruencias
a
1
x b
1
(m
1
)
a
2
x b
2
(m
2
)
.
.
.
a
s
x b
s
(m
s
)
es un entero que satisface cada congruencia en el sistema.
Un ejemplo simple de tal sistema sucede en la solucion de la unica congruencia
lineal con modulo grande. Sea m con factorizacion
m = p
e
1
1
p
e
2
2
. . . p
es
s
;
ya que p
e
i
i
[m se tiene que
A B(m)
si y solo s cada una de las congruencias
A B(p
e
1
1
)
A B(p
e
2
2
)
.
.
.
A B(p
es
s
)
se cumplen. De lo anterior se sigue que la congruencia
ax b(m)
Lic. Walter Otoniel 26
tiene las mismas soluciones que el sistema de congruencias simultaneas
ax b(p
e
1
1
)
ax b(p
e
2
2
)
.
.
.
ax b(p
es
s
)
Aunque existen varias congruencias a resolver en el anterior sistema, los mod-
ulos son generalmente mucho mas peque nos que m, y, como se vera, el calculo
se ha simplicado.
Ejemplo 3.4
La congruencia
3x 11(2275)
Ya que 2275 = 5
2
7 13 la congruencia anterior puede ser reemplazada por
el siguiente sistema de congruencias lineales, con modulo peque no
3x 11(25)
3x 11(7)
3x 11(13)
El teorema basico de existencia para sistemas de congruencias lineales es el
Teorema Chino del Resto, el cual es nombrado as en honor de Sun-Tsu,
quien se cree fue el primer matematico que estudio casos especiales de este
teorema. El metodo de prueba proporciona ademas un algoritmo para con-
struir las soluciones de un sistema de congruencias, a partir de las soluciones
individuales de cada congruencia en el sistema.
Teorema 3.2 (Teorema Chino del Resto) Supongase que m
1
, m
2
, . . . , m
s
son s enteros, primos relativos dos a dos. Sea M = m
1
m
2
. . . m
s
, y supongase
que a
1
, a
2
, . . . , a
s
son enteros tales que (a
i
, m
i
) = 1 para cada i. Entonces las
s congruencias
a
1
x b
1
(m
1
)
a
2
x b
2
(m
2
)
.
.
.
a
s
x b
s
(m
s
)
tienen una solucion simultanea que es unica modulo M.
Lic. Walter Otoniel 27
Demostracion: De las soluciones de cada congruencia particular, se con-
struira una com un al sistema. primero se escogen los enteros c
1
, c
2
, . . . , c
s
,
tales que
a
i
c
i
b
i
(m
i
)
(El Teorema 3.1, garantiza la existencia de tales enteros). Ahora bien, Sea
n
i
=
M
m
i
, ya que los m
i
son primos relativos dos a dos, se tiene que (n
i
, m
i
) =
1. De aqu por el Corolario 5.1, existe un q
i
tal que n
i
q
i
1(m
i
). Sea
x
0
= c
1
n
1
q
1
+ c
2
n
2
q
2
+ . . . + c
s
n
s
q
s
se mostrara que es una solucion de el sistema original de s congruencias.
Primero, (por construccion de n
j
) notese que m
i
[n
j
exepto para j = i. De
aqu
a
i
x
o
= a
i
c
1
n
i
q
1
+ a
i
c
2
n
2
q
2
+ . . . + a
i
c
i
n
i
q
i
+ . . . + a
i
c
s
n
s
q
s
a
i
c
i
n
i
q
i
(m
i
)
a
i
c
i
(m
i
), (ya que n
i
q
i
1(m
i
))
b
i
(m
i
)
Por lo tanto x
0
es una solucion de cada congruencia.
Por otro lado si y es una solucion del sistema de s congruencias, entonces
por el Teorema 3.1, x
0
c
i
y(m
i
). De aqu m
i
[(x
0
y) para cada m
i
;
ya que los m
i
son primos relativos dos a dos, m
1
m
2
. . . m
s
[(x
0
y), es decir
M[(x
0
y). Por lo tanto x
0
y(M).
Ejercicios 3.1
1. Dado que (a, m) = 1 y (a1, m) = 1, Pruebe que 1+a+a
2
+. . .+a
(m)

0(m).
2. Demuestre que si r
1
+ r
2
+ . . . + r
(m)
0(m).
3. Encuentre el menor entero positivo x que satisfaga cada una de las
siguientes congruencias:
a) 3
56
x(7)
b) 738 x(11)
c) 7
128
x(13)
Lic. Walter Otoniel 28
4. Demuestre que si p 3(4), entonces el producto de todos los enteros
pares menores que p es congruente con 1 o 1 modulo p.
5. Encuentre todas las soluciones de los siguientes sistemas de congruen-
cias:
a) x 1(3), x 1(2)
b) x 3(5), x 5(7), x 7(11)
c) 2x 1(5), 3x 2(7), 4x 3(11)
3.2. Breve Introduccion a la Teora de Grupos Anillos
y Campos
En esta seccion se discutira algunas de las formas en las cuales los concep-
tos elementales de la teora de n umeros surgen en el algebra. La teora de los
n umeros proporciona una variedad de ejemplos de las estructuras del agebra
abstracta: Grupos Anillos y Campos. Antes de dar la denicion formal de
grupo se revisa un poco el lenguaje usado. Las operaciones de adicion y
multiplicacion se llaman operaciones binarias debido a que dos (o mas)
elementos se suman o se multiplican para producir un tercer elemento.La
sustraccion de pares de elementos, a b, la potenciacion a
b
tambien son op-
eraciones binarias.
Una operacion binaria se dice que es unvoca si para cada par de elementos
a, b, a b tiene un valor unico o bien no esta denido.
Por otro lado se dice que un conjunto A de elementos es cerrado respecto
a una operacion , si a b esta denido y es un elemento del conjunto para
todo par de elementos a, b A.
Un elemento e A es un elemento identidad respecto a la operacion si
se cumple que e a = a e, a A.
Asumiendo la existencia del elemento identidad e, se dice que un elemento a
tiene un inverso a
1
, si se cumple la propiedad a a
1
= a
1
a = e.
Se esta listo para la siguiente denicion: Denicion: Un grupo G es un con-
junto de elemtos a, b, c, . . . en G junto con una operacion binaria unvoca
tal que
1. G es cerrado bajo la operacion ,
2. Se cumple la ley asociativa a +(b c) = (a +b) c, a, b, c G,
Lic. Walter Otoniel 29
3. Existe un unico elemento identidad e en G,
4. Cada elemento a G tiene un inverso a
1
G.
Se dice que el grupo G es abeliano o conmutativo si ab = ba, a, b
G. Un grupo G se dice nito si card(G) es nito; en caso contrario se dira que
G es innito. si G es nito, el card(G) recibe el nombre de orden del grupo.
Lic. Walter Otoniel 30
4. ECUACIONES DIOFANTINAS
4.1. La ecuacion ax + by = c
En esta parte se hara uso especial del mcd, para probar una condicion
necesaria y suciente para que la ecuacion ax + by = c tenga soluciones
enteras.
Teorema 4.1 La ecuacion ax +by = c tiene soluciones en enteros si y solo
s d[c, donde d = (a, b). Ademas, si u
0
, v
0
es una solucion particular, la
solucion general tiene la forma:
x = u
0
+
b
d
k, y = v
0

a
d
k, k Z
Demostracion: Por propiedades de divisibilidad d[ax+by, para toda pereja
[x, y], as que si d ,[c, entonces la ecuacion no tiene soluciones en Z.
Por otro lado, si d[, se sabe que existen enteros (propiedad lineal del mcd)
u, v tales que au + bv = d, multiplicando ambos lados de esta ecuacion por
c
d
se tiene:
a
_
u
c
d
_
+ b
_
v
c
d
_
= c
de donde u
0
=
_
u
c
d
_
, v
0
=
_
v
c
d
_
es una solucion particular de la ecuacion.
Para poder encontrar todas las soluciones, supongase que (x, y) es una solu-
cion arbitraria. entonces
ax + by = au
0
+ bv
0
a(x u
o
) = b(v
0
y)
de donde b[a(x u
0
) por lo que
b
d
[
a
d
(x u
0
), pero recordar que
_
a
d
,
b
d
_
= 1 ,
por lo tanto
b
d
[(x u
0
).
Es decir x u
0
=
b
d
k, para alg un entero k, as que x = u
0
+
b
d
k.
Sutituyendo este valor en la ecuacion ax + by = c se tiene que
a(u
0
+
b
d
k) + by = c,
by = c au
0
a
b
d
k
by = bv
0
b
a
d
k
Lic. Walter Otoniel 31
as que y = v
0

a
d
k as pues se concluye que toda solucion entera se puede
expresar como
x = u
0
+
b
d
k, y = v
0

a
d
k
Ejemplo 4.1
Encontrar todas las soluciones enteras de x+y = 2, 3x4y = 5, 8x12y = 48.
No esta mal encontrar la solucion particular por simple inspeccion (si esto es
facil, claro), as pues, notese que x = 1, y = 1, para la primera ecuacion, x =
3, y = 1, para la segunda, nalmente para encontrar una solucion particular
para la tercera ecuacion, notese que por la propiedad lineal del mcd aplicada
a (12, 8) = 4, se tiene que 4 = 1 12 + (1) 8, multiplicando esta ecuacion
por 48/4, se obtiene 48 = 12 12 + (12) 8, o 48 = 8 (12) 12 (12).
As pues la solucion particular es x = 12, y = 12. Entonces las soluciones
generales de estas ecuaciones estan dadas por
_
x = 1 + k
y = 1 k
,
_
x = 3 4k
y = 1 3k
,
_
x = 12 3k
y = 12 2k
Ejercicios 4.1
1. Si N = abc + 1, demostrar que (N, a) = (N, b) = (N, c) = 1.
2. Demostrar que (k, n + k) = 1 si y solo s (k, n) = 1.
3. Demostrar que (k, n + k) = d si y solo s (k, n) = d.
4. Demostrar que si x
2
+ ax + b = 0 tiene una raz entera, es un divisor
de b.
5. Demostrar que n(n + 1) nunca es un cuadrado, para n > 1.
6. En un cine cobran 6 pesos a mayores, y 2.50 pesos a los menores. En
un cierto da se recaudaron 300 pesos y asistieron mas adultos que
menores. cuales fueron los posibles n umeros de asistentes?
7. Un hombre cobra un cheque por d dolares y c centavos en un banco.
El cajero, por error, le da c dolares y d centavos. El hombre no se da
cuenta hasta que gasta 23 centavos y ademas se da cuenta que en ese
momento tiene 2d dolares y 2c centavos. Cual era el valor del cheque?
Lic. Walter Otoniel 32
8. Un hombre compro doce piezas de fruta (manzanas y naranjas) por 99
centavos. Si una manzana cuesta 3 centimos mas que una naranja, y
compro mas manzanas que naranjas, cuantas compro de cada una?
9. En una clase de teora de n umeros hay estudiantes de segundo, tercer
y cuarto curso. Si cada estudiante de segundo curso contribuye con $
1.25, cada uno de tercero con $ 0.90 y cada uno de cuarto con $ 0.50,
el instructor recibira una paga de $ 25. Hay 26 estudiantes; cuantos
hay de cada grado?
4.2. La ecuacion x
2
+ y
2
= z
2
En esta seccion se trata con uno de los problemas mas antiguos de la teora
de n umeros, esto es, hallar todos los triagulos rectangulos cuyos lados son
enteros, es decir hallar todas las soluciones enteras positivas de la ecuacion
x
2
+ y
2
= z
2
Se hara uso del siguiente resultado: Todo cuadrado perfecto es de la forma
4k o de la forma 4k + 1
Se dice que una terna x, y, z es un triple pitagorico si cumple que x
2
+y
2
= z
2
Ya que se decea resolver la ecuacion x
2
+ y
2
= z
2
en esteros positivos, con-
siderese una solucion x, y, z de este tipo. Sea d = (x, y), entonces es claro que
d[z
2
, de donde d[z, y ya que (x, y, z) = ((x, y), z) se tiene que d = (x, y, z).
As pues d = (x, y, z) = (x, y) = (x, z) = (y, z) y
_
x
d
_
2
+
_
y
d
_
2
=
_
z
d
_
2
con
_
x
d
,
y
d
_
=
_
x
d
,
z
d
_
=
_
y
d
,
z
d
_
= 1
Una solucion x
1
, y
1
, z
1
de la ecuacion, que cumpla que estos tres son relativa-
mente primos dos a dos recibe el nombre de solucion primitiva. Notese que
toda solucion x, y, z puede escribirse en la forma dx
1
, dy
1
, dz
1
, donde x
1
, y
1
, z
1
es una solucion primitiva. Recprocamente, si x
1
, y
1
, z
1
es una solucion prim-
itiva, entonces dx
1
, dy
1
, dz
1
es una solucion si d es cualquier entero positivo.
Por tanto solo es necesario obtener las soluciones primitivas, que es lo que se
hace a continuacion. Notese que x y y no pueden ser de la misma paridad,
ya que ambos no pueden ser pares, y si ambos fuesen impares se tendra que
z
2
sera de la forma 4k + 2, algo imposible.
Supongase pues (sin perdida de generalidad) que y es par, x y z impares.
Entonces
y
2
= z
2
x
2
Lic. Walter Otoniel 33
dividiendo esta ecuacion por 4 se tiene
_
z + x
2
__
z x
2
_
=
_
y
2
_
2
(8)
es facil darse cuenta que z + x y z x son ambos pares. Ademas, por
propiedades de divisibilidad es claro que
_
z + x
2
,
z x
2
_

_
z + x
2
+
z x
2
_
= z
_
z + x
2
,
z x
2
_

_
z + x
2

z x
2
_
= x
por tanto, ya que (x, y) = 1
_
z + x
2
,
z x
2
_
= 1
y como el producto
_
z + x
2
__
z x
2
_
es un cuadrado perfecto, cada uno
de estos dos factores debe ser un cuadrado perfecto, es decir:
z + x
2
= s
2
,
z x
2
= t
2
. Notese que s > t > 0; ademas, (s, t) = 1, y resolviendo el sistema
_
_
_
z + x
2
= s
2
,
z x
2
= t
2
,
se tiene
_
x = s
2
t
2
,
z = s
2
+ t
2
,
reemplazando en y
2
= z
2
x
2
se obtiene
_
_
_
y
2
= (s
2
+ t
2
)
2
(s
2
t
2
)
2
,
= 4s
2
t
2
,
y = 2st
para terminar, notese que si s y t fuesen de la misma paridad, se tendra que
x y z seran ambos pares, contradiciendo el hecho que (x, z) = 1. Recproca-
mente, por sustitucion directa se verica que los tres n umeros x = s
2
t
2
,
y = 2st, z = s
2
+t
2
satisfacen la ecuacion pitagorica x
2
+y
2
= z
2
. As se ha
demostrado el siguiente teorema.
Lic. Walter Otoniel 34
Teorema 4.2 Todas las soluciones primitas positivas de la ecuacion x
2
+
y
2
= z
2
, donde x es impar e y es par, estan dadas por
_
_
_
x = s
2
t
2
,
y = 2st,
z = s
2
+ t
2
para cualesquiera s, t enteros que satisfagan las condiciones siguientes:
(a) s > t > 0,
(b) (s, t) = 1,
(c) s y t tienen distinta paridad
4.3. La ecuacion x
4
+ y
4
= z
2
En esta seccion interesa encontrar soluciones para la ecuacion x
4
+y
4
= z
2
en enteros positivos. Se puede restringir la b usqueda a soluciones x, y, z
para las cuales (x, y) = 1, como se hizo en la seccion anterior. Ahora bien
(x
2
)
2
+(y
2
)
2
= z
2
donde x
2
, y
2
, z es una solucion primitiva de la ecuacion en
de la seccion anterior.
Sin perdida de generalidad puede suponerse que y
2
es par, demanera que y
es par. As que existen dos enteros m, n tales que x
2
= m
2
n
2
, y
2
= 2mn,
z = m
2
+ n
2
, m > n > 0, (m, n) = 1 y m y n son de distinta paridad. Si
m fuera par, entonces n sera impar y se tendra x
2
0 1(4). Lo cual es
imposible, por lo cual m es impar y n es par. Observese que
_
y
2
_
2
= m
n
2
,
_
m,
n
2
_
= 1,
as que existen enteros r, s tales que
m = r
2
,
n
2
= s
2
, y = 2rs, (r, s) = 1, r > 0, s > 0, r impar.
Ademas, x
2
+ n
2
= m
2
obteniendo que x
2
+ 4s
4
= r
4
. Notando ue r, 2s=1,
se puede aplicar la teora de la seccion anterior a esta ecuacion. As pues,
existen enteros t y w tales que
x = t
2
w
2
, 2s
2
= 2tw, r
2
t
2
+ w
2
, (t, w) = 1, t > w > 0.
Lic. Walter Otoniel 35
Ya que tw = s
2
, puede escribirse t = f
2
, w = g
2
para algunos f > 0, g > 0,
(f, g) = 1. Entonces se tendra que r
2
= f
4
+ g
4
, pero esta ecuacion tine
la misma forma que la ecuacion original!. As que en el afan de tratar de
reducir la ecuacion original a algo mas sencillo se ha llegado a una ecuacion
que tiene la misma forma. Cualquiera dira que no se ha ganado algo, pero es
posible que s. Observese que se inicio con la solucion x, y, z y se nalizo con
la solucion f, g, r, puede verse que se ha encontrado una solucion diferente,
en efecto, z = m
2
+ n
2
= r
4
+ 4s
4
> r
4
, de modo que z > r y f, g, r es una
solucion diferente. Mas que esto, se obtenido una solucion con z > r > 0.
Ahora bien, si se aplica la misma reduccion completa a la nueva solucion se
obtendra otra solucion f
1
, g
1
, r
1
, con r > r
1
> 0. Si se continua este proceso
se obtiene una sucesion completa de soluciones con correspondientes r
i
tales
que r > r
1
> r
2
> . . . > 0, en donde todos los r
i
son enteros, as se debe
tener que r
r
0. Por lo tanto la suposicion de que hubiera una solucion ha
conducido a una contradiccion.
Se ha demostrado pues que la ecuacion no tiene solucion x, y, z en enteros
positivos con (x, y) = 1.
Por otro lado si x, y, z fuera cualquier solucion entera de la ecuacion con
xy ,= 0, entonces
[x[
d
,
[y[
d
,
[z[
d
2
donde d = (x, y) sera una solucion en enteros
positivos con
_
[x[
d
,
[y[
d
_
= 1.
Por lo tanto, cualquier solucion x, y, z sera tal que xy = 0. Con todo lo
anterior se ha probado el siguiente teorema
Teorema 4.3 Las unicas soluciones enteras de x
4
+ y
4
= z
2
son las solu-
ciones triviales x = 0, y, z = y
2
, y x, y = 0, z = x
2
.
La tecnica usada en la demostracion anterior se conoce como demostracion
por descenso o bien metodo del descenso innito de fermat, claramente
se basa en el principio de buena ordenacion.
A partir del hecho de que la ecuacion x
4
+y
4
= z
2
no tiene soluciones enteras
positivas es facil darse cuenta que la ecuacion x
4
+y
4
= z
4
tampoco tendra.
Este no es mas que un caso particular de la famosa conjetura de Fermat que
establece que para n > 2, las ecuaciones x
n
+ y
n
= z
n
no tienen soluciones
enteras diferentes de las triviales en las cuales una de las variables es cero.
Lic. Walter Otoniel 36
4.4. Suma de Cuatro Cuadrados
En esta seccion se probara que si n Z
+
, entonces existen enteros x
j
(j = 1, 2, 3, 4), tales que n = x
2
1
+x
2
2
+x
2
3
+x
2
4
; es decir todo entero positivo
puede ser escrito como una suma de cuatro cuadrados. Para probar esto es
importante la siguiente identidad:
Lema 4.1
4

j=1
x
2
j
4

j=1
y
2
j
= (x
1
y
1
+ x
2
y
2
+ x
3
y
3
+ x
4
y
4
)
2
+ (x
1
y
2
x
2
y
1
+ x
3
y
4
x
4
y
3
)
2
+ (x
1
y
3
x
3
y
1
+ x
4
y
2
x
2
y
4
)
2
+ (x
1
y
4
x
4
y
1
+ x
2
y
3
x
3
y
2
)
2
A partir del lema 4.1 sera suciente probar que todo primo puede ser ecrito
como una suma de cuatro cuadrados. Ya que 2 = 1
2
+ 1
2
+ 0
2
+ 0
2
, se
restringira el analisis a primos impares.
Lema 4.2 Si p es un primo impar, entonces existen a, b Z tales que
0 a
p 1
2
, 0 b
p 1
2
, y a
2
+ b
2
+ 1 0(p).
Demostracion: Considerense los conjuntos
A =
_
a
2
: a = 0, 1, . . . ,
p 1
2
_
B =
_
b
2
1 : b = 0, 1, . . . ,
p 1
2
_
Es claro que ning un par de elementos de A son congruentes entre s modulo p,
ya que si a
2
i
a
2
j
(p), entonces a
i
a
j
0(p) o a
i
+ a
j
0(p). Si a
i
a
j
(p),
entonces a
i
= a
j
, ya que 0 a
i
, a
j

p 1
2
; si a
i
+ a
j
0(p), entonces
a
i
= a
j
= 0. De manera Analoga se establece que ning un par de elementos
de B son congruentes entre s modulo p. Pero el conjunto A B tiene p +1
elementos, as que alg un a
2
A es congruente modulo p a alg un b
2
1 B.
Es decir a
2
+ b
2
+ 1 0(p).
De el lema anterior se tiene que a
2
+ b
2
+ 1 = kp, para alg un entero k > 0;
Tanbien ya que
0 < kp = a
2
+ b
2
2
_
p 1
2
_
2
+ 1 < p
2
,
Lic. Walter Otoniel 37
k < p. Se ha estalecido el siguiente resultado: Existen x
j
Z (j = 1, 2, 3, 4)
tales que
kp =
4

j=1
x
2
j
, (9)
0 < k < p, y x
j
, 0(p) para al menos un x
j
.
Si logra mostrar que el menor k para el cual (9) es ja es k = 1, entonces
se habra demostrado que todo primo impar p es expresable como lasuma de
cuatro cuadrados.
Sea m el menor entero positivo k para el cual (9) es ja.
Supongase que m > 1. Si m es par, entonces se puede asumir que
x
1
x
2
(2) y x
3
x
4
(2).
Es decir, si m es par, entonces ninguno, dos, o cuatro de los x
j
son pares,
as (9) se puede reescribir de la siguiente forma, (tomando m = k)
_
x
1
+ x
2
2
_
2
+
_
x
1
x
2
2
_
2
+
_
x
3
+ x
4
2
_
2
+
_
x
3
x
4
2
_
2
=
m
2
p
Pero entonces se tiene que
m
2
p se puede representar como una suma de cuatro
cuadrados; a partir de la manera como se escogio m y de (9) se puede concluir
que
x
1
+ x
2
2

x
1
x
2
2

x
3
+ x
4
2

x
3
x
4
2
0(p).
Pero entonces
x
1
+ x
2
2

x
1
x
2
2
0(p)
De donde x
1
x
2
0(p); similarmente, x
3
x
4
0(p), pero esto contradice
(9). Por lo tanto m es impar.
Se tiene pues que m 3 e impar, se puede encontrar y
j
en un absolutamente
menor SCR modulo m, es decir [y
j
[ < m/2, tal que y
j
x
j
(p) para j =
1, 2, 3, 4, esto quiere decir que existe m
j
tal que
y
j
= x
j
+ m
j
m, j = 1, 2, 3, 4. (10)
Lic. Walter Otoniel 38
Ahora
4

j=1
y
2
j
=
4

j=1
x
2
j
+ 2m
4

j=1
x
j
m
+
j
m
2
4

j=1
m
2
j

j=1
x
2
j
(m)
Por lo tanto, Para alg un M se tiene que Mm =

y
2
j
. Ya que [y
j
[ < m/2,
0 Mm < 4(m/2)
2
= m
2
.
Si M = 0, entonces y
j
= 0 para todo j. Pero entonces de (10), x
j
= m
j
m,
y de (9) se tiene que mp = m
2

(m
j
)
2
, o m[p, lo cual es imposible. Por lo
tanto, 0 < Mm < m
2
, as 0 < M < m.
Ahora se tiene

x
2
j
= mp,

y
2
j
= Mm, y 0 < M < m < p. Sea
w
1
= x
1
y
1
+ x
2
y
2
+ x
3
y
3
+ x
4
y
4
w
2
= x
1
y
2
x
2
y
1
+ x
3
y
4
x
4
y
3
w
3
= x
1
y
3
x
3
y
1
+ x
4
y
2
x
2
y
4
w
4
= x
1
y
4
x
4
y
1
+ x
2
y
3
x
3
y
2
y usando el lema 4.1 se encuentra que
4

j=1
w
2
j
= Mm
2
p. (11)
Notese que w
1
=

x
j
y
j
=

x
j
(x
j
+ m
j
m) =

x
2
j
+ m

x
j
y
j
0(m).
An alogamente, se establece que w
2
w
3
w
4
0(m). Escribiendo w
j
=
W
j
m y de (11) se tiene

W
2
j
= Mp. De (9) se concluye que W
j
0(p), j =
1, 2, 3, 4. As escribiendo W
j
= D
j
p; entonces Mp =

W
2
j
= p
2

D
2
j
, de lo
cual se tiene que p[M, pero esto es imposible. De aqu m = 1 y todo primo
es la suma de cuatro cuadrados.
El lema 4.1 junto con el lema 4.2 demuestran el siguiente Teorema
Teorema 4.4 Todo entero positivo puede ser escrito como la suma de cuatro
cuadrados
Lic. Walter Otoniel 39
5. FUNCIONES ARITM

ETICAS
5.1. La Funcion Parte Entera
La funcion Parte Entera no forma parte del conjunto de Funciones Ar-
itmeticas, sin embargo, se abordara su estudio ya que es de mucha impor-
tancia en la teora de n umeros, su ubicacion aqu es con el unico proposito
de que quede junto con las otras funciones de Teora de N umero que se re-
visaran.
Sea x un n umero real cualquiera, el smbolo x| denotara el mayor entero
que es menor o igual a x. As por ejemplo 3,0006| = 3, | = 3, | = 4,
5,83| = 6. La funcion f tal que f(x) = x|, se llama funcion parte entera
y es muy importante en teora de n umeros. Notese que el dominio de f es el
conjunto de n umeros reales, y su rango es el conjunto de n umeros enteros. El
teorema siguiente enuncia las propiedades mas relevantes de dicha funcion.
Teorema 5.1 Sea x cualquier n umero real:
1. x 1 < x| x, x| x < x| + 1, 0 x x| < 1.
2. Si n Z, x + n| = x| + n.
3. x| + y| x + y| x| + y| + 1.
4. x| + x| =
_
0 si x es un entero
1 si x no es un entero
5.
_
x|
m
_
=
_
x
m
_
6. x| es el menor entero mayor o igual que x.
5.2. La Funcion (n)
Cualquier funcion cuyo dominio es alg un subconjunto de los n umeros en-
teros es llamada una Funcion Aritmetica.
Para algunas demostraciones de esta seccion se utilizaran argumentos com-
binatorios.
Ejemplo 5.1 Sea p primo, determine (p
m
).
Lic. Walter Otoniel 40
Claramente hay p
m1
enteros positivos menores o iguales que p que no son
primos relativos con p
m
, estos son: p, 2p, 3p, . . . , p
m1
p. Por lo tanto, existen
p
m
p
m1
enteros positivos menores que y primos relativos con p
m
. De manera
que
(p
m
) = p
m
p
m1
= p
m
_
1
1
p
_
.
Teorema 5.2 Supongase que a toma valores en un sistema completo de
residuos modulo m, y que a

toma valores en un sistema completo de residuos

modulo m

, con (m, m

) = 1, entonces am

+a

m toma valores en un sistema

completo de residuos modulo mm

Demostracion: Primero, notese que existen mm

n umeros de la forma am

+
a

m. Si a
i
m

+a

i
m a
j
m

+a

j
(mm

), entonces mm

[[(a

1
a

2
)m+(a
1
a
2
)m

],
de aqu se tendra que m

[(a

1
a

2
)m y m[(a
1
a
2
)m

, es decir a

1
m

2
m

(m) y a
1
m

a
2
m

(m), es decir a

1
a

2
(m) y a
1
a
2
(m

), obteniendose
una contradiccion. As pues los mm

n umeros son incongruentes entre s,

formando un sistema completo de residuos modulo mm

.
Una funcion f(m) se dice multiplicativa, si (m, m

) = 1 implica f(mm

) =
f(m)f(m

). Del anterior Teorema es trivial probar el siguiente Corolario.

Corolorario 5.1 (n) es multiplicativa.
Demostracion: Por el teorema anterior, am

+a

m recorre un sistema com-

pleto de residuos modulo mm

cuando a y a

recorren sistemas completos de

residuos modulo m y m

, respectivamente. Por otro lado

(am

+ a

m, mm

) = 1 [(am

+ a

m, m) = 1] [(am

+ a

m, m) = 1]
[(am

, m) = 1] [(a

m, m

) = 1]
[(a, m) = 1] [(a

, m

) = 1]
De aqu los (mm

) n umeros menores que y primos con mm

son los menores

residuos positivos de los (m)(m

) valores de am

+ a

m para los cuales a

es primo a m y a

a m

; y por lo tanto
(mm

) = (m)(m

)
Es importante que m y n sean primos relativos. Efectivamente, (2) = 1 y
(2
2
) = 2 ,= (2)(2).
Lic. Walter Otoniel 41
Teorema 5.3 Si n > 1 entonces (n) = n

p|n
(1
1
p
).
Observacion: El smbolo

p|n
denota el producto del conjunto de todos los
primos que dividen a n. De manera analoga, mas adelante

d|n
(d) deno-
tara la suma de los valores de la funcion tomada para todos los divisores
de n.
Demostracion: Si n > 1 puede escribirse n = p
m
1
1
p
m
2
2
. . . p
m
j
j
.
Ahora bien, (p
m
i
i
, p
m
i+1
i+1
p
m
i+2
i+2
. . . p
m
j
j
) = 1 para i = 1, 2, . . . , j 1. Aplicando
el Corolario 5.1 r 1 veces, se tiene
(n) =
r

i=1
(p
m
i
i
)
Recuerdese que (p
m
) = p
m
p
m1
, por lo tanto
(n) =
r

i=1
p
i
m
i
_
1
1
p
i
_
= n
r

i=1
_
1
1
p
i
_
= n

p|n
_
1
1
p
_
Ejemplo 5.2
Del Ejemplo 5.1, es facil ver que
1+(p) +(p
2
) +. . . +(p
m
) = 1+(p1) +(p
2
p) +. . . +(p
n
p
n1
) = p
m
El siguiente Teorema es una generalizacion del ejemplo anterior.
Teorema 5.4

d|n
(d) = n
Demostracion: Sea S
n
= 1, 2, . . . , n, evidentemente card(S
n
) = n.
Para cada d que divida a n, sea D
d
(n) = m Z
+
, m n : (m, n) = d.
Por ejemplo, tomando n = 6, D
1
(6) = 1, 5, D
2
(6) = 2, 4, D
3
(6) = 3,
D
4
(6) = , D
5
(6) = , D
6
(6) = 6. No es difcil darse cuenta que para cada
n los D
d
(n) son conjuntos disjuntos. Ademas para cada m S
n
, m D
d
(n),
donde (m, n) = d. En consecuencia
n = card(S
n
) =

d|n
card(D
d
(n))
Lic. Walter Otoniel 42
Ahora se mostrara que card(D
d
(n)) = (n/d). Notesse que todo los elementos
de D
d
(n) son m ultiplos de d, y son menores o iguales que n. De aqu los
elementos de D
d
(n) se encuentran entre los n umeros d, 2d, . . . , (n/d)d. Pero
si (a, n/d) = x, entonces claramente (ad, n) = xd, y xd = d si y solo s x = 1.
Por lo tanto, los unicos ad D
d
(n) son aquellos para los cuales (a, n/d) = 1,
por denicion de la funcion existen (n/d) de tales n umeros. De donde
n = card(S
n
) =

d|n
card(D
d
(n)) =

d|n
(n/d)
pero notese que

d|n

_
n
d
_
=

d|n
(d)
Queda pues demostrado el teorema.
5.3. Formulas para d(n) y (n)
En esta seccion se encontraran formulas para el n umero d(n) de divisores
de n, y la suma (n) de estos divisores. Como en el caso de la funcion (n)
estas funciones son facilmente evaluadas cuando n es una potencia de un
primo.
Ejemplo 5.3
Si p denota un primo, entonces los unicos divisores de p son 1 y p. De
qu d(p) = 1 y (p) = p + 1. De manera as general, lo divisores positivos de
p
n
son 1, p, p
2
, . . . , p
n
, De manera que d(p
n
) = n + 1 y
(p
n
) = 1 + p + p
2
+ . . . + p
n
=
p
n+1
1
p 1
, por Teorema 1.1
El siguiente Teorema establece las formulas generales para d(n) y (n)
Teorema 5.5 Si n = p
m
1
1
p
m
2
2
. . . p
m
j
j
, entonces
d(n) = (m
1
+ 1)(m
2
+ 1) . . . (m
j
+ 1)
y
(n) =
p
m
1
+1
1
1
p
1
1
p
m
2
+1
2
1
p
2
1
. . .
p
m
j
+1
j
1
p
j
1
Lic. Walter Otoniel 43
Demostracion: Para d(n) se dara un argumento combinatorio: Si n > 1,
n = p
m
1
1
p
m
2
2
. . . p
m
j
j
, es decir cada primo p
i
aparece m
i
veces, luego cada
divisor de n esta formado por productos de potencias de los primos que
aparecen en la descomposicion canonica de n. De manera que para el primo
p
i
se tienen (m
i
+ 1) opciones: no escogerlo, escogerlo una vez, escogerlo dos
veces, y as sucesivamente hasta escogerlo m
i
veces. Por la regla del producto
se podran construir (m
1
+ 1)(m
2
+ 1) . . . (m
j
+ 1) divisores. Es decir
d(n) = (m
1
+ 1)(m
2
+ 1) . . . (m
j
+ 1)
(si no se escoge ning un primo se obtiene el devisor 1).
Por otro lado, por el ejemplo 5.3, (p
m
i
i
) =
p
m
i
+1
i
1
p
i
1
, as ocupando de nuevo
la regla del producto ya que n = p
m
1
1
p
m
2
2
. . . p
m
j
j
se tendra que
(n) =
p
m
1
+1
1
1
p
1
1
p
m
2
+1
2
1
p
2
1
. . .
p
m
j
+1
j
1
p
j
1
Ahora se dene la funcion de mobius (n) muy importante para ciertos re-
sultados en teora de n umeros.
Denicion:
(n) =
_
_
_
1 si x = 1
0 si p
2
[n para alg un primo p
(1)
r
si n = p
1
p
2
. . . , p
r
donde los p
i
son primos distintos
Ejemplo 5.4
(2) = 1, (3) = 1, (4) = 0, (6) = 1.
Teorema 5.6 (n) =

d|n
(d)
n
d
.
Demostracion: Se deja como ejercicio.
El siguiente corolario es evidente a partir del Teorema 5.6
Corolorario 5.2 Si n = p
m
1
1
p
m
2
2
. . . p
m
j
j
, entonces
d(d) = d(p
m
1
1
)d(p
m
2
2
) . . . d(p
m
j
j
)
Lic. Walter Otoniel 44
Ejercicios 5.1
1. Pruebe que las funciones (n), (n), (n), d(n) son funciones aritmeticas
multiplicativas.
2. Pruebe que d(n) es impar si y solo s n es un cuadrado perfecto.
3. Muestre que

d|n
d = d
d(n)/2
4. Pruebe que el n umero de maneras de escribir n como suma de enteros
consecutivos es igual a d(m) donde m es el mayor impar dividiendo m.
5. Muestre que (n) d(m)(2), donde m es el mayor factor impar de n.
6. Suponga que f(n) y g(n) son multiplicativas y que f(p
r
) = g(p
r
) para
cada r y cada primo p. Pruebe que f(n) = g(n) para todo n.
7. Muestre que si (n)[n 1, entonces no existe ning un primo p tal que
p
2
[m.
8. C. Goldbach conjeturo que todo n umero par mayor que 2 es la suma
de dos primos. P. Erdos conjeturo que, para cualquier n umero par 2n,
existen enteros q y r tales que (q) + (r) = 2n. La conjetura de
Goldbach implica la de Erdos?
Lic. Walter Otoniel 45
6. CONGRUENCIAS CUADR

ATICAS
Hasta aqu se ha resuelto completamente la congruencia lineal
ax b(m)
Esta seccion sera dedicada al estudio un tanto avanzado de congruencias que
envuelvan polinomios cuadraticos. Se iniciara con la mas simple de estas:
x
2
a(p)
donde p es un primo. Se probara un importante teorema debido a Gauss, a
saber la Ley de Reciprocidad Cuadratica.El estudio de congruencias cuadraticas
se puede ver como la relacion entre los aspectos multiplicativos y los aditivos
de la teora de n umeros.
Ya se probo que los elementos de un sistema reducido de restos modulo m
forman un grupo bajo la operacion multiplicacion.
Ya que estudios posteriores, requieren familiaridad con la estructura de este
grupo, se revisaran un par de resultados los sitemas reducidos de restos modu-
lo p, donde p es un primo.
Ejemplo 6.1
Notese que (10) = 4, ademas 1, 3, 7, 9 es un sistema reducido de restos
modulo 10. Ya que
3
1
= 3 3(10)
3
2
= 9 9(10)
3
3
= 27 7(10)
3
4
= 81 1(10)
7
1
= 7 7(10)
7
2
= 49 9(10)
7
3
= 343 3(10)
7
4
= 2401 1(10)
Se tiene que 3, 3
2
, 3
3
, 3
4
y 7, 7
2
, 7
3
, 7
4
son tambien sistemas reducidos de
restos modulo 10
En el ejemplo anterior 4 = (10) es el menor entero h para el cual g
h
1(10),
donde g = 3, 7.
Denicion: Si h es el menor entero positivo tal que a
h
1(m) se dice que
a pertenece al exponente h modulo m.
Teorema 6.1 La congruencia a
b
1(m) se satisface para alg un entero b si
y solo s (a, m) = 1.
Lic. Walter Otoniel 46
Demostracion: Supongase que a
b
1(m), sea d = (a, m), evidentemente si
d[a y d[m entonces d[(a
b
1), de donde se tiene que d[1, por lo tanto d = 1.
Por otro lado, si (a, m) = 1, por el teorema de Euler a
(m)
1(m) as basta
tomar b = (m).
Teorema 6.2 Si a petenece al exponente h modulo m, y a
r
1(m), entonces
h[r.
Demostracion: Por el lema de la division de Euclides r = hq + s, con
0 s < h, de aqu
1 a
r
a
hq+s
(a
h
)
q
a
s
a
s
(m)
de donde s = 0, ya que por denicion h es el menor entero positivo tal que
a
h
1(m). Por lo tanto h[r.
Denicion: Si g es un entero pertenciendo al exponente (m) modulo m,
entonces g es llamada una raz primitiva modulo m.
Teorema 6.3 Si g es una raz primitiva modulo m, entonces g, g
2
, . . . , g
(m)
.
son mutuamente incongruentes y forman un sistema reducido de rstos modu-
lo m.
Demostracion: Evidentemente hay (m) elementos, (g
i
, m) = 1, i = 1, 2, . . . , (m).
Ahora supongase que
g
t
g
s
con 1 s < t (m) entonces m[(g
t
g
s
), es decir m[g
s
(g
ts
1) de aqu por
el teorema 1.6 m[(g
ts
1), de donde g
ts
1(m). Pero t s < (m), con-
tradiciendo el hecho de que g pertenece al exponente (m).
Teorema 6.4 Si a pertenece al exponente h modulo m y (k, h) = d, entonces
a
k
petenence al exponente h/d modulo m.
Corolorario 6.1 Si g es raz primitiva modulo m, entonces g
r
es una raz
primitiva modulo m si y solo s (r, (m)) = 1.
Teorema 6.5 Si Existe alguna raz primitiva modulo m, existen exacta-
mente ((m)) races primitivas no congruentes entre s.
Teorema 6.6 Para cada primo p, existen races primitivas modulo p.
Lic. Walter Otoniel 47
6.1. Residuos Cuadraticos-Criterio de Euler
Despues de la congruencia ax b(m) la congruencia mas simple es:
x
2
b(m) (12)
En donde la habilidad que se tenga para resolver (12) posibilitara determinar
cuando una congruencia cuadraticca de la forma
ax
2
+ bx + c 0(n)
tiene solucion.
Primero se obtendra un metodo para determinar cuando la congruencia
x
2
a(p) (13)
con p primo y (a, p) = 1, tiene solucion. Si (13) con las condiciones dadas
tiene una solucion, se dice que a es un residuo cuadratico modulo p.
Ejemplo 6.2
Los residuos cuadraticos modulo 7 son: 1, 4, y 9. Evidentemente cualquier
otro entero congruente a alguno de estos modulo 7 es tambien un residuo
cuadratico modulo 7.
Teorema 6.7 El n umero a es un residuo cuadratico modulo p si y solo s
a
p1
2
1(p)
Demostracion: Si a es un residuo cuadratico modulo p, existe un entero y
tal que
y
2
a(p)
ya que p ,[a, se tiene que p ,[y, de donde
a
p1
2
(y
2
)
p1
2
y
p1
(p)
por el teorema de Euler.
Por el otro lado, supongase que
a
p1
2
1(p)
Lic. Walter Otoniel 48
sea g una raz primitiva modulo p. Entonces existe un entero r tal que
g
r
a(p),
y as
g
r
p1
2
a
p1
2
1(p).
Aqu se debe tener p 1[r
p 1
2
, de manera que
r
2
debe ser entero, es decir
r = 2s, donde s es un entero. as, si x = g
s
, entonces
x
2
g
2s
g
r
a(p)
Lo cual establece el as llamado criterio de Euler.
La prueba del anterior teorema provee un importante corolario:
Corolorario 6.2 Sea g una raz primitiva modulo p, y (a, p) = 1. Sea r
cualquier entero tal que g
r
a(p). Entonces r es par si y solo s a es un
residuo cuadratico modulo p.
6.2. El Smbolo de Legendre
Ahora se introduce el smbolo de Legendre
_
a
p
_
, el cual simplica grande-
mente los calculos en problemas sobre residuos cuadraticos.
Denicion: Si p es un primo distinto de dos, entonces
_
a
p
_
=
_
_
_
1 si a es un residuo cuadratico modulo p
0 si p[a
1 en otro caso
Teorema 6.8 Si p es un primo distinto de 2 y a y b son relativamente primos
a p, entonces
_
a
p
_
=
_
b
p
_
, si a b(p) (14)
_
ab
p
_
=
_
a
p
__
b
p
_
(15)
Lic. Walter Otoniel 49
a
p1
2

_
a
p
_
(p) (16)
Demostracion: (14) se sigue directamente a partir de la denicion de
_
a
p
_
,
mientras que (15) se sigue a partir del corolario anterior.
Ahora para (16), notese que si a es un residuo cuadratico modulo p, entonces
el Teorema 14 implica que
a
p1
2
1 =
_
a
p
_
(p).
Si p[a, entonces
a
p1
2
0 =
_
a
p
_
(p).
Finalmente, si p ,[a, entonces a
p1
2
1(p), ya que
a
p1
1(p).
De donde, si (a, b) = 1 y a no es un residuo cuadratico modulo p, se tiene
que
a
p1
2
1 =
_
a
p
_
(p).
La denicion del smbolo de Legendre
_
a
m
_
se generaliza al caso donde m es
cualquier n umero impar, as:
Si m = p
1
P
2
. . . p
r
, donde los p
i
son primos impares (no necesariamente dis-
tintos), entonces
_
n
m
_
=
_
n
p
1
__
n
p
2
_
. . .
_
n
p
r
_
.
Este smbolo as extendido es llamado el smbolo de Jacobi
6.3. La Ley de Reciprocidad Cuadratica
Un famoso Teorema llamado La Ley de Reciprocidad Cuadratica debido a
Gauss, permite resolver a lo sumo todas las congruencias cuadraticas. Se dice
que este Teorema desconcerto a grandes matematicos tales como L. Euler y
A. Legendre. Este es de los grandes Teoremas de Gauss y lo demostro cuando
Lic. Walter Otoniel 50
solo tena 19 a nos, dando al menos 6 diferentes pruebas. Se probara primero
un Teorema llamado el Lema de Gauss.
Denicion: El menor residuo de n modulo m es el entero x que pertenece
al sistema completo de residuos modulo m absolutamente menor dado por
__
m + 2
2
_
,
_
m + 2
2
_
+ 1, . . . , 1, 0, 1, . . . ,
_
m
2
_
_
, y se denotara por LR
m
(n).
Ejemplo 6.3
El Conjunto 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5 es un sistema completo de
residuos modulo 11 absolutamente menor. As LR
1
1(21) = 1, LR
1
1(99) =
0, LR
1
1(60) = 5.
Denicion: Se dene el sgn(x) (ledo el signo de x) por
sgn(x) =
_
_
_
1 si x > 0,
0 si x = 0,
1 si x < 0.
Teorema 6.9 [Lema de Gauss]: Sea (m, p) = 1, donde p es un primo dis-
tinto de dos, y sea el n umero de enteros en el conjunto
_
m, 2m, . . . ,
p 1
2
m
_
cuyos menores residuos modulo p son negativos. Entonces
_
m
p
_
= (1)

.
Demostracion: Es claro que (jm, p) = 1 para j = 1, 2, . . . ,
p 1
2
m. Ahora
para cualquier n,
nm LR
p
(nm) = sgn(LR
p
(nm))[LR
p
(nm)[(p).
ya que 0 < [LR
p
(nm)[ < p/2, se tiene que si n toma todos los valores enteros
1, 2, . . . ,
p 1
2
, tambien [LR
p
(nm)[ los toma. De aqu
m(2m)(3m) . . . ((p1)/2)m sgn(LR
p
(m))[LR
p
(m)[sgn(LR
p
(2m))[LR
p
(2m)[ . . .
sgn(LR
p
((p 1)m/2))[LR
p
((p 1)m/2)[(p),
Lic. Walter Otoniel 51
o
m(2m)(3m) . . . ((p1)/2)m sgn(LR
p
(m))sgn(LR
p
(2m)) . . . sgn(LR
p
((p1)m/2))
[LR
p
(m)[[LR
p
(2m)[ . . . [LR
p
((p 1)m/2)[(p)
es decir
_
p 1
2
_
!m
p1
2

sgn(LR
p
(m))sgn(LR
p
(2m)) . . . sgn(LR
p
((p 1)m/2))
_
p 1
2
_
!(p).
Aplicando el Teorema 2.3, se tiene
m
p1
2
sgn(LR
p
(m))sgn(LR
p
(2m)) . . . sgn(LR
p
((p 1)m/2))(p).
Pero
m
p1
2

_
m
p
_
(p),
por el Teorema 6.5 y
(1)

= sgn(LR
p
(m))sgn(LR
p
(2m)) . . . sgn(LR
p
((p 1)m/2)).
De donde
_
m
p
_
(1)

(p)
ya que cada lado de esta congruencia es igual a 1 0 1, y siendo p > 2,
_
m
p
_
= (1)

(p).
Ahora se prueba el Teorema que tanto se estaba esperando!
Teorema 6.10 [Ley de Reciprocidad Cuadratica]: Si p y q son primos im-
pares distintos, entonces
_
p
q
_
=
_
q
p
_
excepto que p q 3(4), en dicho
caso
_
p
q
_
,=
_
q
p
_
Lic. Walter Otoniel 52
Demostracion: Sea
1
el n umero de enteros en el conjunto
_
q, 2q, . . . ,
p 1
2
q
_
con menor residuo modulo p negativo. Analogamente se
2
el n umero de
enteros en el conjunto
_
p, 2p, . . . ,
q 1
2
p
_
con menor residuo modulo q negativo. Por el Lema de Gauss, se tiene que
_
q
p
_
= (1)

1
y
_
p
q
_
= (1)

2
. Pero notese que
_
p
q
_
=
_
q
p
_
si y solo
s
_
p
q
__
q
p
_
= 1, as pues
_
p
q
_
=
_
q
p
_
si y solo s
(1)

1
+
2
= 1.
De lo anterior, para probar el Teorema, se debe mostrar que
1
+
2
es impar
si y solo s p q 3(4).
Se procedera geometricamente, as: Primero se contaran los puntos latices
(esto es, puntos cuyas coordenadas son enteros) dentro de cierto hexagono,
mostrando que existe un n umero impar de puntos latices en dicho hexagono si
y solo s p q 3(4). Segundo, se mostrara que existen
1
+
2
puntos latices
dentro del hexagono. As pues juntando estas dos cuentas, se mostrara que

1
+
2
es impar si y solo s p q 3(4).
Considerese el hexagono R en el primer cuadrante del plano XY con vertices
ABCDEF que esta en el rectangulo AGDJ acotado por los ejes coordenados
y las rectas x = p/2 y y = q/2, ver Figura 1.
EF se dene por
y =
q
p
x +
1
2
,
BC se dene por
x =
p
q
y +
1
2
.
Es claro que la recta BC intercepta al eje X en
_
1
2
, 0
_
, y EF intercepta al
eje Y en
_
0,
1
2
_
; es evidente que ambas rectas son paralelas a la diagonal
Lic. Walter Otoniel 53
Figura 1: Puntos Latices en la prueba del Teorema 6.7
AD.
Las coordenadas de los puntos
1
(x, y) que estan en el interior de R deben
satisfacer las siguientes desigualdes
0 < x < p/2, 0 < y < q/2, (17)
y <
q
p
x +
1
2
, y >
q
p
x
q
2p
. (18)
Ahora, notese que si (m, n) es cualquier punto latice en el interio de R,
entonces tambien
p + 1
2
m,
q + 1
2
n lo es. (esto se verica sustituyendo
cada coordenada en (17) y (18) ). Por otro lado, observese que
(m, n) =
p + 1
2
m,
q + 1
2
n
si y solo s m =
p + 1
4
y n =
q + 1
4
; de donde P :
_
p + 1
4
,
q + 1
4
_
es un punto
latice si y solo s p q 3(4). De aqu ya que a cada (m, n) en el interior de
R le corresponde
p + 1
2
m,
q + 1
2
n tambien en el interior de R, se tiene
1
Aqu (x, y) es un punto en el plano y no el mcd(x, y)
Lic. Walter Otoniel 54
que la unica manera para que el n umero de puntos latices se impar es que
p q 3(4)
Ahora se contaran los puntos latices de R de una manera diferente.
Es evidente que no hay puntos latices en la diagonal y =
q
p
x. Ahora si (m, n)
es un punto latice abajo de la diagonal entonces, no es difcil vericar que
qm
p

q
2p
< n <
qm
p
;
es decir

q
2
< np qm < 0. (19)
De donde se puede ver que np tiene un menor residuo modulo q negativo, a
saber np qm. Recprocamente, si np tiene un residuo menor negativo, se
puede encontrar un m, tal que (18) se cumple; de aqu (m, n) esta en R y
est a abajo de la diagonal. Por lo tanto, ya que
2
es el n umero de enteros
en el conjunto
_
p, 2p, . . . ,
q 1
2
p
_
con residuo menor modulo q negativo,
existen
2
puntos latices en R abajo de la diagonal AD.
De la misma manera, se prueba que existen
1
puntos latices arriba de la
diagonal principal.
As pues
1
+
2
(el total de puntos latices) es impar si y solo s p q 3(4).
Teorema 6.11 Si p es un primo impar, entonces
_
1
p
_
= (1)
p1
2
(20)
_
2
p
_
= (1)
p
2
1
8
(21)
Demostracion: Por el Lema de Gauss, con m = 1, se tiene que =
p 1
2
;
estableciendose (20).
Ahora con m = 2, es el n umero de enteros en el conjunto 2, 4, . . . , p 1
Lic. Walter Otoniel 55
cuyos menores residuos modulo p son negativos, el cual es el mismo que el
n umero de enteros en el intervalo
_
p + 1
2
, p 1
_
. De aqu,
=
_

_
2s cuando p = 8s + 1,
2s + 1 cuando p = 8s + 3,
2s + 1 cuando p = 8s + 5,
2s + 2 cuando p = 8s + 7.
De donde, es par si y solo s p 1(8). En consecuencia
_
2
p
_
=
_
1 cuando p 1(8),
1 cuando p 3(8).
ya que
(1)
p
2
1
8
=
_
1 cuando p 1(8),
1 cuando p 3(8).
estableciendose (21)
Teorema 6.12 Si p es primo impar y (a, p) = 1, entonces la congruencia
x
2
a(p
n
) (22)
tiene solucion si y solo s
_
2
p
_
= 1.
Ejercicios 6.1
1. Pruebe que si c es impar, entonces
_
ab
c
_
=
_
a
c
_
_
b
c
_
.
2. Pruebe que si b y c son impares, entonces
_
a
bc
_
=
_
a
b
__
a
c
_
.
3. Muestre que si a b(c), donde c es impar, entonces
_
a
c
_
=
_
b
c
_
.
4. Muestre que 17 es un rsiduo cuadratico modulo 19.
5. Tiene solucion la congruencia x
2
631(1093)? (sug. Use el smbolo
de Jacobi)
Lic. Walter Otoniel 56
6. Tiene solucion la congruencia x
2
17(29)?
7. Tiene solucion la congruencia 3x
2
12(23)?
8. Tiene solucion la congruencia 2x
2
27(41)?
9. Tiene solucion la congruencia x
2
+ 5x 12(31)? (sug. Complete
cuadrados)
10. Tiene solucion la congruencia x
2
19(30)? (sug. Use el teorema chino
del resto)