Teora Elemental de N umeros

Francisco Javier Garca Capitan

Problemas del libro Elementary Number Theory, de Underwood Dudley.

Indice
1. Enteros 2
2. Factorizaci on unica 6
3. Ecuaciones diofanticas lineales 9
4. Congruencias 14
5. Congruencias lineales 18
6. Los teoremas de Fermat y Wilson 27
7. Los divisores de un entero 33
8. N umeros perfectos 39
9. El teorema y la funcion de Euler 45
10.Races primitivas 50
11.Congruencias cuadraticas 56
12.Reciprocidad cuadratica 63
1. Enteros
1. Calcular (314,159) y (4144, 7696).
314 =1 159 + 155
159 =1 155 + 4
155 =38 4 + 3
4 =1 3 + 1
3 =3 1
(314, 159) = (159, 155) = (155, 4) = (4, 3) = (3, 1) = 1.
4144 =0 7696 + 4144
7696 =1 4144 + 3552
4144 =1 3552 + 592
3552 =6 592
(4144, 7696) = (7696, 4144) = (4144, 3552) = (3552, 592) = 592.
2. Calcular (3141,1592) y (10001, 1000083).
3141 =1 1592 + 1549
1592 =1 1549 + 43
1549 =36 43 + 1
43 =43 1
(3141, 1592) = (1592, 1549) = (1549, 43) = (43, 1) = 1.
100083 =10 10001 + 73
10001 =137 73
(100083, 10001) = (10001, 73) = 73.
3. Encontrar x e y tales que 314x + 159y = 1.
314 = 1 159 + 155 155 = 1 314 + (1) 159
159 = 1 155 + 4 4 = (1) 314 + 2 159
155 = 38 4 + 3 3 = 39 314 + (77) 159
4 = 1 3 + 1 1 = (40) 314 + 79 159
2
4. Encontrar x e y tales que 4144x + 7696y = 1.
7696 = 1 4144 + 3552 3552 = 1 7696 + (1) 4144
4144 = 1 3552 + 592 592 = (1) 7696 + 2 4144
5. Si N = abc + 1, demostrar que (N, a) = (N, b) = (N, c) = 1.
Si d es un divisor positivo de N y de a, entonces tambien lo sera de
N abc = 1, por lo que d = 1.
6. Encontrar dos soluciones diferentes de 299x + 247y = 13.
Simplicando por 13, la ecuacion es equivalente a 23x + 19y = 1. Los
primeros diez m ultiplos de 23 y 19 son:
23: 23, 46, 69, 92, 115, 138, 161, 184, 207, 230,
19: 19, 38, 57, 76, 95, 114, 133, 152, 171, 190.
Observando los n umeros 115 y 114 obtenemos que 23 5 +247 (6) =
1, de donde obtenemos x = 5, y = 6. Para encontrar otra solucion
hallamos otros diez m ultiplos de 23 y 19:
23: 253, 276, 299, 322, 345, 368, 391, 414, 437, 460
19: 209, 228, 247, 266, 285, 304, 323, 342, 361, 380
Vemos entonces que 23 14 = 322 y que 19 17 = 323. Por tanto, otra
solucion sera x = 14, y = 17.
7. Demostrar que si a|b y b|a entonces a = b o a = b.
Si a|b y b|a entonces existen enteros k y h tales que b = ka y a = hb.
Si uno de los n umeros a y b es cero, tambien lo es el otro, y entonces
tenemos a = b. En otro caso, como b = ka = khb, tendremos kh = 1,
de donde o k = h = 1 o k = h = 1 que llevan respectivamente a a = b
y a = b.
8. Demostrar que si a|b y a > 0, entonces (a, b) = a.
Que (a, b) = a equivale a decir que a|a, a|b y que si c|a y c|b, entonces
c a. Que a|a es evidente, que a|b es una de las hipotesis y, por
ultimo, de c|a deducimos que a = kc para alg un entero k, y como
a > 0, deducimos que c a.
3
9. Demostrar que si ((a, b), b) = (a, b).
Podemos usar el ejercicio anterior y tener en cuenta que (a, b)|b y
(a, b) > 0. Por tanto, ((a, b), b) = (a, b).
10. a) Demostrar que (n, n + 1) = 1 para todo n > 1.
b) Si n > 0, cuanto puede valer (n, n + 2)?
a) Sea d un divisor positivo de n y n+1. Entonces tambien lo sera de
(n + 1) n = 1, por lo que d = 1.
b) Sea d un divisor positivo de n y n+2. Entonces tambien lo sera de
(n + 2) n = 2, por lo que d = 1 o d = 2.
11. a) Demostrar que (k, n + k) = 1 si y solo si (k, n) = 1.
b) Es cierto que (k, n + k) = d si y solo si (k, n) = d?
a) Supongamos que (k, n + k) = 1 y sea d un divisor positivo de
n y k. Entonces podremos expresar k = du, n = dv y k + n =
du+dv = d(u+v), por lo que d es un divisor positivo de k y n+k
y debe ser 1. Recprocamente y de forma analoga, si suponemos
que (k, n) = 1 y d es un divisor positivo de k y n + k, tendremos
k = du, n + k = dv, por lo que n = (n + k) k = d(v u) y
obtenemos que d es un divisor positivo de k y n. Por ello, como
(k, n) = 1, debe ser d = 1 y tambien (k, n + l) = 1.
b) S, es cierto. Sean (k, n + k) = d y (k, n) = e. e es un divisor de
n y k. Entonces podremos expresar k = eu, n = ev y k + n =
eu +ev = e(u +v), por lo que e es un divisor de k y n +k y debe
ser e|d. De forma parecida, al ser d un divisor com un de k y n+k
podremos escribir k = du y n + k = dv lo que permite escribir
n = d(v u) siendo entonces d un divisor de k y n. Por tanto d|e.
Como d|e y e|d, y ambos son positivos, d = e.
12. Demostrar que si a|b y c|d, entonces ac|bd.
Expresemos b = ka y d = hc y tendremos bd = (ka)(hc) = (kh)(ac),
de donde ac|bd.
13. Demostrar que si d|a y d|b, entonces d
2
|ab.
Expresemos a = kd y b = hd y tendremos ab = (kd)(hd) = (kh)d
2
, de
donde d
2
|ab.
4
14. Demostrar que si c|ab y (c, a) = d, entonces c|db.
Como c|ab, existe un entero k tal que ab = kc y como (c, a) = d, existen
enteros x e y tales que cx+ay = d. Multiplicando esta ultima igualdad
por b, tenemos que db = bcx + aby = bcx + kcy = c(bx + ky), por lo
que c|db.
15. a) Demostrar que si x
2
+ ax + b = 0 tiene una raz entera, es
un divisor de b.
b) Demostrar que si x
2
+ ax + b = 0 tiene una raz racional,
es en realidad un n umero entero.
a) Sea m una raz entera de x
2
+ax+b = 0. Entonces b = m
2
am =
m(ma). Por tanto, m debe ser un divisor de b.
b) Sea
p
q
una raz racional irreducible de x
2
+ ax + b = 0. Entonces
p
2
q
2
+ b
p
q
+ c = 0 p
2
+ bpq + cq
2
= 0 p
2
= q(bp + cq).
Como la fraccion
p
q
es irreducible y q es un divisor de p
2
, tambien
lo es de p. En efecto, de p
2
= qh y px + qy = 1, podemos obtener
p
2
x + pqy = p y qhx + pqy = p, y entonces p = q(hx + qy). Por
tanto q = 1 y la fraccion
p
q
es un entero.
5
2. Factorizaci on unica
1. Desomponer factorialmente 1234, 34560 y 111111.
1234 = 2 617, 34560 = 2
8
3
3
5, 111111 = 3 7 11 13 37.
2. Descomponer factorialmente de 2345, 45670 y 999999999999.
(Observar que 101|1000001).
2345 = 5 7 67. 45670 = 2 5 4567.
999999999999 = 3
3
7 11 13 37 101 9901.
3. Tartaglia (1556) armaba que las sumas 1 +2 +4, 1 +2 +4 +8,
1 + 2 + 4 + 8 + 16, ... eran alternadamente n umeros primos y
compuestos. Demostrar que estaba equivocado.
Teniendo en cuenta que 1 +2 +4 + +2
n1
= 2
n
1, construimos la
tabla
n 3 4 5 6 7 8 9
2
n
1 7 15 31 63 127 255 511
Primo? SI NO SI NO SI NO NO
Vemos que a 511 = 7 73 le tocara ser primo y no lo es.
4. a) DeBouvelles (1509) armaba que para cada n 1 uno o
ambos de los n umeros 6n+1 y 6n1 son primos. Demostrar
que estaba equivocado.
b) Demostrar que hay innitos n umeros n tales que tanto
6n + 1 como 6n 1 son compuestos.
a) Si introducimos en Mathematica la instrucccion
Table[{PrimeQ[6*n+1], PrimeQ[6*n-1]}, {n,1,20}],
obtenemos que n = 20 es el primer valor para el que 6n + 1 =
121 = 11
2
y 6n 1 = 7 119 son ambos compuestos.
b) Sea n cualquier n umero de la forma n = 77k 57. Entonces:
6n + 1 = 462k 342 + 1 = 462k 341 = 11(42k 31)
6n 1 = 462k 342 1 = 462k 343 = 7(66k 49)
6
(La solucion a este apartado la encontre buscando los n umeros
compuestos de la forma 6n+1 y 6n1 divisibles por 11 uno y por
7 otro, y encontrando que se van diferenciando 77 unos de otros).
5. Demostrar que los exponentes en la descomposicion factorial
de un cuadrado perfecto son pares.
Si n = m
2
y m = p
e
1
1
p
e
2
2
p
er
r
, obtenemos que n = (p
e
1
1
p
e
2
2
p
er
r
)
2
=
p
2e
1
1
p
2e
2
2
p
2er
r
.
6. Demostrar que si los exponentes en la descomposicion fac-
torial de un n umero son pares, dicho n umero es cuadrado
perfecto.
Supongamos que n tiene una descomposicion factorial de la forma
n = p
2e
1
1
p
2e
2
2
p
2e
r
r
. Entonces n = (p
e
1
1
p
e
2
2
p
e
r
r
)
2
= m
2
, siendo m =
p
e
1
1
p
e
2
2
p
e
r
r
.
7. Encontrar el entero mas peque no divisible por 2 y 3 que es a
la vez un cuadrado y una quinta potencia.
Cualquier n umero de la forma n = 2
10k
3
10h
, con h, k 1 es divisible
por 2 y por 3, y es un cuadrado y una quinta potencia. Para k = 1 y
h = 1, resulta n = 6
10
= 60466176.
8. Si d|ab, se deduce que d|a o d|b?
No, pues, por ejemplo, 12|36, pero ni 12|9, ni 12|4.
9. Es posible que un primo p divida tanto a n como a n + 1
(n 1).
No pues tambien dividira a (n + 1) n = 1.
10. Demostrar que n(n + 1) nunca es un cuadrado para n > 0.
Sean m, n > 0 tales que n
2
+ n = m
2
. Resulta n = m
2
n
2
= (m +
n)(mn). Por tanto, m + n n m 0. Contradiccion.
11. a) Comprobar que 2
5
9
2
= 2592.
b) Es 2
5
a
b
= 25ab posible para otros a, b? (Aqu 25ab repre-
senta los dgitos de 2
5
a
b
, no un producto.)
a) 2
5
9
2
= 32 81 = 2592.
7
b) Escribiendo el la igualdad propuesta en la forma
a
b
=
2500 + ab
32
= 78,125 +
ab
32
,
y teniendo en cuenta que ab puede ser como mucho 98, llegamos
a 78 < a
b
78,125 +
98
32
= 78,125 + 3,0625 = 81,1875. Es decir,
a
b
solo puede ser 79, 80 u 81. Solo 81 es una potencia de un
n umero entero. Ademas, lo es de dos formas, 9
2
y 3
4
. La solucion
a = 3, b = 4 no es valida pues el valor de a
b
es unico y solo coincide
con la solucion a = 9, b = 2.
12. Sea p el factor primo menor de n, siendo n compuesto. De-
mostrar que si p > n
1/3
, entonces n/p es primo.
Razonamos por reduccion al absurdo. Supongamos que n/p no es primo.
Entonces existe un primo q que divide propiamente a n/p, es decir
cumple que pq < n. El n umero n/pq o es un primo r o es divisible
por un primo r que tambien divide a n. En cualquier caso, tenemos
pqr n, en contradicci on con que, al ser p el menor de los primos que
dividen a n, pqr p
3
> n.
13. Verdadero o falso? Si p y q dividen a n, y ambos son mayores
que n
1/4
, entonces n/pq es primo.
Consideramos p = 5 y q = 7 y n = 6pq = 210. Tanto p como q son
mayores que n
1/4
, y sin embargo n/pq = 6 no es primo.
14. Demostrar que si n es compuesto, entonces 2
n
1 es compuesto.
Supongamos que n = pq. Sustituyendo b = 2
p
y a = 1 en la formula
b
q
a
q
= (b a)(b
q1
+ ab
q2
+ + a
q2
b + a
q1
)
obtenemos
2
n
1 = (2
p
1)(2
p(q1)
+ 2
p(q2)
+ + 2
p
+ 1),
por lo que 2
n
1 es compuesto.
15. Es cierto que si 2
n
1 es compuesto, entonces n es compuesto?
No es cierto, puesto que 2
11
1 = 2047 = 23 89 es compuesto, mientras
que 11 es primo.
8
3. Ecuaciones diofanticas lineales
1. Encontrar todas las soluciones enteras de x+y = 2, 3x4y = 5
y 15x + 16y = 17.
Es facil encontrar una solucion de cada una de las ecuaciones:
x = 1, y = 1, para la primera, x = 3, y = 1 para la segunda y x =
17, y = 17 para la tercera. Entonces, las soluciones de estas ecuaciones
vendran dadas por las formulas:
_
x = 1 + t
y = 1 t
,
_
x = 3 4t
y = 1 3t
,
_
x = 17 + 16t
y = 17 15t
.
2. Encontrar todas las soluciones enteras de 2x+y = 2, 3x4y = 0
y 15x + 18y = 17.
La ultima ecuacion no tiene ninguna solucion, pues (15, 18) = 3 no es
un divisor de 17. Una solucion de la primera es x = 1, y = 0 y una
solucion de la segunda es x = 0, y = 0. Entonces, las soluciones de
estas ecuaciones son:
_
x = 1 + t
y = 2t
,
_
x = 4t
y = 3t
.
3. Encontrar todas las soluciones enteras positivas de x + y = 2,
3x 4y = 5 y 6x + 15y = 51.
Las soluciones enteras de x+y = 2 son de la forma x = 1t, y = 1+t.
Para que x e y sean positivos, t debe cumplir las desigualdades t < 1
y t > 1. Solo puede ser t = 0 y entonces la unica solucion positiva de
esta ecuacion es x = 1, y = 1.
Las soluciones enteras de 3x 4y = 5 son de la forma x = 3 4t, y =
1 3t. Para que x e y sean positivos, t debe cumplir las desigualdades
t <
4
3
y t <
1
3
, que se cumplen ambas si y solo si t 0. Por tanto las
soluciones enteras positivas de 3x 4y = 5 las podemos expresar as:
_
x = 3 + 4t
y = 1 + 3t
, (t 0).
9
Las soluciones enteras de 6x + 15y = 51 son las mismas que las de
2x +5y = 17 y una de ellas es x = 1, y = 3. Las demas son de la forma
_
x = 1 + 5t
y = 3 3t
.
Para que x e y sean positivos es necesario que t 0 y t < 1, es decir, el
unico valor de t posible es t = 0 y la unica solucion positiva es x = 1,
y = 3.
4. Encontrar todas las soluciones positivos de 2x+y = 2, 3x4y = 0
y 7x + 15y = 51.
Empezamos por hallar las soluciones enteras de estas ecuaciones:
_
x = t
y = 2 2t
,
_
x = 4t
y = 3t
,
_
x = 102 + 15t
y = 51 7t
.
Ahora es facil encontrar los valores de t que hacen que x e y sean
positivos. En el primer caso no hay ning un valor de t. En el segundo caso
es valido cualquier t 1. En la tercera ecuacion, debe ser
102
15
< t <
51
7
o 6,8 < t < 7
2
7
, es decir debe ser t = 7, que da lugar a x = 3, y = 2
como unica solucion positiva.
5. Encontrar todas las soluciones positivas de
_
x + y + z = 31
x + 2y + 3z = 41
Restando las dos ecuaciones, obtenemos y + 2z = 10, cuyas soluciones
son de la forma
_
y = 2t
z = 5 t
,
que nos lleva a x = 31 2t (5 t) = 26 t. Para que x, y, z sean
positivos, debe ser t > 0, t < 54 y t < 26, es decir t = 1, 2, 3, 4 que dan
lugar a las soluciones
t 1 2 3 4
x 25 24 23 22
y 2 4 6 8
z 4 3 2 1
10
6. Encuentra las cinco formas diferentes de sumar $4.99 con 100
monedas de 1, 10 y 25 centavos.
Planteamos el problema con el sistema
_
x + y + z = 100
x + 10y + 25z = 499
.
Restando las dos ecuaciones obtenemos 9y + 24z = 399, y dividiendo
por 3, 3y + 8z = 133. Para resolver esta ecuacion, despejamos:
y =
133 8z
3
= 44 2z +
1 2z
3
= 44 2z + p,
cumpliendo p que 3p + 2z = 1, y de nuevo despejando,
z =
1 3p
2
=
1 p
2
p = q p,
donde 1 p = 2q, y por tanto, p = 1 2q. Ahora, vamos sustituyendo
y obteniendo z = q p = q (1 2q) = 3q q, y = 44 2z + p =
44 2(3q 1) + (1 2q) = 47 8q, x = 100 y z = 100 (47
8q) (3q 1) = 54 +5q. Como x, y, z deben ser no negativos, q 1 y
q 5, que da lugar a los siguientes valores de x, y, z:
q 1 2 3 4 5
x 59 64 69 74 79
y 39 31 23 15 7
z 2 5 8 11 14
7. Un hombre compro doce piezas de fruta (manzanas y na-
ranjas) por 99 centavos. Si una manzana cuesta 3 centimos
mas que una naranja, y compro mas manzanas que naranjas,
cuantas de cada compro?
Llamamos x, y al n umero de manzanas y peras, respectivamente, y p
al precio de una naranja. Entonces
_
x + y = 12
(p + 3)x + py = 99

