Práctico Nº2: Máximo común divisor
Franco Golfieri
September 2024
1 Problemas
1.1 Máximo común divisor y algoritmo de Euclides
1. En cada uno de los siguientes casos calcule d = (a : b). Encuentre además una combinación lineal
d = ax + by de manera tal que el valor absoluto de x + y sea mı́nimo.
(a) a = 210, b = 567
(b) a = 480, b = −176
(c) a = 15 × 36, b = 15 × 22
(d) a = −26, b = 0
(e) a = 28, b = 756
(f) a = 318 + 1, b = 318 − 1
2. Si a es un número entero, determine los valores posibles de:
(a) (ka : kb) = k(a : b)
(a:b)
(b) ( ab : kb ) = k , suponiendo que k es un divisor común de a y b
(c) Si a y b son coprimos, entonces (a : bc) = (a, c)
3. Suponiendo que (a : b) = 14. Calcule los posibles valores de:
(a) (a:a+b)
(b) (5a:5b)
(c) (7a:14b)
4. Demuestre que (a2 + 3 : a2 − 2) = 1, cualquiera sea el entero a.
5. Sean a1 , a2 , . . . , an números enteros y sea d = (a1 : a2 : . . . : an ).
(a) Pruebe que existen enteros x1 , x2 , . . . , xn tales que d = a1 x1 + a2 x2 + . . . + an xn .
(b) Demuestre que ( xa11 : a2
x2 : ... : an
xn ) =1
(c) Exhiba un ejemplo de cuatro números coprimos -en el sentido de que los cuatro sea 1-, pero de
manera que cualquier par de ellos no lo sea
6. (a) Determine una progresión aritmética, de 20 términos, de manera que todos ellos sean múltiplos
de 4 y coprimos con 7.
(b) Como en a), pero ahora de forma tal que todos los términos sean múltiplos de 13 y la cifra de las
unidades de cada uno sea 1.
1
P
7. Calcule −50≤k≤50 (k : 15).
8. Si se toma un número natural n entre 1 y 10000. Cuál es el valor más probable de (n : 18)?
Una sucesión (a veces llamado secuencia) es una lista infinita de números que cumplen cierto patrón.
Por ejemplo, la sucesión de números naturales pares es: 2, 4, 6, . . ., la de númeoros múltiplos de 6 es
6, 12, 18, 24, . . .. También existen sucesiones que cada vez van aumentando de a cierto número cada
vez, estas son las llamadas sucesiones aritméticas. Por ejemplo, la sucesión: 2, 5, 8, 11, 14, . . . es una
sucesión artmética de amplitud 3. Notar que cada nuevo término de la sucesión se obtiene del anterior
sumandole 3.
Uno de los ejemplos más famosos de sucesiones, es la sucesión de Fibonacci. Esta sucesión se
obtiene de la siguiente forma. Los primeros dos términos son 0, 1. A partir de ahı́, cada nuevo término
se obtiene sumando los dos términos anteriores de la sucesión. Es decir, el tercer término de la sucesión
será 0 + 1 = 1. Por lo que nos queda de momento los términos 0, 1, 1. El cuárto término será la suma
del segundo y el tercero, es decir 1 + 1 = 2. El quinto la suma del tercero y el cuarto, es decir 1 + 2 = 3
y ası́ sucesivamente. Los primeros 8 términos de la sucesión son 0, 1, 1, 2, 3, 5, 8, 13.
9. Consideremos la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, . . . Demuestre que dos términos consecutivos
cualesquiera de la misma son coprimos.
10. La suma de dos números naturales m y n es 300 y su máximo común divisor es 25. Halle los posibles
valores de m y n (m < n). Resuelva un problema similar, sabiendo ahora que el máximo común divisor
es 6 y que el producto de los números es 648.
11. Pruebe que existen infinito pares (x, y) de números enteros tales que x + y = 100 y (x : y) = 5.
12. Demuestre las siguientes propiedades (c > 1; m, n ∈ N):
(a) Si m|n entonces cm − 1|cn − 1
(b) El resto de dividir cn − 1 por cm − 1 es cr − 1, donde r es el resto de dividir n por m.
(c) (cm − 1 : cn − 1) = c(m:n) − 1.
n
(d) Si m|n y m es impar entonces cm + 1|cn + 1.
13. Calcule el máximo común divisor de 22222222 y 222222222222.
14. Sea x un número racional tal que xm ∈ Z (m ∈ Z). Pruebe que x es entero.
15. Determine cuántos términos de la secuencia 198, 396, 594, . . . , 19800 son divisibles por 53. ¿ Y por 84?
16. Sean a y b dı́gitos. Demuestre que existe un múltiplo de 1557 cuyo desarrollo decimal termina en ab.
17. Sean a y b números naturales ¿ Cuántos puntos de coordenadas enteras hay en el segmento que une
en el plano a los puntos (0, b) y (a, 0)?
1.2 Resolución de ecuaciones diofánticas lineales
18. Resuelva las siguientes ecuaciones diofánticas:
(a) 30X+36Y=24
(b) 30X+36Y=4
(c) 41X-19Y=8
19. ¿ De cuántas maneras puede descomponerse a 834 como suma de dos números pares positivos, uno
múltiplo de 15 y otro múltiplo de 21?
2
20. Para adquirir ejemplares de dos libros, cuyos respectivos precios son 12 y 17.50 pesos, una escuela
dispone de 1680 pesos ¿ De cuántas maneras puede hacerse la operación, si debe comprarse por lo
menos un ejemplar de cada libro y debe gastarse todo el dinero?
21. Resuelva el siguiente sistema de ecuaciones diofánticas:
16x + 15y = 1
6x + 10y + 15z = 11
22. Dado un número natural n, se sabe que en la recta de ecuación 9x + 14y = n hay exactamente un
punto de coordenadas enteras y positivas. ¿ Cuál es el mayor valor posible de n?