_
x + y = 12
3x + p(x + y) = 99

3x + 12p = 99
x + 3p = 33
x = 33 3p
.
11
Sustituyendo, y = 12x = 12(334p) = 4p21. Como compro mas
manzanas que naranjas, 33 4p > 4p 21 54 > 8p p 6. Por
otro lado, x e y deben ser positivos, por lo que 4p 21 0 p 6.
Solo puede ser p = 6, que da x = 9 manzanas e y = 3 naranjas.
8. 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?
Llamando x, y, z al n umero de alumnos de segundo, tercer y cuarto
curso, respectivamente, planteamos el sistema
_
x + y + z = 26
125x + 90y + 50z = 2500

_
x + y + z = 26
25x + 18y + 10z = 500
.
Multiplicando por 10 la primera ecuacion y restandosela a la segunda
obtenemos 15x + 8y = 240. Teniendo en cuenta que 8 15 = 120,
hallamos que x = 8, y = 15 es una solucion entera de esta ultima
ecuacion, por lo que todas las otras seran de la forma
_
x = 8 + 8t
y = 15 15t
,
, y entonces z = 26 x y = 26 (8 + 8t) (15 15t) = 3 + 7t.
Evidentemente, la unica solucion positiva se obtiene para t = 0: 8
alumnos de segundo curso, 15 de tercero y 3 de cuarto.
9. El siguiente problema aparecio por primera vez en un libro
indio escrito sobre el a no 850. Tres mercaderes encontraron
una bolsa en el camino. Uno de ellos dijo: Si yo consigo esta
bolsa, sere el doble de rico que vosotros dos juntos. Entonces
el segundo dijo: Yo sere el doble de rico que vosotros juntos.
El tercer hombre dijo: Yo sere tan rico como cinco veces
vosotros dos juntos. Cuanto tena cada mercader y cuanto
haba en la bolsa?
Sean x, y, z la cantidad poseda por los tres mercaderes y b la cantidad
12
que contiene la bolsa. Entonces:
_

_
x + b = 2(y + z)
y + b = 3(x + z)
z + b = 5(x + y)

_
x = 2y + 2z b
y + b = 3x + 3z
z + b = 5x + 5y

_
y + b = 6y + 9z 3b
z + b = 15y + 10z 5b
_
5y + 9z = 4b
15y + 9z = 6b
10y = 2b y =
b
5
9z = 3b z =
b
3
.
Finalmente, x =
_
2
5
+
2
3
1
_
b =
b
15
.
10. 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?
Planteemos la ecuacion (100c + d) 23 = 200d + 2c y obtendremos
98c 199d = 23. Usemos el algoritmo de Euclides para encontrar una
solucion de esta ecuacion:
199 = 2 98 + 3 3 = (2) 98 + 1 199
98 = 32 3 + 2 2 = 65 98 + (32) 199
3 = 1 2 + 1 1 = (67) 98 + 33 199
Entonces c = 67, d = 33 es una solucion de 98c 199d = 1 y,
multiplicando por 23, c = 1541, d = 759 es una solucion de 98c
199d = 23. Las demas soluciones seran de la forma
_
c = 1541 + 199t
d = 759 + 98t
.
Para t 8 es cuando se obtienen valores positivos de c y d: Para t = 8,
c = 51, d = 25. Para valores mayores de t, c sera mayor que 100,
que es imposible. Por tanto, el valor del cheque era de 25 dolares y 51
centavos.
13
4. Congruencias
1. Encontrar el resto de 1492 (mod 4), (mod 10) y (mod 101).
Dividiendo 1492 por 4, 10 y 101 obtenemos de resto 0, 2 y 78 respecti-
vamente. Entonces:
1492 0 ( mod 4), 1492 2 ( mod 10) y 1492 78 ( mod 101).
2. Encontrar el resto de 1789 (mod 4), (mod 10) y (mod 101).
Dividiendo 1789 por 4, 10 y 101 obtenemos de resto 1, 9 y 72, respec-
tivamente. Entonces:
1789 1 ( mod 4), 1789 9 ( mod 10) y 1789 72 ( mod 101).
3. Es cierto que a b (mod m), implica que a
2
b
2
(mod m).
Es cierto, pues si a b (mod m), m es un divisor de a b, por lo que
tambien lo sera de (a b)(a + b) = a
2
b
2
.
4. Es cierto que a
2
b
2
(mod m), implica que a b (mod m).
En principio, todo divisor de a
2
b
2
no tiene por que serlo de a b.
Por ejemplo, para a = 7 y b = 5, a
2
b
2
= 49 24 = 24. Basta tomar
m = 3, para tener 49 25 1 (mod 3) y sin embargo, 7 1 (mod 3)
y 5 2 (mod 3)
5. Encontrar todos los m tales que 1066 1776 (mod m).
m debera ser un divisor de 710 = 1776 1066. Como 710 = 2 5 71,
los divisores de 710 son 1, 2, 5, 10, 71, 142, 355 y 710.
6. Encontrar todos los m tales que 1848 1914 (mod m).
m debera ser un divisor de 66 = 1914 1848. Como 66 = 2 3 11, los
divisores de 66 son 1, 2, 3, 6, 11, 22, 33, 66.
7. Si k 1 (mod 4), con quien es congruente 6k + 5 (mod 4)?
Si escribimos k = 1 + 4m, 6k + 5 = (6 + 24m) + 5 = 24m + 11
3 (mod m).
8. Demostrar que todos los primos (excepto el 2) es congruente
con 1 o 3 modulo 4.
Los restos modulo 4 son 0, 1, 2, 3. Aquellos n umeros que dan resto
modulo 0 o 2 son pares, y no pueden ser primos.
14
9. Demostrar que todos los primos (excepto el 2 y el 3) son
congruentes con 1 o 5 modulo 6.
Los restos modulo 6 son 0, 1, 2, 3, 4, 5. Aquellos n umeros que dan
resto modulo 0, 2 o 4 son pares, y no pueden ser primos y los dan resto
modulo 3, son de la forma 6k + 3 = 3(2k + 1), es decir, son divisibles
por 3, y tampoco pueden ser primos.
10. Con que pueden ser congruentes modulo 30 los primos dis-
tintos de 2, 3 o 5?
Quitaremos de los n umeros, {0,1,...,29}, los pares mayores que 2, los
m ultiplos de 3 mayores que 3, los m ultiplos de 5 mayores que 5, etc.
Quedaran 1,7,11,13,17,19,23,29.
11. En la multiplicaci on 31415992653 = 2910 93995, se ha perdido un
dgito del producto y todos los demas son correctos. Encontrar
el dgito perdido sin efectuar la multiplicacion.
Usamos la prueba del nueve, basada en las congruencias modulo 9.
Al sumar las cifras de 314159 y 92653 obtenemos 5 y 7 modulo 9,
respectivamente. La suma de cifras del producto debe ser congruente
con 35 modulo 9, es decir 8 modulo 9. Como la suma de cifras del
producto es 2 modulo 9, la cifra que falta es un 6.
12. Demostrar que ning un cuadrado tiene como ultimo dgito 2,
3, 7 u 8.
Basta hacer congruencias modulo 10, o lo que es lo mismo jarse en u,
la cifra de las unidades cuando elevamos al cuadrado los n umeros n del
0 al 9.
n 0 1 2 3 4 5 6 7 8 9
u 0 1 4 9 6 5 6 9 4 1
13. Cual puede ser el ultimo dgito de una cuarta potencia.
De forma parecida al ejercicio anterior, nos podemos jar en u, la cifras
de las unidades cuando elevamos al cuadrado uno de los n umeros n =
0, 1, 4, 5, 6, 9:
n 0 1 4 5 6 9
u 0 1 6 4 6 1
15
Por tanto, el ultimo dgito de una cuarta potencia puede ser 0, 1, 4 o
6.
14. Demostrar que la diferencia de dos cubos consecutivos nunca
es divisible por 3.
Basta tener en cuenta que (n + 1)
3
n
3
= 3n
2
+ 3n
2
+ 1 da de resto 1
modulo 3.
15. Demostrar que la diferencia de dos cubos consecutivos nunca
es divisible por 5.
Dando a la expresion 3n
2
+ 3n + 1 los valores 0, 1, 2, 3, 4 obtenemos,
respectivamente, 1, 7, 19, 37, 61, y ninguno de estos n umeros es divisible
por 5.
16. Demostrar que
d
k
10
k
+ d
k1
10
k1
+ + d
1
10 + d
0
d
0
d
1
+ d
2
d
3
+ + (1)
k
d
k
(mod 11)
y deducir un criterio de divisibilidad por 11.
Para demostrar esta formula es suciente comprobar que si n es par
entonces 10
n
(1)
n+1
(mod 11) y ello se deduce facilmente por in-
duccion de que 10
1
1 (mod 11) y que 10
2
1 (mod 11) y por
tanto,
d
k
10
k
+ d
k1
10
k1
+ + d
1
10 + d
0
d
0
+ d
1
(1) + d
2
+ d
3
(1) + + (1)
k
d
k
(mod 11)
d
0
d
1
+ d
2
d
3
+ + (1)
k
d
k
(mod 11)
17. A dice que 27,182,818,284,590,452 es divisible por 11. B dice
que no. Quien lleva razon?
Usando el criterio encontrado en el ejercicio anterior, cuando un n u-
mero sea divisible por 11, tambien lo sera la diferencia de las sumas
de los dgitos que ocupan posiciones impares y pares del n umero. En
nuestro caso, los dgitos que ocupan posiciones impares suman 2 +1 +
2 + 1 + 2 + 4 + 9 + 4 + 2 = 27 y los que ocupan posiciones impares,
7 + 8 + 8 + 8 + 5 + 0 + 5 = 49. La diferencia es 49 27 = 22, que es
divisible por 11. Por tanto, A tiene razon.
16
18. Un palndromo es un n umero que se lee igual hacia delante y
hacia detras. Por ejemplo, 22, 1331 y 935686539 son palndro-
mos.
a) Demostrar que todo palndromo de 4 dgitos es divisible
por 11.
b) Que ocurre con los palndromos de seis dgitos?
a) Aplicamos el criterio visto en el ejercicio 16. Si N = abba,
sera a b + b a = 0 por lo que N es divisible por 11.
b) Si N = abccba, N es congruente modulo 11 con a b + c
c + b a = 0, por lo que tambien sera divisible por 11.
19. Demostrar que si n 4 (mod 9), entonces n no puede escri-
birse como suma de tres cubos.
Ponemos en una tabla los valores de k, k
2
y k
3
modulo 9, dando a n
los valores de los restos modulo 9:
k 0 1 2 3 4 5 6 7 8
k
2
0 1 4 0 7 7 0 4 1
k
3
0 1 8 0 1 8 0 1 8
Vemos que los valores posibles de k
3
son 0, 1 y 8. Al sumar tres n umeros
que sean 0, 1 u 8, modulo 9, los resultados posibles son 0 + 0 + 0 = 0,
0 +0 +1 = 1, 0 +0 +8 = 8, 0 +1 +1 = 2, 0 +1 +8 = 0, 0 +8 +8 = 7,
1 + 1 + 1 = 3, 1 + 1 + 8 = 1, 1 + 8 + 8 = 8 y 8 + 8 + 8 = 6, as que nos
posible obtener un n umero que sea congruente con 4 modulo 9 como
suma de tres cubos. (Tampoco uno que sea congruente con 5 modulo
9).
20. Demostrar que para cualquiera k > 0 y m 1, x 1 (mod m
k
)
implica que x
m
1 (mod m
k+1
).
Que x 1 (mod m
k
) signica que x = 1 + ym
k
siendo y un n umero
entero. Usamos la formula del binomio:
x
m
= (1 + ym
k
)
m
= 1 +
_
m
1
_
ym
k
+
_
m
2
_
(ym
k
)
2
+ + (y
m
k)
m
Como todos los sumandos, excepto el primero son divisibles por m
k+1
,
resulta que x
m
1 (mod m
k+1
).
17
5. Congruencias lineales
1. Resolver las siguientes congruencias:
2x 1 (mod 17) 3x 1 (mod 17)
3x 6 (mod 18) 40x 777 (mod 1777)
2x 1 (mod 17) 2x 18 (mod 17) x 9 (mod 17).
3x 1 (mod 17) 3x 18 (mod 17) x 6 (mod 17).
3x 6 (mod 18) x 2 (mod 6) x 2, 8, 14 (mod 18).
40x 777 (mod 1777) 40x 1000 (mod 1777)
x 25 (mod 1777) x 1752 (mod 1777).
2. Resolver las siguientes congruencias:
2x 1 (mod 19) 3x 1 (mod 19)
4x 6 (mod 18) 20x 984 (mod 1984)
2x 1 (mod 19) 2x 20 (mod 19) x 10 (mod 19).
3x 1 (mod 19) 3x 39 (mod 19) x 13 (mod 19).
4x 6 (mod 18) 4x 24 (mod 18)
x 6 (mod 9) x 6, 15 (mod 18).
20x 984 (mod 1984) 20x 1000 (mod 1984)
x 50 (mod 496) x 446 (mod 496)
x 446, 992 (mod 1984).
3. Resolver los sistemas
a) x 1 (mod 2), x 1 (mod 3).
b) x 3 (mod 5), x 5 (mod 7), x 7 (mod 11).
c) 2x 1 (mod 5), 3x 2 (mod 7), 4x 3 (mod 11).
a) Si x es una solucion de x 1 (mod 2), sera de la forma x = 2k+1.
Imponiendo que x 1 (mod 3), llegamos a 2k + 1 1 (mod 3)
o k 0 (mod 3), por lo que k = 3h para alg un entero h y x =
2(3h) + 1 = 6h + 1, es decir, x 1 (mod 6).
18
b) Si x 3 (mod 5), x es de la forma x = 5k + 3 para alg un entero
k. Imponemos que x 5 (mod 7): 5k + 3 5 (mod 7) 5k
2 (mod 7) 5k 30 (mod 7) k 6 (mod 7) k = 7h + 6
para alg un entero h. Entonces x = 35h + 33 para alg un ente-
ro h. Ahora sometemos x a la congruencia x 7 (mod 11) y
obtenemos 35h + 33 7 (mod 11) 35h 7 (mod 11)
5h 1 (mod 11) 5h 45 (mod 11) h 9 (mod 11).
Entonces h = 11m + 9 para alg un entero m, y nalmente x =
35(11m + 9) + 33 = 385m + 348 para alg un entero m, es decir
x 348 (mod 385).
c) En primer lugar, 2x 1 (mod 5) 2x 6 (mod 5) x
3 (mod 5), As que x es de la forma 5k +3. Sustituyendo en 3x
2 (mod 7), 15k + 9 2 (mod 7) k 0 (mod 7). Entonces k es
de la forma 7h y x es de la forma 35h+3, que llevado a la ecuacion
4x 3 (mod 11) la convierte en 140h + 12 3 (mod 11) 8h
2 (mod 11) 4h 1 (mod 11) h 3 (mod 11), luego h es
de la forma 11m + 3 y x es de la forma 385h + 108, es decir
x 108 (mod 385).
4. Resolver los sistemas
a) x 1 (mod 2), x 2 (mod 3)
b) x 2 (mod 5), 2x 3 (mod 7), 3x 4 (mod 11)
c) x 31 (mod 41), x 59 (mod 26)
a) Ponemos x = 2k + 1 y sustituimos en x 2 (mod 3), obteniendo
2k + 1 2 (mod 3) 2k 1 (mod 3) k 2 (mod 3) x =
2(3h + 2) + 1 = 6h + 5 x 5 (mod 6).
b) x es de la forma 5k + 2 y como
2x 3 (mod 7) x 5 (mod 7)
3x 4 (mod 11) x 5 (mod 11)
_
x 5 (mod 77),
5k + 2 5 (mod 77) 5k 3 (mod 77) k 16 (mod 77).
Entonces, x = 5(77h + 16) + 2 = 385h + 82 y, por tanto, x
82 (mod 385).
19
c) Escribiendo x = 41k + 31 y sustituyendo en x 7 (mod 26),
obtenemos 41k + 31 7 (mod 26) 41k 2 (mod 26). Usando
el algoritmo de Euclides encontramos que 7 41 11 26 = 1 y
por tanto que 14 41 22 26 = 2, lo que nos permite armar que
41k 2 (mod 26) 41k 2 + 22 26 = 574 (mod 26) k
14 (mod 26). Entonces, x = 41(26h + 14) + 31 = 1066h + 605
x = 605 (mod 1066).
5. Que posibilidades hay para el n umero de soluciones de una
congruencia lineal modulo 20?
Como 20 = 2
2
5, los divisores de 20 son 1, 2, 4, 5, 10 y 20. La con-
gruencia ax b (mod 20) puede tener, entonces, 1, 2, 4, 5, 10 o 20
soluciones pues ese puede ser el maximo com un divisor de a y 20.
6. Construir congruencias lineales modulo 20 con ninguna solu-
cion, con exactamente una solucion y con mas de una solucion.
Se puede encontrar una con 20 soluciones?
Para encontrar una congruencia que no tenga solucion tomamos, por
ejemplo a = 6, de manera que (a, 20) = 2, y ahora elegimos b de
manera que 2 b, por ejemplo b = 7. Entonces la congruencia sera
6x 7 (mod 20).
Para encontrar una congruencia con exactamente una solucion, bus-
camos un a tal que (a, 20) = 1 y cualquier b. Por ejemplo, 3x
1 (mod 20), cuya unica solucion es x = 7.
Para encontrar una congruencia con 4 soluciones, elegimos a tal que
(a, 20) = 4, por ejemplo a = 8, y b un m ultiplo de 4, por ejemplo b = 4.
As obtenemos 8x 4 (mod 20), que es equivalente a 2x 1 (mod 5)
o x 3 (mod 5), que dan lugar a las soluciones 3, 8, 13 y 18 de la
congruencia 8x 4 (mod 20).
S hay congruencias modulo 20 que tienen 20 soluciones, por ejemplo
20x 0 (mod 20).
7. Resolver 9x 4 (mod 1453).
Si x es solucion de esta congruencia, existe un entero y tal que 9x
1453y = 4. Usando el algoritmo de Euclides encontramos que 9 339
1453 2 = 1, y por tanto que 9 1292 1453 8 = 4. Entonces 9x
4 (mod 1453) x 1292 (mod 1453).
20
8. Resolver 4x 9 (mod 1453).
Si x es solucion de esta congruencia, existe un entero y tal que 4x
1453y = 9. Con el algoritmo de Euclides encontramos que 4 (363) +
1453 1 = 1, y por tanto que 4 (3267) + 1453 9 = 9. Entonces la
congruencia propuesta es equivalente a x 3267 3 1453 3267 =
1092 (mod 1453).
9. Resolver en x e y:
a) x + 2y 3 (mod 7), 3x + y 2 (mod 7).
b) x + 2y 3 (mod 6), 3x + y 2 (mod 6).
a) Usamos el metodo de sustitucion, reduciendo modulo 7:
x = 3 2y 9 6y + y = 2 5y = 0 y = 0 x = 3.
b) Ahora modulo 6: y = 2 3x x+4 6x = 3 5x = 1 x = 5
y = 2 15 = 13 = 5.
10. Resolver en x e y:
a) x + 2y 3 (mod 9), 3x + y 2 (mod 9).
b) x + 2y 3 (mod 10), 3x + y 2 (mod 10).
a) Usamos el metodo de sustitucion, reduciendo modulo 9:
x = 3 2y 9 6y + y = 2 5y = 2 4y = 2 2y = 1
y = 5 x = 7 = 2.
b) Ahora modulo 10: y = 23x x+46x = 3 5x = 1. En este
caso, la congruencia no tiene solucion, pues (a, m) = (5, 10) = 5
no divide a b = 1.
11. Cuando los participantes en el Desle del Departamento de
Matematicas se alinearon de 4 en 4, sobraba una persona;
cuando lo intentaron de 5 en 5, sobraban dos personas y cuan-
do iban de 7 en 7, sobraban 3. Como de grande es el Depar-
tamento?
Se trata de resolver el sistema
x 1 (mod 4), x 2 (mod 5), x 3 (mod 7),
21
Si x = 4k + 1, entonces 4k + 1 2 (mod 5) 4k 1 (mod 5) k
4 (mod 5) k = 5h + 4 x = 20h + 17 20h + 17 3 (mod 7)
6h 0 (mod 7) h 0 (mod 7) h = 7m x = 140m + 17.
El n umero de miembros del Departamento puede ser 17, 157, etc.
12. Encontrar un m ultiplo de 7 que deje resto 1 cuando se divide
por 2, 3, 4, 5 o 6.
Si N da resto 1 al dividir por 2, 3, 4, 5 o 6, N 1 es un m ultiplo de
2 3 4 5 6 = 720. Entonces buscamos una solucion de la ecuacion
7n 1 = 720k. Usando el algoritmo de Euclides encontramos que 7
103 720 1 = 1, por lo que n = 103 nos da la solucion N = 721.
13. Encontrar el menor impar n, n > 3 tal que 3|n, 5|n+2 y 7|n+4.
Buscamos un n > 3 tal que 2|n3, 3|n3, 5|n3 y 7|n3, por tanto
n 3 es un m ultiplo de 2 3 5 7 = 210. El menor n umero n > 3 es
210 + 3 = 213.
14. Encontrar el menor entero n, n > 2 tal que 2|n, 3|n +1, 4|n +2,
5|n + 3 y 6|n + 4.
Buscamos un n > 2 tal que 2|n 2, 3|n 2, 4|n 2, 5|n 2 y 6|n 2.
Por tanto, 60 divide a n 2. El menor valor posible de n es, entonces,
n = 60 + 2 = 62.
15. Encontrar un entero positivo tal que su mitad es un cuadrado,
su tercera parte es un cubo y su quinta parte es una quinta
potencia.
Escribimos el n umero en la forma N = 2
a
3
b
5
c
, con lo que
N
2
= 2
a1
3
b
5
c
,
N
3
= 2
a
3
b1
5
c
y
N
5
= 2
a
3
b
5
c1
.
Como
N
2
es un cuadrado y
N
3
es un cubo, c debe ser un m ultiplo de 6,
y como
N
5
es una quinta potencia, c 1 debe ser m ultiplo de 5. c = 6
cumple estas dos condiciones.
Analogamente, Como
N
2
es un cuadrado y
N
5
es una quinta potencia,
b debe ser un m ultiplo de 10, y como
N
3
es un cubo, c 1 debe ser
m ultiplo de 3. b = 10 cumple estas dos condiciones.
Analogamente, Como
N
3
es un cubo y
N
5
es una quinta potencia, a debe
ser un m ultiplo de 15, y como
N
2
es un cuadrado, a 1 debe ser par.
a = 15 cumple estas dos condiciones.
22
Por tanto, una solucion es N = 2
15
3
10
5
6
= 30, 233, 088, 000, 000.
16. Cada uno de los n umeros consecutivos 48, 49 y 50 tiene un
factor cuadrado.
a) Encontrar n tal que 3
2
|n, 4
2
|n + 1 y 5
2
|n + 2.
b) Puede encontrarse un n tal que 2
2
|n, 3
2
|n + 1 y 4
2
|n + 2?.
a) Buscamos un n tal que 9|n, 16|n + 1 y 25|n + 2, o lo que es lo
mismo, una solucion del sistema
n 0 (mod 9), n 1 (mod 16), n 2 (mod 25).
Escribiendo n = 9k 1 (mod 16), llegamos a 9k 63 (mod 16)
o k 7 (mod 16). Entonces k = 16h + 7 y n = 144h + 63 para
alg un h.
Ahora 144h + 63 2 (mod 25) 19h 10 (mod 25)
b) Si 4|n y 16|n + 2, sera n 0 (mod 4), n 2 (mod 16), y
entonces para alg un k tendramos 4k 2 (mod 16), que es im-
posible, pues (4, 16) = 4 no divide a 2.
17. Si x r (mod m) y x s (mod m + 1), demostrar que
x r(m + 1) sm (mod m(m + 1)).
Expresemos x = km + r y x = h(m + 1) + s. Entonces
r(m + 1) sm = (x km)(m + 1) (x h(m + 1))m =
= (m + 1)x km(m + 1) mx + hm(m + 1) =
= x + (h k)m(m + 1).
18. Que enteros positivos, despues de ser multiplicados por 3, 5 y
7 respectivamente y los productos divididos por 20, dan restos
en progresion aritmetica con diferencia com un 1 y cocientes
iguales a los restos?
Llamando a, b, c a los tres n umeros, el problema queda planteado as:
_

_
3a = 20q + q
5b = 20(q + 1) + (q + 1)
7c = 20(q + 2) + (q + 2)

_
3a = 21q
5b = 21(q + 1)
7c = 21(q + 2)

_
5b 3a = 21
7c 3a = 42
.
23
Resolviendo la primera de las ecuaciones obtenemos
_
a = 53 + 5t
b = 42 + 3t
,
Siendo a m ultiplo de 7, tambien debe serlo t, pongamos t = 7s, y
entonces a = 63 + 35s = 7(9 + 5s), es decir q = 9 + 5s.
Para s = 0, obtenemos q = 9 y
a = 63, 3a = 189 = 20 9 + 9
b = 42, 5b = 210 = 20 10 + 10
c = 33, 7c = 231 = 20 11 + 11
Para s = 1, obtenemos q = 14 y
a = 98, 3a = 294 = 20 14 + 14
b = 63, 5b = 315 = 20 15 + 15
c = 48, 7c = 336 = 20 16 + 16.
19. Supongamos que los modulos del sistema
x = a
i
(mod m
i
) i = 1, 2, , k
no son primos relativos dos a a dos. Encontrar una condicion
que deban cumplir los a
i
para que el sistema tenga solucion.
La condicion (m
i
, m
j
)|(a
i
a
j
) para todo i, j es necesaria y suciente
para que el sistema tenga solucion.
En efecto, supongamos que el sistema tiene solucion. Entonces existe
un x
0
tal que m
i
|(x
0
x
i
) i = 1, 2, , k. Si 1 i, j k, como
(m
i
, m
j
) es un divisor de m
i
y de m
j
, tambien lo sera de x
0
x
i
y de
x
0
x
j
y, por tanto, de su diferencia x
i
x
j
.
Para demostrar el recproco, vamos a tener en cuenta que cada con-
gruencia x = a (mod m) puede descomponerse en un sistema de con-
gruencias primarias x = a (mod p
e
i
i
) (llamadas as porque sus modulos
son potencias de primos) , siendo p
e
1
1
p
e
r
r
la descomposicion canonica
de m en factores primos.
Supongamos, entonces, que se cumple que (m
i
, m
j
)|(a
i
a
j
) para todo
i, j. Si se cumple que (m
i
, m
j
) = 1 para todos los i = j, entonces
24
sabemos que el sistema tiene solucion por el teorema chino del resto.
Si no es as, una vez que descomponemos cada congruencia del sistema
en un sistema de congruencias primarias, nos encontraremos con pares
de congruencias del tipo
_
x = a
i
(mod p
s
)
x = a
j
(mod p
t
)
,
En este sistema de congruencias, si s t, p
s
es un divisor de p
t
y si
x es una solucion de la segunda congruencia, tambien lo va a ser de
la primera pues p
t
|(x a
j
) p
s
|(x a
j
) p
s
|(x a
i
), cumpliendose
la ultima implicacion por la hipotesis (m
i
, m
j
)|(a
i
a
j
). Esto nos di-
ce que son superuas las congruencias cuyos modulos sean potencias
inferiores, por lo que pueden eliminarse. Al nal, nos va a quedar un
sistema de congruencias primarias en las formadas por las potencias
con mayor exponente, que son las que se usan para construir el mnimo
com un m ultiplo. Estas potencias de mayor exponente no tienen facto-
res comunes, por lo que el teorema chino del resto nos garantiza una
solucion del sistema.
Por ejemplo, resolvamos el sistema de congruencias
_
_
_
x 5 (mod 6)
x 2 (mod 15)
x 7 (mod 20)
En ese caso, (6, 15) = 3 divide a 5 2, (6, 20) = 2 divide a 5 7, y
(15, 20) = 5 divide a 2 7 = 5, por lo que el sistema tiene solucion.
Ahora, transformamos el sistema en uno de congruencias primarias:
_

_
x 5 (mod 2)
x 5 (mod 3)
x 2 (mod 3)
x 2 (mod 5)
x 7 (mod 4)
x 7 (mod 5)
La primera es superua porque el modulo de la pen ultima tiene mayor
exponente. La segunda es equivalente a la tercera. La ultima es equi-
valente a la cuarta. Por tanto, eliminando las congruencias superuas
25
nos queda:
_
_
_
x 2 (mod 3)
x 2 (mod 5)
x 7 (mod 4)

_
_
_
x 2 (mod 3)
x 2 (mod 5)
x 3 (mod 4)
Para resolver esta congruencia el metodo usado en la demostracion del
teorema chino del resto en varios textos, por ejemplo en el de Niven y
Zuckermann.
El producto de los modulos m
1
= 3, m
2
= 5 y m
3
= 4 es M = 60.
Dividiendo M por 3, 5 y 4 obtenemos M
1
= 20, M
2
= 12 y M
3
= 15,
respectivamente.
Ahora hallamos n umeros x
i
, y
i
tales que M
i
x
i
+ m
i
y
i
= 1, (1 i 3):
20 (1) + 3 7 = 1, x
1
= 1, y
1
= 7
12 (2) + 5 5 = 1, x
2
= 2, y
2
= 5
15 (1) + 4 4 = 1, x
3
= 1, y
3
= 4
Una solucion del sistema viene dada por:
x =2 M
1
x
1
+ 2 M
2
x
2
+ 3 M
3
x
3
=
=2 20 (1) + 2 12 (2) + 3 15 (1) =
=133 = 13 (mod 60) = 47 (mod 60).
20. Cuantos m ultiplos de b hay en la sucesion a, 2a, 3a, , ba?
xa es un m ultiplo de b si y solo si x es una solucion ax 0 (mod b), y el
n umero de soluciones de esta congruencia es (a, b), es decir el maximo
com un divisor de a y b.
26
6. Los teoremas de Fermat y Wilson
1. Cual es el resto de 5
6
(mod 7), 5
8
(mod 7) y 1945
8
(mod 7)?
Por el teorema de Fermat, 5
6
1 (mod 7). Como consecuencia, 5
8

5
2
4 (mod 7). Ahora usamos que 1945 6 (mod 7) y que 6
6

1 (mod 7). Entonces: 1945

8
6
8
6
2
1 (mod 7).
2. Cual es el resto de 5
10
(mod 11), 5
12
(mod 11) y de
1945
12
(mod 11)?
Por el teorema de Fermat, 5
10
1 (mod 11). Como consecuencia, 5
12

5
2
3 (mod 11). Ahora usamos que 1945 9 (mod 11) y que 9
10

1 (mod 11). Entonces: 1945

12
9
12
9
2
4 (mod 11).
3. Cual es el ultimo dgito de 7
355
?
Hallamos las primeras potencias de 7 y obtenemos: 7
2
9 (mod 10),
7
3
3 (mod 10), 7
4
1 (mod 10). Como 355 = 4 88 + 3, 7
355
7
3

3 (mod 10) y 7
355
acaba en 3.
4. Cuales son los dos ultimos dgitos de 7
355
?
Las primeras potencias de 7 son 7, 49, 343, 2401.
Entonces 7
4
1 (mod 100) y como 355 = 4 88 + 3, 7
355
7
3

43 (mod 100) y 7
355
acaba en 43.
5. Cual es el resto de dividir 314
162
por 163?
Basta tomar a = 314 y p = 163 y obtenemos, por el teorema de Fermat,
314
162
1 (mod 163).
6. Cual es el resto de dividir 314
162
por 7?
Tomando, a = 314 y p = 7 y obtenemos, por el teorema de Fer-
mat, 314
6
1 (mod 7). Entonces 314
162
= (314
6
)
27
1 (mod 7) =
1 (mod 7).
7. Cual es el resto de dividir 314
164
por 165? (Observar que 165
no es primo!)
Descomponemos 165 = 3 5 11 y 314 = 2 157. Por el teorema de
Fermat, 314
2
1 (mod 3), 314
4
1 (mod 5) y 314
10
1 (mod 11).
27
Por tanto:
314
164
= 314
282
1 (mod 3)
314
164
= 314
441
1 (mod 5)
314
164
= 314
1031+4
314
4
6
4
3
2
= 9 (mod 11)
,
Entonces de donde deducimos que 314
164
es una solucion del sistema:
_
x 1 (mod 15)
x 9 (mod 11)
El producto de los modulos m
1
= 11 y m
2
= 15 es M = 165. Dividiendo
M por 15 y 11 obtenemos M
1
= 11 y M
2
= 15, respectivamente.
Ahora hallamos n umeros x
i
, y
i
tales que M
i
x
i
+ m
i
y
i
= 1, (1 i 2):
11 (4) + 15 3 = 1, x
1
= 4, y
1
= 3
15 3 + 11 (4) = 1, x
2
= 3, y
2
= 4
La solucion del sistema viene dada por:
x =1 M
1
x
1
+ 9 M
2
x
2
=
=1 11 (4) + 9 15 3 =
=361 31 (mod 165).
8. Cual es el resto de dividir 2001
2001
por 26?
Como 26 = 2 13, Hallemos los restos de dividir 2001
2001
por 2 y por
13. Evidentemente, 2001
2001
1 (mod 2). Por el teorema de Fermat,
2001
12
1 (mod 13). Usando que, 2001 = 166 12 + 9, y que 2001
1 (mod 13), 2001
2001
2001
9
(1)
9
= 1 (mod 13). Por tanto
2001
2001
sera congruente, modulo 26 con la solucion del sistema
_
x 1 (mod 2)
x 1 (mod 13)
El producto de los modulos es M = 26. Dividiendo M por 2 y 13
obtenemos M
1
= 13 y M
2
= 2, respectivamente.
Ahora hallamos n umeros x
i
, y
i
tales que M
i
x
i
+ m
i
y
i
= 1, (1 i 2):
13 1 + 2 (6) = 1, x
1
= 1, y
1
= 6
2 (6) + 13 1 = 1, x
2
= 6, y
2
= 1
28
Una solucion del sistema viene dada por:
x =1 M
1
x
1
+ (1) M
2
x
2
=
=1 13 1 + (1) 2 (6) =
=25 (mod 26).
9. Demostrar que
(p 1)(p 2) (p r) (1)
r
r! (mod p),
para r = 1, 2, . . . , p 1.
(p 1)(p 2) (p r) (1)(2) (r) =
= (1) (1)
. .
r veces
1 2 r =
= (1)
r
r! (mod p)
10. a) Calcular (n 1)! (mod n) para n = 10, 12, 14 y 15.
(10 1)! = 9 8 7 6 5 4 3 2 1 = 0 (mod 10)
(12 1)! = 11 10 9 8 7 6 5 4 3 2 1 = 0 (mod 12)
(14 1)! = 13 8 7 6 5 4 3 2 1 = 0 (mod 14)
(15 1)! = 14 7 6 5 4 3 2 1 = 0 (mod 15)
b) Enunciar un teorema y demostrarlo.
Si p es primo sabemos que (p1)! 1 (mod p), seg un el teorema
de Wilson. El apartado anterior muestra que si n es cualquiera
de los n umeros 10, 12, 14 y 15, entonces (n 1)! 0 (mod n).
Podemos pensar que esto va a ser cierto cuando n no sea primo.
En efecto, si no es primo podra descomponerse en la forma n = ab
y tanto a como b son distintos de 1 y de n, ambos son n umeros
menores que n. Si a y b pueden elegirse distintos, ambos apare-
ceran en el desarrollo de (n1)!, por lo que (n1)! 0 (mod n).
El unico caso en el que no pueden elegirse a y b distintos es aquel
en que n = p
2
, siendo p un primo. Exceptuando a su vez el caso
p = 2 (o n = 4), que puede comprobarse directamente ((41)! = 6
29
no es divisible por 4), p y 2p seran siempre dos n umeros meno-
res que p
2
1. Por ello, p y 2p apareceran en el desarrollo de
(n1)! = (p
2
1)! y si n = p
2
, sera (n1)! 0 (mod n). La con-
clusion es: Si n > 4 no es primo, entonces (n 1)! 0 (mod n).
11. Demostrar que 2(p 3)! + 1 0 (mod p).
(Suponemos que p es un primo impar mayor o igual que 3). Usando
que
(p 1)! =(p 1)(p 2)(p 3)! =
=(p
2
3p + 2)(p 3)!
2(p 3)! (mod p)
y el teorema de Wilson, obtenemos que 1 2(p 3)! (mod p), que es
lo que queramos demostrar.
12. En 1732 Euler escribio: He obtenido resultados [correctos] a
partir de un teorema elegante, de cuya veracidad estoy seguro,
aunque no tengo demostracion: a
n
b
n
es divisible por el primo
n + 1 si ni a y b lo son. Demostrar este teorema, usando el
teorema de Fermat.
Basta tener en cuenta que si n + 1 no divide ni a a ni a b, entonces,
por el teorema de Fermat, tendremos que a
n
1 (mod (n + 1)) y
b
n
1 (mod (n + 1)), de donde a
n
b
n
0 (mod (n + 1)) es divisible
por n + 1.
13. Observar que
6! 1 (mod 7)
5!1! 1 (mod 7)
4!2! 1 (mod 7)
3!3! 1 (mod 7)
Hacer el mismo tipo de calculos (mod 11).
La instruccion de Mathematica,
Table[{(10-t)!t!, Mod[(10-t)!t!,11]},{t,0,5}]
30
nos permite armar que
10! = 3628800 1 (mod 11)
9!1! = 362880 1 (mod 11)
8!2! = 80640 1 (mod 11)
7!3! = 30240 1 (mod 11)
6!4! = 17280 1 (mod 11)
5!5! = 14400 1 (mod 11)
14. Enunciar un teorema a partir de los datos del problema 13, y
demostrarlo.
El teorema puede enunciarse as: Si p es primo y 0 r < p, entonces
(p1r)!r! = (1)
r+1
(mod p). Si usamos (ejercicio 9) que (p1)(p
2) (p r) (1)
r
r! (mod p), obtenemos:
(p 1)! = (p 1)(p 2) (p r) (p 1 r) !
1 (1)
r
r!(p 1 r)! (mod p)
r!(p 1 r)! (1)
r+1
(mod p)
15. Supongamos que p es un primo impar.
a) Demostrar que 1
p1
+ 2
p1
+ + (p 1)
p1
1 (mod p).
b) Demostrar que 1
p
+ 2
p
+ + (p 1)
p
0 (mod p).
a) 1
p1
+ 2
p1
+ + (p 1)
p1

p1
..
1 + + 1 1 (mod p).
b) 1
p
+ 2
p
+ + (p 1)
p
1 + 2 + + p =
p1
2
p 0 (mod p).
16. Demostrar que el recproco del teorema de Fermat es falso.
[Superpista: Considerar 2
340
(mod 341)].
341 = 11 31 no es primo. Hallemos 2
340
(mod 11) y 2
340
(mod 31).
Seg un el teorema de Fermat, 2
10
= 1 (mod 11), por lo que 2
340
=
(2
10
)
34
1 (mod 11). De la misma forma, como 2
5
1 (mod 31),
2
340
= 2
685
1 (mod 31). Entonces, obtenemos 2
340
1 (mod 341).
Vemos entonces que la relacion a
n1
1 (mod n) no implica que n sea
primo.
17. Demostrar que para cualesquiera dos primos diferentes p y q,
31
a) pq|(a
p+q
a
p+1
a
q+1
+ a
2
)
b) pq|(a
pq
a
p
a
q
+ a)
a) Usamos el teorema de Fermat y obtenemos que a
p
a (mod p) y
que a
q
a (mod q), p|(a
p
a) y q|(a
q
a), de donde pq divide a
(a
p
a)(a
q
a) = (a
p+q
a
p+1
a
q+1
+ a
2
).
b) Demostremos que q divide a a
pq
a
p
a
q
+a. Usando el teorema de
Fermat, obtenemos que a
p1
1 (mod p) y que a
q1
1 (mod q).
Elevando a p, a
p(q1)
1 (mod q) y de ah, a
pq
a
p
a
q
+ a
2
=
a
p
(a
pqp
1) + a(1 a
q1
) es divisible por q.
De forma parecida se demuestra que p divide a a
pq
a
p
a
q
+ a.
18. Demostrar que si p es un primo impar, entonces 2p|(2
2p1
2).
Usando el teorema de Fermat, 2
p1
1 (mod p) y, elevando al cuadra-
do, 2
2p2
1 (mod p), es decir, 2
2p2
= 1 + kp para un cierto entero
k. Multiplicando esta igualdad por 2, obtenemos 2
2p1
= 2 + k(2p), es
decir, 2
2p1
2 es un m ultiplo de 2p.
19. Para que enteros n es cierto que p|(1 + n + n
2
+ + n
p2
)?
Si p|n, entonces no es cierta la relacion, pues p|n y p|(1+n+n
2
+ +
n
p2
) implica que p|1.
Si p|(n 1), entonces tampoco es cierta la relacion, pues tenemos n
1 (mod p) y p|(1 + n + n
2
+ + n
p2
) 1 (mod p.
Si p n y p (n 1) s es cierta la relacion pues
1 + n + n
2
+ + n
p2
=
n
p1
1
n 1

0
n 1
= 0 (mod p)
20. Demostrar que todo primo impar n excepto el 5 divide a alg un
n umero de la forma 111 11 (k dgitos, todos unos).
Si p es un primo impar distinto de 5, p no divide a 10. El unico p que
divide a 10 1 = 9 es p = 3 que divide a 111. Para los demas p, el
ejercicio anterior nos dice que p es un divisor de
111 11
. .
p1 unos
= 1 + 10 + 10
2
+ + 10
p2
.
32
7. Los divisores de un entero
1. Calcular d(42), (42), d(420) y (42).
Si n = p
e
1
1
p
e
2
2
p
e
r
r
, entonces:
d(n) = (e
1
+ 1) (e
2
+ 1) (e
r
+ 1)
(n) =
p
e
1
+1
1
1
p
1
1

p
e
2
+1
2
1
p
2
1

p
er+1
r
1
p
r
1
Como 42 = 2
1
3
1
7
1
,
d(42) = 2 2 2 = 8, (42) =
2
2
1
2 1

3
2
1
3 1

7
2
1
7 1
= 3 4 8 = 96.
Como 420 = 2
2
3
1
5
1
7
1
,
d(420) = 3 2 2 2 = 24,
(420) =
2
3
1
2 1

3
2
1
3 1

5
2
1
5 1

7
2
1
7 1
= 7 4 6 8 = 1344.
2. Calcular d(540), (540), d(5400), y (5400).
Como 540 = 2
2
3
3
5
1
,
d(540) = 3 4 2 = 24,
(540) =
2
3
1
2 1

3
4
1
3 1

5
2
1
5 1
= 7 40 6 = 1680.
Como 540 = 2
3
3
3
5
2
,
d(540) = 4 4 3 = 48,
(540) =
2
4
1
2 1

3
4
1
3 1

5
3
1
5 1
= 15 40 31 = 18600.
3. Calcular d y para 10115 = 5 7 17
2
y 100115 = 5 20023.
d(10115) = 2 2 3 = 12,
(10115) = (1 + 5) (1 + 7)
17
3
1
17 1
= 6 8 307 = 14736.
d(100115) = 2 2 = 4,
(100115) = (1 + 5)(1 + 20023) = 6 20024 = 120144.
33
4. Calcular d y para 10116 = 2
2
3
2
281 y 100116 = 2
2
3
5
103.
Para 10116:
d = 3 3 2 = 18,
= (1 + 2 + 4) (1 + 3 + 9) (1 + 281) = 7 13 282 = 25662.
Para 100116:
d = 3 6 2 = 36,
= (1 + 2 + 4)
3
6
1
3 1
(1 + 103) = 7 364 104 = 264992.
5. Demostrar que (n) es impar si n es una potencia de 2.
Si n = 2
r
, entonces (n) = 1 + 2 + + 2
r
=
2
r+1
1
21
= 2
r+1
1, que es
un n umero impar.
6. Demostrar que si f(n) es multiplicativa, tambien lo es f(n)/n.
Sea f(n) multiplicativa y sea g(n) = f(n)/n. Entonces, si m y n son
enteros positivos tales que (m, n) = 1, se cumplira que
g(mn) =
f(mn)
mn
=
f(m)f(n)
mn
=
f(m)
m

f(n)
n
= g(m)g(n),
es decir, g es tambien una funcion multiplicativa.
7. Cual es el menor entero n tal que d(n) = 8? Y el menor tal
que d(n) = 10?
Si n = p
e
1
1
p
e
2
2
p
e
r
r
, entonces: d(n) = (e
1
+ 1) (e
2
+ 1) (e
r
+ 1).
8 se descompone propiamente de dos formas 2 4 y 2 2 2, es decir que
un n umero con 8 divisores sera de la forma n = pq
3
o n = pqr. En el
primer caso, para p = 3, q = 2, obtenemos n = 24, y en el segundo, para
p = 2, q = 3, r = 5, obtenemos n = 30. Por tanto, el n mas peque no
con d(n) = 8 es n = 24.
10 se descompone solo de una forma 2 5. Un n umero con diez divisores
sera de la forma n = p q
4
. El mas peque no de todos ellos se obtiene
para p = 3, q = 2 y es n = 48.
8. Tiene d(n) = k una solucion n para cualquier k?
S. Dado el n umero k, el n umero p
k1
tiene k divisores, por lo que
d(n) = k.
34
9. En 1644, Mersenne preguntaba por un n umero con 60 diviso-
res. Encontrar uno menor que 10,000.
De cualquier descomposicion de 60 podremos obtener n umeros con 60
divisores. Por ejemplo, de la descomposicion trivial 60 = 60, obtendre-
mos que p
59
, con p primo tiene 60 divisores, pero 2
59
> 10000 y no
nos sirve. Puede servir el n umero n = 2
4
3
2
5 7 = 5040, que tiene
5 3 2 2 = 60 divisores.
10. Encontrar innitos n umeros n tales que d(n) = 60.
Cualquier n umero de la forma p
59
, siendo p primo, tiene 60 divisores.
11. Si p es un primo impar, para que valores de k es impar la
expresion 1 + p + + p
k
?
Si p es impar, tambien lo es cualquier potencia de p, por lo que la suma
1 + p + + p
k
, de k + 1 n umeros impares, sera impar cuando k sea
par.
12. Para que n umeros n es impar (n)?
Si n = p
e
1
1
p
e
r
r
, (n) = (1 + + p
e
1
1
) (1 + + p
e
r
r
) sera impar si
y solo todos los parentesis son impares, es decir, si y lo si todos los e
i
son pares, que es lo mismo que decir que n es un cuadrado.
13. Si n es un cuadrado, demostrar que d(n) es impar.
Si n es un cuadrado, todos los exponentes de su descomposicion factorial
son pares: n = p
2e
1
1
p
2e
r
r
. Por tanto d(n) = (2e
1
+ 1) (2e
r
+ 1) es
un producto de n umeros impares y es impar.
14. Si d(n) es impar, demostrar que n es un cuadrado.
Sea n = p
e
1
1
p
er
r
tal que d(n) = (e
1
+1) (e
r
+1) es impar. Todos los
parentesis deben ser impares, pues si uno de ellos fuera par, tambien lo
sera d(n), as que todos los e
i
son pares y n es un cuadrado.
15. Observar que 1+
1
3
=
4
3
, 1+
1
2
+
1
4
=
7
4
, 1+
1
5
=
6
5
, 1+
1
2
+
1
3
+
1
6
=
12
6
,
1+
1
7
=
8
7
y 1+
1
2
+
1
4
+
1
8
=
15
8
. Enunciar y demostrar un teorema.
Las fracciones que sumamos en la parte izquierda de las igualdades son
los inversos de los divisores del n umero. El resultado es una fraccion con
35
numerador la suma de divisores del n umero y denominador el n umero.
Entonces, el enunciado sera

d|n
1
n
=

d|n
d
n
=
(n)
n
.
La demostracion es sencilla, si tenemos en cuenta que si ordenamos
los divisores d
1
= 1, d
2
, . . . , d
r1
, d
r
= n de n cumplen que d
1
d
n
=
d
2
d
r1
= = n, y entonces

d|n
1
n
=
1
d
1
+
1
d
2
+
1
d
r1
+
1
d
r
=
d
r
n
+
d
r1
n
+ +
d
2
n
+
d
1
n
=
(n)
n
.
16. Encontrar innitos n umeros n tales que (n) (n 1).
Empecemos por demostrar que hay innitos primos de la forma 4m+3.
Si hubiera un n umero nito de ellos, digamos p
1
, p
2
, . . . , p
r
, considera-
mos el n umero n = 4(p
1
p
2
. . . p
r
) 1 = 4(p
1
p
2
. . . p
r
1) +3. El n umero
n, que debe ser compuesto, no puede tener todos sus factores primos
de la forma 4m+1, ya que tambien lo sera n. Entonces, alguno de los
primos p
i
debe ser factor de n, pero esto es imposible, ya que p
i
sera
un divisor de 1 por la relacion 4p
1
p
2
. . . p
r
N = 1.
Ahora, sea n cualquier n umero primo de la forma p = 4m+3. Como n
es primo, (p) = p+1 = 4m+4. Por otro lado, (p1) = (4m+2) =
(2 (2m + 1)) = 3 (2m + 1) > 3(2m + 2) = 6m + 6 > 4m + 4.
La solucion de este problema no se me ocurrio a m; despues de pensar
en n umeros de la forma n = 2
k
+1, que tambien parecen ser solucion del
problema, pero que no lo pude demostrar, envie un correo a Underwood
Dudley pidiendo una pista y esto fue lo que me contesto:
I dont remember what I had in mind when I rst included pro-
blem 7 of section 16, but it looks as if taking n = p, where p is a
prime such that p = 2s+1 with s odd works. Then (n) = p+1 =
2s+2, and (n1) = (2s) = 3(s) 3(s+1) = 3s+3 2s+2.
The existence of innitely many such primes is guaranteed by
Dirchlets theorem on primes in arithmetic progressions.
Para no usar el teorema de Dirichlet, lo que he hecho aqu es incluir
la demostracion del caso particular del teorema de Dirichlet para los
primos de la forma 4m + 3.
36
17. Si N es impar, cuantas soluciones tiene x
2
y
2
= N?
Teniendo en cuenta que x
2
y
2
= (x +y)(x y), para cada descompo-
sicion N = m n, estudiamos el sistema
_
x + y = m
x y = n
.
Al ser N impar, tambien lo seran m y n, y el sistema tendra una unica
solucion entera, de la forma x =
1
2
(m + n), y =
1
2
(m n). Mas a un,
suponiendo que
(
1
2
(m
1
+ n
1
),
1
2
(m
1
n
1
)) = (
1
2
(m
2
+ n
2
),
1
2
(m
2
n
2
)),
facilmente llegamos a m
1
= m
2
y n
1
= n
2
, es decir, cada sistema
produce soluciones diferentes. Cuantas descomposiciones N = m n
podemos hacer? Si solo contamos los m y n positivos, habra la mitad
de d(N), pero si contamos las posibilidades negativas, el resultado es
2 d(N).
18. Desarrollar una formula para
2
(n), la suma de los cuadrados
de los divisores positivos de n.
Sea n = p
e
1
1
p
e
r
r
. Entonces:

2
(n) =

d|n
d
2
=

f
i
e
i
p
2f
1
1
p
2f
r
r
=

f
1
e
1
p
2f
1
1

frer
p
2f
r
r
=
=

f
1
e
1
(p
2
1
)
f
1

f
r
e
r
(p
2
r
)
f
1
=
p
2e
1
+1
1
1
p
2
1
1

p
2e
r
+1
r
1
p
2
r
1
.
19. Adivinar una formula para

k
(n) =

d|n
d
k
,
siendo k un entero positivo.

k
(n) =

d|n
d
k
=

f
i
e
i
p
kf
1
1
p
kf
r
r
=

f
1
e
1
p
kf
1
1

f
r
e
r
p
kf
r
r
=
=

f
1
e
1
(p
k
1
)
f
1

frer
(p
k
r
)
f
1
=
p
ke
1
+1
1
1
p
k
1
1

p
ker+1
r
1
p
k
r
1
.
37
20. Demostrar que el producto de los divisores positivos de n es
n
d(n)/2
.
Ordenamos los divisores d
1
= 1, d
2
, . . . , d
r1
, d
r
= n de n de manera
que
_

_
d
1
d
r
=n
d
2
d
r1
=n
... =...
d
r1
d
2
=n
d
r
d
1
=n
Al multiplicar, obtenemos (d
1
d
2
d
r1
d
r
)
2
= n
d(n)
, de donde
d
1
d
2
d
r1
d
r
=

n
d(n)
= n
d(n)/2
.
38
8. N umeros perfectos
Un n umero N es perfecto cuando la suma de todos sus divisores es 2N,
es decir, si es N la suma de sus divisores menores que N.
Si 2
k
1 es primo, entonces N = 2
n1
(2
k
1) es primo.
Si N es par y perfecto, entonces N = 2
p1
(2
p
1) para alg un primo p
y 2
p
1 tambien es primo.
M y N son amigos cuando (M) = (N) = M + N.
N abundante si (n) > 2n, deciente si (n) < 2n y triangular si es de
la forma
1
2
n(n + 1).
1. Comprobar que 2620, 2924 y 17296, 18416 son parejas de n ume-
ros amigos. (La ultima pareja, descubierta por Fermat, fue la
segunda encontrada. Tener en cuenta que 17296 = 2
4
23 47 y
18416 = 2
4
1151).
Con Divisors[2620], Mathematica nos dice que los divisores de 2620
son 1, 2, 4, 5, 10, 20, 131, 262, 524, 655, 1310, 2620. Usando ahora la
isntruccion DivisorSigma[1,2620] obtenemos que la suma de estos
divisores es (2620) = 5544.
De forma parecida, obtenemos que los divisores de 2924 son 1, 2, 4, 17,
34, 43, 68, 86, 172, 731, 1462, 2924, siendo su suma tambien igual a
5544. Por tanto 2620 y 2924 son n umeros amigos.
Con 17296 y 18416, hay mas n umeros:
Divisores de 17296: 1, 2, 4, 8, 16, 23, 46, 47, 92, 94, 184, 188, 368,
376, 752, 1081, 2162, 4324, 8648, 17296.
Divisores de 18416: 1, 2, 4, 8, 16, 1151, 2302, 4604, 9208, 18416.
Suma de los divisores, en ambos casos: 35712.
Por tanto, tambien se trata de n umeros amigos.
2. Durante largo tiempo se penso que los n umeros perfectos ter-
minaban alternativamente en 6 y 8. Demostrar que esto no
es correcto comprobando que los n umeros correspondientes a
los primos 2
13
1 y 2
17
1 acaban ambos en 6.
39
Sea p = 13 o p = 17. El n umero perfecto correspondiente es N =
2
p1
(2
p
1). Como p es de la forma 4m + 1, 2
p
acaba en 2 y 2
p
1
acaba en 1. Ahora, p 1 es m ultiplo de 4 y 2
p1
acaba en 6, por lo que
N acabara en 6.
3. Clasicar los enteros 2, 3, . . . , 21 como abundantes, decientes
o perfectos.
6 es perfecto. 12, 18 y 20 son abundantes. Los demas, 2, 3, 4, 5, 7, 8,
9, 10, 11, 13, 14, 15, 16, 17, 19 y 21, son decientes.
4. Clasicar los enteros 402, 403, . . . , 421 como abundantes, de-
cientes o perfectos.
402, 408, 414, 416 y 420 son abundantes. El resto, 403, 404, 405, 406,
407, 409, 410, 411, 412, 413, 415, 417, 418, 419 y 421 son decientes.
n 402 403 404 405 406 407 408 409 410 411
(n) 816 448 714 726 720 456 1080 410 756 552
n 412 413 414 415 416 417 418 419 420 421
(n) 728 480 936 504 882 560 720 420 1344 422
5. Si (n) = kn, se dice que n es un n umero k-perfecto. Compro-
bar que 672 es 3-perfecto y que 2, 178, 540 = 2
2
3
2
5 7
2
13 19
es 4-perfecto.
672 = 2
5
3 7. A partir de aqu obtenemos:
(672) = (2
6
1) (3 + 1) (7 + 1) = 63 32 = 2016 = 3 672.
(2178540) =(1 + 2 + 2
2
) (1 + 3 + 3
2
) 6 (1 + 7 + 7
2
) 14 20 =
=7 13 6 57 14 20 =
=8714160 = 4 2178540.
6. Demostrar que no hay n umeros de la forma 2
a
3
b
que sean 3-
perfectos.
Supongamos que N = 2
a
3
b
es 3-perfecto. Entonces de(N) = 3N de-
ducimos que
(2
a+1
1)
3
a+1
1
2
= 2
a
3
a+1
(2
a+1
1)(3
a+1
1) = 2
a+1
3
a+1
.
40
Multiplicando y cancelando, obtenemos 2
a+1
+ 3
a+1
= 1, que es impo-
sible.
7. Diremos que un n umero n es superperfecto si ((n)) = 2n.
Demostrar que si n = 2
k
y 2
k+1
1 es primo, entonces n es
superperfecto.
Con las hipotesis sobre n, es evidente que
((n)) = ((2
k
)) = (2
k+1
1) = 2
k+1
= 2n.
8. Durante mucho tiempo se penso que todo n umero abundante
era par. Demostrar que 945 es abundante, y encontrar otro
n umero abundante de la forma 3
a
5 7.
Como 945 = 3
2
109,
(945) = (1 + 3 + 3
2
) (1 + 109) = 13 110 = 1430 > 945.
Si n = 3
a
5 7, entonces (n) =
3
a+1
1
2
6 8 = 24(3
a+1
1) = 72 3
a
24.
Entonces (n) > n 72 3
a
24 > 35 3
a
37 3
a
> 35 a 0. Es
decir, todos los n umeros de la forma 3
a
5 7 son abundantes.
9. En 1575 se observo que todo n umero perfecto par es un n u-
mero triangular. Demostrar que esto es as.
Sea N un n umero perfecto par. Por el teorema de Euler, N es de la
forma 2
k1
(2
k1
1), siendo 2
k1
1 primo. Entonces N = 2
k1
(2
k

1) =
1
2
(2
k
1)2
k
, es decir N es de la forma
1
2
m(m+1) con m = 2
k
1
y es un n umero triangular.
10. En 1575 se observo que
6 =1 + 2 + 3,
28 =1 + 2 + 3 + + 7,
496 =1 + 2 + 3 + + 31.
Puede esto continuar?
Seg un hemos visto en el ejercicio anterior, cualquier n umero perfecto
par es un n umero triangular:
2
k1
(2
k
1) =
1
2
(2
k
1)2
k
= 1 + 2 + 3 + + (2
k
1).
41
11. Sean
p =3 2
e
1,
q =3 2
e1
1,
r =3
2
2
2e1
1,
siendo e un entero positivo. Si p, q y r son primos, demostrar
que 2
e
pq y 2
e
r son amigos. (Considerando e 200, p, q y r son
primos solo para e = 2, 4, 7.)
Sean M = 2
e
pq, N = 2
e
r.
(M) =(2
e
pq) = (2
e+1
1)(p + 1)(q + 1) =
=(2
e+1
1) 3 2
e
3 2
e1
=
=2
2e1
3
2
(2
e+1
1).
(N) =(2
e
r) = (2
e+1
1)(r + 1) = (2
e+1
1) 3
2
2
2e1
.
Habiendo comprobado que (M) = (N), solo queda ver que ambos
valores de son iguales a M + N para demostrar que M y N son
amigos:
M + N =2
e
(pq + r) =
=2
e
_
(3 2
e
1) (3 2
e1
1) + (3
2
2
2e1
1)
_
=
=2
e
(3
2
2
2e1
3 2
e
3 2
e1
+ 1 + 3
2
2
2e1
1) =
=2
e
(2 3
2
2
2e1
9 2
e1
) =
=2
e
3
2
(2
2e
2
e1
) = 2
2e1
3
2
(2
e+1
1).
El programita siguiente nos permite conrmar la armacion del enun-
ciado:
For[e = 1, e <= 2000, e++,
p := 3*2^e - 1;
q := 3*2^(e - 1) - 1;
r := 3^2 2^(2 e - 1) - 1;
If[PrimeQ[p] && PrimeQ[q] && PrimeQ[r],
Print[{e, p, q, r, 2^e p q, 2^e r}]]]
e p q r M N
2 11 5 71 220 284
4 47 23 1151 17296 18416
7 383 191 73727 9363584 9437056
42
12. Demostrar que si p > 3 y 2p + 1 es primo, entonces 2p(2p + 1)
es deciente.
Sea n = 2p(2p + 1). Suponiendo, que no lo dice el enunciado, que p es
primo, tenemos (p) = 3(p+1)(2p+2) = 6(p+1)
2
= 6p
2
+12p+6. Por
otro lado, 2n = 4p(2p+1) = 8p
2
+4p y 6p
2
+12p+6 < 8p
2
+4p 2p
2

8p6 > 0 p
2
4p3 > 0 p
2
4p+4 > 1 (p2)
2
> 1 p > 3.
La suposicion de que p sea primo, que el autor habra considerado
implcita al llamar p al n umero es necesaria para concluir que el n
es deciente, pues si tomamos p = 6, n = 156 = 2
2
3 13 y (156) =
(1 + 2 + 4) 4 14 = 392 > 312 = 2 156.
13. Demostrar que todos los n umeros perfectos pares acaban en
6 o en 8.
Sabemos que un n umero perfecto par es de la forma 2
p1
(2
p
1), siendo
p un n umero primo.
Si p es de la forma 4k+1, entonces n = 2
4k
(2
4k+1
1) = 16
k
(216
k
1).
Como 16
k
siempre acaba en 6 y 2 16
k
1 siempre acaba en 1, n
acabara en 6.
Supongamos ahora que p es de la forma 4k + 3.
Entonces n = 2
4k+2
(2
4k+3
1) = 4 16
k
(8 16
k
1). Como 4 16
k
siempre acaba en 4 y 8 16
k
1 siempre acaba en 7, n acabara en 8.
14. Si n es un n umero perfecto par y n > 6, demostrar que la suma
de sus dgitos es congruente con 1 (mod 9).
Sabemos que un n umero perfecto par es de la forma 2
p1
(2
p
1), siendo
p un n umero primo.
Si p es de la forma 4k + 1, entonces n = 2
4k
(2
4k+1
1). Conside-
remos los diferentes casos de k modulo 3 en la siguiente tabla:
k (mod 3) 2
4k
(mod 9) (2
4k+1
1) (mod 9)
0 1 1
1 7 4
2 4 7
Vemos que en todos los casos es 2
4k
(2
4k+1
1) 1 (mod 9).
43
Si p es de la forma 4k + 3, entonces n = 2
4k+2
(2
4k+3
1). Distin-
guiendo casos como antes tenemos:
k (mod 3) 2
4k+2
(mod 9) (2
4k+3
1) (mod 9)
0 4 7
1 1 1
2 7 4
Tambien aqu es 2
4k
(2
4k+1
1) 1 (mod 9) en todos los casos.
15. Si p es impar, demostrar que 2
p1
(2
p
1) 1+
9
2
p(p1) (mod 81).
44
9. El teorema y la funcion de Euler
1. Calcular (42), (420) y (4200).
(42) =(2 3 7) = (2) (3) (7) = 1 2 6 = 12.
(420) =(2
2
3 5 7) = (2
2
) (3) (5) (7) =
=(2
2
2) 2 4 6 = 96.
(4200) =(2
3
3 5
2
7) = (2
3
) (3) (5
2
) (7) =
=(2
3
2
2
) 2 (5
2
5) 6 = 960.
2. Calcular (54), (540) y (5400).
(54) =(2 3
3
) = (2) (3
3
) = 1 (3
3
3
2
) = 18.
(540) =(2
2
3
3
5) = (2
2
) (3
3
) (5) =
=(2
2
2) (3
3
3
2
) (5 1) = 2 18 4 = 144.
(5400) =(2
3
3
3
5
2
) = (2
3
) (3
3
) (5
2
) =
=(2
3
2
2
) (3
3
3
2
) (5
2
5) = 1440.
3. Calcular para 10115 = 5 7 17
2
y 100115 = 5 20023.
(10115) =(5 7 17
2
) = (5) (7) (17
2
) =
=4 6 (17
2
17) = 4 6 17 16 = 6528.
(100115) =(5 20023) = (5) (20023) = 4 20022 = 80088.
4. Calcular para 10116 = 2
2
3
2
281 y 100116 = 2
2
3
5
103.
(10116) =(2
2
3
2
281) = (2
2
) (3
2
) (281) =
=(2
2
2) (3
2
3) (281 1) = 2 6 280 = 3360.
(100116) =(2
2
3
5
103) = (2
2
) (3
5
) (2
2
3
5
103) =
=(2
2
2) (3
5
3
4
) 102 = 33048.
5. Calcular a
8
(mod 15) para a = 1, 2, . . . , 14.
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14
a
2
1 4 9 1 10 6 4 4 6 10 1 9 4 1
a
4
1 1 6 1 10 6 1 1 6 10 1 6 1 1
a
8
1 1 6 1 10 6 1 1 6 10 1 6 1 1
45
(Se puede comprobar con Table[Mod[a^8, 15], {a, 1, 14}]) M
6. Calcular a
8
(mod 16) para a = 1, 2, . . . , 15.
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a
2
1 4 9 0 9 4 1 0 1 4 9 0 9 4 1
a
4
1 0 1 0 1 4 1 0 1 0 1 0 1 0 1
a
8
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
(Se puede comprobar con Table[Mod[a^8, 16], {a, 1, 15}]). M
7. Demostrar que si n es impar, entonces (4n) = 2n.
(4) = (2
2
) = 2
2
2 = 2. Entonces, al ser una funcion multiplicativa,
(4n) = (4)(n) = 2(n).
8. Los n umeros perfectos cumplen (n) = 2n. Que n umeros cumplen
(n) = 2n?
Ninguno, ya que para cualquier n es (n) < n < 2n.
9. 1 + 2 =
3
2
(3), 1 + 3 =
4
2
(4), 1 + 2 + 3 + 4 =
5
2
(5), 1 + 5 =
6
2
(6),
1 + 2 + 3 + 4 + 5 + 6 =
7
2
(7), 1 + 3 + 5 + 7 =
8
2
(8). Enunciar un
teorema.
Todos los sumandos que vemos son primos relativos con n y menores
que n: La suma de los n umeros primos relativos con n y menores que
n es
n
2
(n). Es decir:

d =
n
2
(n),
donde la suma se efect ua sobre los n umeros primos relativos con n y
menores que n.
Teniendo en cuenta que hay (n) divisores de n y menores que n,
podemos expresar:

d =
n
2

_
d
n
2
_
= 0

(2d n) = 0.
Si 1 d < n es primo relativo con n, tambien lo es d

= nd. Teniendo
en cuenta que 2d

n = 2(n d) n = n 2d, la suma anterior

estara formada por pares de sumandos opuestos que se cancelaran y
daran resultado 0.
46
10. Demostrar que

px
(p)

px
(p) =

px
d(p).
Si p es primo, (p) = p + 1, (p) = p 1 y d(p) = 2, por lo que, para
cada p se cumple que (p) (p) = d(p).
11. Demostrar el Lema 3, es decir que si (a, m) = 1 y a b (mod m),
entonces (b, m) = 1, usando para ello que existen enteros r y s
tales que ax + my = 1.
En efecto, la condicion (a, m) = 1 implica que existen enteros r y s
tales que ax + my = 1. Por su parte, la condicion a b (mod m)
implica que existe un entero k tal que a b = km. Sustituyendo a =
b + km en ax + my = 1, obtenemos (b + km)x + my = 1, es decir,
bx+m(kx+y) = 1, es decir, existen n umeros enteros x

= x, y

= kx+y
tales que bx

+ my

= 1, por lo que (b, m) = 1.

12. Si (a, m) = 1, demostrar que cualquier x cumpliendo la con-
gruencia x ca
(m)1
(mod m) cumple ax c (mod m).
x ca
(m)1
(mod m) ax aca
(m)1
= ca
(m)
c (mod m).
13. Sea f(n) = (n+(n))/2. Demostrar que f(f(n)) = (n) si n = 2
k
,
k = 2, 3, . . . .
(n) =(2
k
) = 2
k
2
k1
= 2
k1
f(n) =
n + (n)
2
=
2
k
+ 2
k1
2
= 2
k1
+ 2
k2
= 3 2
k2
f(f(n)) =
3 2
k2
+ 2 (2
k2
2
k3
)
2
=
3 2
k2
+ 2
k1
2
k2
2
=
=2 2
k2
= 2
k1
= (n).
14. Encontrar cuatro soluciones de (n) = 16.
Una primera solucion es n = 17, pues 17 es primo y (n) = 171 = 16.
Otra solucion facil es n = 2
5
= 32, puesto que (2
k
) = 2
k1
y 16 = 2
4
.
Pongamos n = 2
e
p con p primo. Entonces (n) = 2
e1
(p 1) = 16.
47
Dando valores a e obtenemos soluciones para p =
16
2
e1
+ 1 y n = 2
e
p:
e = 1, p = 17, n = 34
e = 3, p = 5, n = 40
e = 4, p = 3, n = 48
Habra mas soluciones? Si preguntamos a Mathematica con
For[n=1, n<=100, n++, If[EulerPhi[n]==16,Print[n]]] M
A parte de las cinco soluciones anteriores, nos dara n = 60.
15. Encontrar todas las soluciones de (n) = 4 y demostrar que no
hay mas.
Si n es impar, no puede tener factores de la forma m
2
, pues entonces
m sera un factor de (m) = 4. Como los divisores de 4 son solo 1, 2
y 4, los factores impares de n solo pueden ser 3 y 5. Pero n = 3s
4 = (n) = 2(s) (s) = 2 s = 3. (imposible). Por tanto la unica
posibilidad cuando n es impar es n = 5.
Si n = 2
e
, (n) = 2
e1
= 4 e = 3 n = 8.
Si n = 2
e
m, con m impar, (n) = 2
e1
(m) = 4.
e = 1, (m) = 4, m = 5, n = 10
e = 2, (m) = 2, m = 3, n = 12
e = 4, (m) = 1, imposible
Las soluciones, son por tanto, 5, 8, 10 y 12.
16. Demostrar que (mn) > (m)(n) si m y n tienen un factor
com un mayor que 1.
Si (m, n) = d, entonces m = dm

y n = dn

con (m

, n

) = 1. Llamemos
d
1
= (d, m

) y d
2
= (d, n

).
17. Demostrar que (m, n) = 2 implica (mn) = 2(m)(n).
Podemos escribir m = 2
r
u, n = 2
s
v, siendo exactamente uno de los
n umeros r y s igual a 1, y siendo tambien u y v n umeros impares tales
que (u, v) = 1. Con todo ello podemos calcular
(m) = 2
r1
(u),
(n) = 2
s1
(v),
(mn) = (2
r+s
uv) = 2
r+s1
(uv),
(m)(n) = 2
r1
(u)2
s1
(v) = 2
r+s2
(uv).
48
18. Demostrar que (n) =
n
2
si y solo si n = 2
k
para alg un entero
positivo k.
La parte evidente es que si n = 2
k
, entonces
(n) = 2
k1
(2 1) = 2
k1
=
n
2
.
Ahora supongamos que (n) =
n
2
. Como n es par, sera de la forma
n = 2
k
m con m impar. Entonces
2
k1
m =
n
2
= (n) = (2
k
m) = 2
k1
(m) (m) = m m = 1,
resultando n un n umero de la forma 2
k
para alg un entero positivo k.
19. Demostrar que n1 y n+1 son ambos primos y n > 4 entonces
(n)
n
3
.
Si n1 y n+1 son primos, desde luego n es par, y ademas es divisible por
3, y puede expresarse n = 2
k
3
h
m con (2, m) = (3, m) = 1 y k, h 1.
Entonces, (n) = 2
k1
3
h1
2 (m) = 2
k
3
h1
(m) 2
k
3
h1
m =
n
3
.
20. Demostrar que (n) = 14 es imposible.
Si p
e
es la mayor potencia de un primo p que divide a n, entonces
p
e1
(p 1) divide a (n) = 14. Entonces, p 1 puede ser 1, 2, 7 o 14.
Como p es primo, p puede ser unicamente 2 o 3. El caso p = 3 obliga a
que e 1 y en el caso p = 2 puede ser e 2. Entonces n = 2
e
3
f
siendo
0 e 2 y 0 f 1. Los valores posibles para n se reducen a 1, 2,
3, 4, 6, 12 y los correspondientes valores de (n) son 1, 1, 2, 2, 2, 4.
49
10. Races primitivas
1. Encontrar los ordenes de 1, 2, . . . , 12 (mod 13).
Construimos la siguiente tabla:
a 1 2 3 4 5 6 7 8 9 10 11 12
a
2
4 9 3 12 10 10 12 3 9 4 1
a
3
8 1 12 8 8 5 5 1 12 5
a
4
3 9 1 9 9 1 3 3
a
5
6 10 2 11 4 7
a
6
12 1 12 12 1 12
a
7
11 7 6 2
a
8
9 3 3 9
a
9
5 5 8 8
a
10
10 4 4 10
a
11
7 11 2 6
a
12
1 1 1 1
o(a) 1 12 3 6 4 12 12 4 3 6 12 2
2. Encontrar los ordenes de 1, 2, . . . , 16 (mod 17).
Construimos la siguiente tabla:
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a
2
4 9 16 8 2 15 13 13 15 2 8 16 9 4 1
a
3
8 10 13 6 12 3 2 15 14 5 11 4 7 9
a
4
16 13 1 13 4 4 16 16 4 4 13 1 13 16
a
5
15 5 14 7 11 9 8 6 10 3 12 2
a
6
13 15 2 8 9 4 4 9 8 2 15 13
a
7
9 11 10 14 12 15 2 5 3 7 6 8
a
8
1 16 16 16 16 1 1 16 16 16 16 1
a
9
14 12 11 10 7 6 5 3
a
10
8 9 15 2 2 15 9 8
a
11
7 11 5 14 3 12 6 10
a
12
4 4 13 13 13 13 4 4
a
13
12 3 10 6 11 7 14 5
a
14
2 15 9 8 8 9 15 2
a
15
6 7 3 5 12 14 10 11
a
16
1 1 1 1 1 1 1 1
o(a) 1 8 16 4 16 16 16 8 8 16 16 16 4 16 8 2
3. Una de las races primitivas de 19 es 2. Encontrar todas las
demas.
Por ser 2 una raz primitiva de 19, sabemos que 2
k
es una raz primitiva
modulo de 19 si y solo si (k, 18) = 1:
50
k 1 5 7 11 13 17
2
k
2 13 14 15 3 10
4. Una de las races primitivas de 23 es 5. Encontrar todas las
demas.
Por ser 5 una raz primitiva de 23, sabemos que 5
k
es una raz primitiva
modulo de 23 si y solo si (k, 22) = 1:
k 1 3 5 7 9 13 15 17 19 21
5
k
5 10 20 17 11 21 19 15 7 14
5. Cuales son los ordenes de 2, 4, 7, 8, 11, 13 y 14 (mod 15)?.
Tiene 15 races primitivas?
a 2 4 7 8 11 13 14
a
2
4 1 4 4 1 4 1
a
3
8 13 2 7
a
4
1 1 1 1
o(a) 4 2 4 4 2 4 2
Vemos que en ning un caso es o(a) = (15) = 10. Por tanto, 15 no tiene
races primitivas.
6. Cuales son los ordenes de 3, 7, 9, 11, 13, 17 y 19 (mod 20)?.
Tiene 20 races primitivas?
a 3 7 9 11 13 17 19
a
2
9 9 1 1 9 9 1
a
3
7 3 17 13
a
4
1 1 1 1
o(a) 4 4 2 2 4 4 2
Vemos que en ning un caso es o(a) = (20) = 8. Por tanto, 20 no tiene
races primitivas.
51
7. Que enteros tienen orden 6 (mod 31)?.
Como 6|(311), sabemos que hay (6) = 2 restos (mod 31) cuyo orden
es 6. Haciendo pruebas, encontramos que uno es a = 6: 6
2
= 5, 6
3
= 30,
6
4
= 25, 6
5
= 26, 6
6
= 1. El otro, lo podemos encontrar sabiendo que
es de la forma 6
k
con (k,6)=1, es decir, 6
5
= 26.
8. Que enteros tienen orden 6 (mod 37)?.
Como 6|(371), sabemos que hay (6) = 2 restos (mod 37) cuyo orden
es 6. Haciendo pruebas, encontramos que uno es a = 11: 11
2
= 10,
11
3
= 36, 11
4
= 26, 11
5
= 27, 11
6
= 1. El otro, lo podemos encontrar
sabiendo que es de la forma 11
k
con (k,6)=1, es decir, 11
5
= 27.
9. Si a, a = 1, tiene orden t (mod p), demostrar que
a
t1
+ a
t2
+ + 1 = 0 (mod p).
Recordemos la formula a
t
1 = (a 1)(a
t1
+ a
t2
+ + 1). Si a
tiene orden t, la parte izquierda es cero modulo p, por lo que p divide
a alguno de los parentesis de la parte derecha, y p no puede dividir a
a 1, porque entonces el orden de a sera 1.
10. Si g y h son dos races primitivas de un primo impar p, entonces
g h
k
(mod p) para alg un entero k. Demostrar que k es impar.
Supongamos que k es par. Entonces
g
p1
2
= (h
k
)
p1
2
= (h
p1
)
k
2
= 1 (mod p),
en contra de que g es una raz primitiva y p 1 es el menor exponente
al que tenemos que elevar g para obtener 1 (mod p).
11. Demostrar que si g y h son races primitivas de un primo p,
entonces el resto de gh no es una raz primitiva de p.
Seg un se ha visto en el ejercicio anterior, si gh fuera una raz primitiva
de p, podra expresarse gh = g
k
para un cierto k que, ademas debe
ser impar. Pero entonces, tenemos h = g
k1
, teniendo que ser k 1
tambien impar, lo cual es imposible.
12. Si g, h y k son races primitivas de p, es siempre el resto de
ghk una raz primitiva de p?
52
No. Por ejemplo, para p = 19, hemos visto en el ejercicio 3 que 2, 3 y
14 son races primitivas. Su producto es 8, que no es una raz primitiva.
13. Demostrar que si a tiene orden 3 (mod p), entonces a+1 tiene
orden 6 (mod p).
Por tener a orden 3 (mod p), cumple a
3
1 0 (mod p). Por tanto,
a
2
+ a + 1 0 (mod p) y
(a + 1)
3
= a
3
+ 3a
2
+ 3a + 1 3(a
2
+ a) + 2 1 (mod p).
De aqu (a + 1)
6
1 (mod p) y el orden de a + 1 debe ser un divisor
de 6. El orden de a + 1 no puede ser 1, pues en ese caso,
a + 1 1 (mod p) a 1 (mod p) a
3
1 (mod p),
en contra de la hipotesis. Si el orden de a + 1 fuera 2, tendramos
(a+1)
2
1 (mod p) a
2
+2a+1 1 (mod p) a
2
+2a 0 (mod p),
y, teniendo en cuenta que a
2
+ a 1 (mod p), nos lleva a a 1
0 (mod p), lo cual es imposible si a tiene orden 3. La unica posibilidad
que queda es que el orden de a + 1 sea 6.
14. Si p y q son primos impares y q|a
p
+ 1, demostrar que o q|a + 1
o q = 2kp + 1 para alg un entero k.
Como q|a
p
+ 1 a
p
1 (mod p) (a)
p
1 (mod p), el orden de
a (mod p), debe ser un divisor de p: 1 o p. Si el orden de a es 1,
entonces a 1 (mod p) a + 1 0 (mod p) p divide a a + 1.
Si el orden de a es p, entonces, p divide a q 1 = (q), por lo que
q = 1 + rp para alg un entero r. Como p y q son impares, r debe ser
par, resultando que q = 1 + 2kp para alg un entero k.
15. Suponiendo que a tiene orden 4 (mod p), cual es el resto de
(a + 1)
4
(mod p)?.
Como a
4
1 = (a1)(a+1)(a
2
+1, obtenemos que a
2
1 y a
3
a,
por lo que (a + 1)
4
= a
4
+ 4a
3
+ 6a
2
+ 4a + 1 = 1 4a 6 + 4a + 1 =
4 = p 4 (mod p).
53
16. Demostrar que 131071 = 2
17
1 es primo.
Como ning un primo impar p divide a 2 1, un primo p que divida a
2
17
1 debe ser de la forma 2 17k +1 = 34k +1. Los valores de 34+1,
primos y menores que

131071 362,07 son 103, 137, 239, 273, 307.

Al dividir 131071 por estos n umeros obtenemos de resto, 55, 99, 99, 31,
289, respectivamente. Por tanto, el n umero 131071 es primo.
17. Demostrar que (2
19
+ 1)/3 es primo.
Usaremos que si un primo p divide a 2
19
+1, entonces p|2 +1 o p es de
la forma p = 38k + 1. Los n umeros de la forma 38k + 1 menores que

174763 418,047 son 39, 77, 115, 153, 191, 229, 267, 305, 343, 381,
de los cuales son primos solo 191 y 229. Como al dividir 174763 por
estos n umeros obtenemos restos no nulos (189 y 36, respectivamente),
el n umero (2
19
+ 1)/3 es primo.
18. Demostrar que si g es una raz primitiva de p, entonces hay dos
potencias consecutivas de g que tienen restos consecutivos. Es
decir, demostrar que existe k tal que g
k+1
g
k
+ 1 (mod p).
Consideremos los restos de los n umeros de la forma g
k+1
g
k
= g
k
(g1),
(1 k p 1).
Estos n umeros son todos distintos (mod p): Sea 1 r < s p 1
y g
r
(g 1) g
s
(g 1) (mod p). Entonces g
r
g
s
(mod p) y g
sr

1 (mod p), en contra de que g es una raz primitiva de p.

Como p no divide a ninguno de los n umeros g
k
(g 1), nunca es g
k+1

g
k
0 (mod p), por lo que para cada 1 t p 1 existira alg un k
tal que g
k+1
g
k
t (mod p), en particular para t = 1, que es lo que
queremos probar.
Como ejemplo, consideremos lo que ocurre con p = 11 y g = 6:
k 1 2 3 4 5 6 7 8 9 10
g
k
6 3 7 9 10 5 8 4 2 1
g
k+1
g
k
3 4 2 1 5 3 4 2 1 5
En este caso tenemos g
5
= g
4
+ 1 (mod 11).
54
19. Demostrar que si g es una raz primitiva de p, entonces no
hay tres potencias consecutivas de g que tengan restos conse-
cutivos. Es decir, demostrar g
k+2
g
k+1
+1 g
k
+2 (mod p) es
imposible para cualquier k.
Suponiendo que fuera cierto tendramos g
k+1
(g1) g
k
(g1) (mod p)
y de ah, g
k+1
g
k
(mod p), lo cual es imposible.
20. a) Demostrar que si m es un n umero con races primitivas,
entonces el producto de enteros menores o iguales que m
y primos relativos con m es congruente con 1 (mod m).
b) Demostrar que el resultado de a) no es siempre cierto si
m no tiene races primitivas.
a) Si m tiene una raz primitiva g, g, g
2
, . . . , g
(m)
son una permu-
tacion de los (m) enteros positivos r
1
, r
2
, . . . , r
(m)
menores que
m y primos relativos con m y son races del polinomio x
(m)

1 (mod p). Entonces,

x
(m)
1 (mod p) = (x r
1
)(x r
2
) (x r
(m)
) (mod p).
Sustituyendo por x = 0, y teniendo en cuenta que (m) es par,
obtenemos r
1
r
2
r
(m)
1 (mod p).
b) Para m = 8, tenemos 1
2
3
2
5
2
7
2
1 (mod 8), por lo que
ninguno de los ordenes de 1, 3, 5, y 7 es 4 = (8) y 8 no tiene
races primitivas. En este caso tenemos 1 3 5 7 = 1 (mod 8).
55
11. Congruencias cuadraticas
1. Cuales de las siguientes congruencias tiene solucion?
x
2
7 (mod 53) x
2
14 (mod 31)
x
2
53 (mod 7) x
2
25 (mod 997)
a) Seg un el criterio de Euler, la congruencia x
2
7 (mod 53) tiene
alguna solucion si y solo si 7
26
1 (mod 53). Hallamos 7
2
=
49 = 4 (mod 53), 7
4
= 16 (mod 53), 7
8
= 256 = 9 (mod 53),
7
12
= 144 = 15 (mod 53), 7
13
= 105 = 1 (mod 53), 7
26
=
1 (mod 53).
b) x
2
53 (mod 7) x
2
4 (mod 7), que tiene una solucion evi-
dente: x = 2.
Observacion: Como 53 1 (mod 3), el teorema de reciprocidad cua-
dratica nos dice esta congruencia tiene solucion si y solo si la tiene
la congruencia del apartado anterior. Usando el smbolo de Legendre,
podamos haber respondido a los dos apartados con los calculos:
_
7
53
_
=
_
53
7
_
=
_
4
7
_
=
_
2
2
7
_
= 1.
c) Seg un el criterio de Euler, la congruencia x
2
14 (mod 31) ten-
dra una solucion si y solo si 14
15
1 (mod 31). Como 2
5
= 32
1 (mod 31), entonces 2
15
1 (mod 31). Ahora calculamos unas
pocas potencias de 7 (mod 31) : 7
2
= 49 18, 7
4
324 14,
7
8
196 10, 7
16
100 7 7
15
1 (mod 31). Por tanto, la
congruencia tiene solucion.
Usando el smbolo de Legendre llegamos al mismo resultado de
una forma mas rapida y sencilla:
_
14
31
_
=
_
2
31
__
7
31
_
= 1
_

_
31
7
__
=
=
_
3
7
_
=
_
7
3
_
=
_
1
3
_
= 1.
d) Observando que 25 = 5
2
es un cuadrado, x 5 es una solucion
inmediata de la congruencia x
2
25 (mod 997).
56
2. Cuales de las siguientes congruencias tiene solucion?
x
2
8 (mod 53) x
2
15 (mod 31)
x
2
54 (mod 7) x
2
625 (mod 9973)
a) Hallemos 8
26
(mod 53) y usemos el criterio de Euler. Tenemos
8
2
= 64 11 (mod 53), 8
4
121 15 (mod 53), 8
6
= 165
6 (mod 53), 8
12
36 (mod 53), 8
13
288 23 (mod 53), 8
26

529 1 (mod 53). Seg un el criterio de Euler, esta congruencia

no tiene solucion. El mismo resultado se obtiene usando el smbolo
de Legendre:
_
2
53
_
= 1
_
8
53
_
=
_
2
3
53
_
=
_
2
53
_
3
= (1)
3
= 1.
b) La congruencia x
2
54 (mod 7) no tiene ninguna solucion, como
podemos ver facilmente usando el smbolo de Legendre:
_
54
7
_
=
_
5
7
_
=
_
7
5
_
=
_
2
5
_
= 1.
c) Lo mismo le ocurre a la congruencia x
2
15 (mod 31):
_
15
31
_
=
_
3
31
_

_
5
31
_
=
_
31
3
_

_
31
5
_
=
_
1
3
_

_
1
5
_
= 1.
d) Observando que 625 = 25
2
es un cuadrado, x 25 es una solucion
inmediata de la congruencia x
2
625 (mod 9973).
3. Encontrar soluciones de las congruencias del Problema 1 que
las tengan.
Para resolver x
2
7 (mod 53), tenemos en cuenta que 7 60 113
166 219 272 325 378 431 484 = 22
2
(mod 53) Las
soluciones son x = 22 y x = 31 (mod 53).
De x
2
53 (mod 7), que es equivalente a x
2
4 (mod 7), la soluciones
son evidentemente x = 2 y x = 5 (mod 7).
Para resolver x
2
14 (mod 31), tenemos en cuenta que 14 45
76 107 138 169 = 13
2
(mod 31). Las soluciones son x = 13 y
x = 18 (mod 31).
Por ultimo la soluciones de x
2
25 (mod 997) son x = 5 y x =
992 (mod 997).
57
4. Encontrar soluciones de las congruencias del Problema 2 que
las tengan.
La unica congruencia con solucion es x
2
625 (mod 9973), y sus solu-
ciones son x = 25 y x = 9948 (mod 9973).
5. Calcular (33/71), (34/71), (35/71), (36/71).
a)
(33/71) =(3/71)(11/71) = (71/3) [(71/11)] =
=(2/3) (5/11) = (1) (11/5) = (1) 1 = 1.
b)
(34/71) =(2/71)(17/71) = 1 (71/17) =
=(3/17) = (17/3) = (2/3) = 1.
c)
(35/71) =(5/71)(7/71) = (71/5) [(71/7)] =
=(1/5) (1/7) = 1 1 = 1.
d) (36/71) = (6
2
/71) = 1.
6. Calcular (33/73), (34/73), (35/73), (36/73).
a)
(33/73) =(3/73)(11/73) = (73/3) (73/11) =
=(1/3) (7/11) = 1 [(11/7)] = (4/7) = 1.
b)
(34/73) =(2/73)(17/73) = 1 (73/17) =
=(5/17) = (17/5) = (2/5) = 1.
c)
(35/73) =(5/73)(7/73) = (73/5) (73/7) = (3/5) (3/7) =
=(5/3) [(7/3)] = (2/3)(4/3) = 1.
d) (36/73) = (6
2
/73) = 1.
7. Resolver 2x
2
+ 3x + 1 = 0 (mod 7) y 2x
2
+ 3x + 1 = 0 (mod 101).
a) Multiplicando 2x
2
+3x+1 0 (mod 7) por 4, resulta, x
2
+5x+4
0 (mod 7), que es equivalente a x
2
+ 12x + 4 0 (mod 7). Ahora
completamos cuadrados: x
2
+12x+36 32 (mod 7) (x+6)
2

4 mod 4 x + 6 2. Hay dos soluciones x 4 y x 8, o

x 3 y x 6.
58
b) Multiplicamos 2x
2
+ 3x + 1 = 0 (mod 101) por 51 y obtenemos
la congruencia x
2
+ 52x + 51 0 (mod 101). Ahora completa-
mos cuadrados: x
2
+ 52x + 676 625 (mod 101) (x + 26)
2

25
2
(mod 101) x+26 25 (mod 101). Las soluciones son x =
1 y x = 51 (mod 101), es decir x = 50 y x = 100 (mod 101).
8. Resolver 3x
2
+ x + 8 0 (mod 11) y 3x
2
+ x + 52 0 (mod 11).
a) Multiplicamos 3x
2
+ x + 8 0 (mod 11) por 4 para obtener
x
2
+ 4x + 10 0 (mod 11) y ahora completamos cuadrados: x
2
+
4x + 4 5 (mod 11) o (x + 2)
2
5 (mod 11) (x + 2)
2

16 (mod 11) x + 2 4 (mod 11). Las soluciones son x 2 y

x 5 (mod 11).
b) 3x
2
+ x + 52 0 (mod 11) y 3x
2
+ x + 52 0 (mod 11) son
congruencias equivalentes, por lo que 3x
2
+ x + 52 0 (mod 11)
tambien tiene por soluciones x 2 y x 5 (mod 11).
9. Calcular (1234/4567) y (4321/4567).
(1234/4567) =(2/4567) (617/4567) = 1 (4567/617) = (248/617) =
=(8/617) (31/617) = 1
3
(617/31) = (28/31) =
=(7/31) = (31/7) = (3/7) = (7/3) = (1/3) = 1.
(4321/4567) =(29/4567) (149/4567) = (4567/29) (4567/149) =
=(14/29) (97/149) = (2/29) (7/29) (149/97) =
=1 (29/7) (52/97) = 1(1/7) (4/97) (13/97) =
=(13/97) = (97/13) = (6/13) = (2/13)(3/13) =
=(3/13) = (13/3) = (1/3) = 1.
10. Calcular (1356/2467) y (6531/2467).
(1356/2467) =(3/2467) (7/2467) (311/2467) =
=1 [(2467/3)] (2467/113) =
=(1/3) (94/113) = (2/113) (47/113) =
=(113/47) = (19/47) = +(47/19) = (9/19) = 1.
59
(6531/2467) =(3/2467) (7/2467) (311/2467) =
=[(2467/3)] [(2467/7)] [(2467/311)] =
=(1/3) (3/7) (290/311) =
= + (7/3) (2/311) (5/311) (29/311) =
=1 1 (311/5) (311/29) = (1/5) (21/29) =
=(3/29) (7/29) = (29/3) (29/7) = (2/3) (1/7) = 1.
11. Demostrar que si p = q+4a (p y q son primos impares), entonces
(p/q) = (a/q).
Si (p/q) = 1, la congruencia x
2
p (mod q) tiene una solucion x
0
.
Podemos considerar que x
0
es par, pues en caso contrario, podemos
tomar px
0
, que tambien es solucion. Llamando x
1
=
x
0
2
, tenemos que
x
2
1
=
x
2
0
4

p
4

pq
4
= a (mod q). Es decir, tambien es (a/q) = 1.
Partiendo ahora de (a, q) = 1, x
2
a (mod q) tiene una solucion x
1
.
Llamando x
0
= 2x
1
, x
2
0
= 4x
2
1
4a q + 4a = p (mod q). Conclusion:
(p/q) = 1.
12. Demostrar que si p = 12k + 1 para alg un k, entonces (3/p) = 1.
Usamos el smbolo de Legendre: (3/p) = (p/3) = (1/3) = 1.
13. Demostrar que el teorema 6 puede expresarse tambien dicien-
do que (2/p) = (1)
p
2
1
8
para cualquier primo impar p.
El teorema 6 dice que (2/p) = 1 si p = 1, 7 (mod 8) y que (2/p) = 1
si p = 3, 5 (mod 8). Si p = 1, 7 (mod 8), entonces p = 1 (mod 8), por
lo que p = 8k1 para alg un k y p
2
1 = 64k
2
16k
p
2
1
8
= 8k
2
2k
es par. Si p = 3, 5 (mod 8), p = 3 (mod 8, por lo que p = 8k 3 para
alg un k. Entonces p
2
1 = 64k
2
48k + 8 y
p
2
1
8
= 8k
2
6k + 1 es
impar.
14. Demostrar que el teorema de reciprocidad cuadratica tambien
puede escribirse
_
p
q
__
q
p
_
= (1)
p1
2

q1
2
,
siendo p y q primos impares.
60
Basta tener en cuenta que cuando p es un primo impar,
p1
2
es par si
p 1 (mod 4) e impar si p 3 (mod 4).
Si p, q 3 (mod 4) los smbolos (p/q) y (q/p) son opuestos, por lo
que su producto es 1. Como
p1
2
y
q1
2
son impares, tambien lo es el
producto de ambos, as que (1)
p1
2

q1
2
= 1.
Si p 1 (mod 4) o q 1 (mod 4), alguno de los n umeros
p1
2
o
q1
2
sera par, as que tambien lo sera el producto de ambos y tendremos
(1)
p1
2

q1
2
= 1, que coincide con el valor de (p/q)(q/p), ya que en este
caso los smbolos son iguales.
15. El estudiante A dice: He comprobado todos los n umeros has-
ta el 100 y todava no he encontrado ning un n tal que n
2
+ 1
sea divisible por 7. Ahora estoy cansado, as que ya encon-
trare uno ma nana. El estudiante B, despues de unos pocos
segundos pensando, dice: No, no lo encontraras. Como lo
supo B tan rapidamente?
Como (1/7) = 1, 1 no es un residuo cuadratico modulo 7 y la
congruencia x
2
1 (mod 7) no tiene solucion.
16. Demostrar que si a es un residuo cuadratico (mod p) y ab =
1 (mod p), entonces b es un residuo cuadratico (mod p).
Usando el smbolo de Legendre, si a es un residuo cuadratico (mod p),
tendremos (a/p) = 1. Entonces
_
b
p
_
=
_
a
p
__
b
p
_
=
_
ab
p
_
=
_
1
p
_
= 1,
por lo que b tambien es un residuo cuadratico (mod p).
17. Tiene x
2
= 211 (mod 159) alguna solucion? Observar que 159
no es primo.
Como, 153 = 3 53, es equivalente al sistema
_
x
2
= 211 (mod 3)
x
2
= 211 (mod 53)
,
_
x
2
= 1 (mod 3)
x
2
= 52 (mod 53)
,
_
x = 2 (mod 3)
x
2
= 52 (mod 53)
Como (1/3) = 1 = (1/53), las dos ecuaciones tienen solucion por
separado. Teniendo en cuenta que 52 105 158 211 264
61
317 370 423 476 529 = 23
2
(mod 53), x = 23 es solucion de
la segunda ecuacion, resultando tambien solucion de la primera. Otras
soluciones son 76, 83 y 136.
18. Demostrar que si p 3 (mod 8) y
p1
2
es primo, entonces
p1
2
es un residuo cuadratico (mod p).
Sea q =
p1
2
. Como p = 8k + 3 para alg un k, q es de ka forma 4k + 1.
Ademas, es p = 2q + 1. Por todo ello, (q/p) = (p/q) = (1/q) = 1,
as que q es un residuo cuadratico (mod p).
19. Generalizar el problema 16 con condiciones sobre r que garan-
ticen que si a es un resto cuadratico (mod p) y ab r (mod p),
entonces b es un resto cuadratico (mod p).
Supongamos que r es un residuo cuadratico (mod p), en cuyo caso
tendremos (r/p) = 1. Si a es un residuo cuadratico (mod p) y ab
r (mod p),
_
b
p
_
=
_
a
p
__
b
p
_
=
_
ab
p
_
=
_
r
p
_
= 1,
por lo que b tambien es un residuo cuadratico (mod p). La condicion
(r/p) = 1 es entonces suciente. Evidentemente, tambien es necesaria
pues si a y b son residuos cuadraticos
20. Supongamos que p = q + 4a, donde p y q son primos impares.
Demostrar que (a/p) = (a/q).
62
12. Reciprocidad cuadratica
1. Adaptar el metodo usado en el texto para evaluar (2/p) para
evaluar (3/p).
Hay que contar cuantos n umeros a hay tales que
p1
2
< 3a < p, o
bien, tales que,
p1
6
< a <
p
3
(en los casos en que 3a > p, nunca es
3a > p +
p1
2
, as que 3a no produce un resto mayor que
p1
2
).
Sea entonces g el n umero de n umeros a que cumplen
p1
6
< a <
p
3
, y
tendremos entonces que (3/p) = (1)
g
.
Sea p = 12k + 1. Entonces
p1
6
= 2k y
p
3
= 4k +
1
3
. Debe ser 2k < a <
4k+
1
3
, es decir, 2k+1 a 4k. En este caso g = 4k(2k+1)+1 = 2k
y (3/p) = 1.
Sea p = 12k + 5. Entonces
p1
6
= 2k +
2
3
y
p
3
= 4k +
5
3
. Debe ser
2k +
2
3
< a < 4k +
5
3
, es decir, 2k + 1 a 4k + 1. En este caso
g = (4k + 1) (2k + 1) + 1 = 2k + 1 y (3/p) = 1.
Sea p = 12k + 7. Entonces
p1
6
= 2k + 1 y
p
3
= 4k +
7
3
. Debe ser
2k + 1 < a < 4k +
7
3
, es decir, 2k + 1 a 4k + 2. En este caso
g = (4k + 2) (2k + 2) + 1 = 2k + 1 y (3/p) = 1.
Sea p = 12k + 11. Entonces
p1
6
= 2k +
5
3
y
p
3
= 4k +
11
3
. Debe ser
2k +
5
3
< a < 4k +
11
3
, es decir, 2k + 2 a 4k + 3. En este caso
g = (4k + 3) (2k + 2) + 1 = 2k + 2 y (3/p) = 1.
Entonces, podemos expresar:
_
3
p
_
=
_
1 si p 1 (mod 12)
1 si p 5 (mod 12)
.
2. Demostrar que 3 es un no-residuo cuadratico de todos los
primos de la forma 4
n
+ 1.
Para cualquier n, es 4
n
+ 1 1 (mod 4) y 4
n
1 (mod 3). Por tanto,
_
3
4
n
+ 1
_
=
_
4
n
+ 1
3
_
=
_
2
3
_
= 1.
3. Demostrar que 3 es un no-residuo cuadratico de todos los
primos de Mersenne mayores que 3.
63
Si p > 2, 2
p
1 = 4 2
p2
1 = 4 (2
p2
1) + 3 3 (mod 4) y
2
p
2 (mod 3). Por tanto,
_
3
2
p
1
_
=
_
2
p
1
3
_
=
_
1
3
_
= 1.
4. a) Demostrar que si p 7 (mod 8), entonces p|(2
(p1)/2
1).
b) Encontrar un factor de 2
83
1.
a) p|(2
(p1)/2
1) 2
(p1)/2
1 (mod p) (2/p) = 1. Siempre
que p 7 (mod 8), tenemos que (2/p) = 1, as que entonces
p|(2
(p1)/2
1).
b) Haciendo que
p1
2
= 83, obtenemos p = 167, as que p = 167 es
un factor de 2
83
1.
5. a) Si p = y q = 10p + 3 son primos impares, demostrar que
(p/q) = (3/p).
b) Si p = y q = 10p + 1 son primos impares, demostrar que
(p/q) = (1/p).
a) Si p 1 (mod 4), entonces (p/q) = (q/p). Si p 3 (mod 4),
10p + 3 33 1 (mod 4) y tambien es (p/q) = (q/p). Por tanto,
tenemos que (p/q) = (q/p) = (3/p).
b) Si p 1 (mod 4), (p/q) = (q/p) = (1/p) = 1 = (1/p).
Si p 3 (mod 4), (p/q) = (q/p) = (1/p) = 1 = (1/p).
6. a) Que primos pueden dividir a n
2
+ 1 para alg un n?
b) Que primos pueden dividir a n
2
+ n para alg un n?
c) Que primos pueden dividir a n
2
+ 2n + 2 para alg un n?
a) Aquellos para los que x
2
1 (mod p) tiene solucion es decir,
aquellos para los que (1/p) = 1. Entonces son los p 3 (mod 4).
b) Es evidente que cualquier primo p divide a n
2
+ n siendo n = p,
as que la respuesta en este caso es Todos los primos.
c) n
2
+2n+2 0 (mod p) n
2
+2n+1 = 1 (mod p) (n+1)
2

1 (mod p). Tambien son los p 3 (mod 4).

64
7. a) Demostrar que si p 3 (mod 4) y a es un residuo cuadra-
tico (mod p), entonces p a es un no-residuo cuadratico
(mod p).
b) Que ocurre si p 1 (mod 4)?
a)
_
p a
p
_
=
_
a
p
_
=
_
a
p
__
1
p
_
=
_
a
p
_
= 1
b)
_
p a
p
_
=
_
a
p
_
=
_
a
p
__
1
p
_
= 1 1 = 1.
8. Si p > 3, demostrar que p divide a la suma de sus residuos
cuadraticos que tambien son restos.
Los residuos cuadraticos a
1
, . . . , a
r
, con r =
p1
2
que son restos pueden
considerarse cuadrados de los n umeros 1, . . . , r. Usando la formula
1
2
+ 2
2
+ + n
2
=
n
3
3
+
n
2
2
+
n
6
=
n(n + 1)(2n + 1)
6
,
obtenemos
a
1
+ + a
r
=
r(r + 1)(2r + 1)
6
=
(p 1)(p + 1)p
24
0 (mod p).
9. Si p es un primo impar, evaluar
(1 2/p) + (2 3/p) + + ((p 2) (p 1)/p).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1
1 -1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1
10. Demostrar que si p 1 (mod 4), entonces x
2
1 (mod p)
tiene una solucion dada por el resto (mod p) de ((p 1)/2)!.
65