Algoritmo de Euclides

Escribe el procedimiento de cada ejercicio.

1.
En el algoritmo de Euclides escribes $a = q \times b + r$ con $0 \le r < b$ . ¿Qué pareja divides a continuación?
1. a) $(a, b - r)$
2. b) $(b, r)$
3. c) $(q, r)$
4. d) $(a, r)$
Respuesta: $(b, r)$
La siguiente pareja es $(b, r)$ , porque $\text{MCD}(a, b) = \text{MCD}(b, r)$ . El número $a$ ya no hace falta.
2.
¿Cuál es el resto al dividir $245$ entre $63$ ?
Respuesta: 56
$245 = 3 \times 63 + 56$ , porque $63 \times 3 = 189$ y $245 - 189 = 56$ . El resto $56$ es menor que $63$ , como debe ser.
3.
El algoritmo de Euclides para $60$ y $42$ da $60 = 1 \times 42 + 18$ , $42 = 2 \times 18 + 6$ , $18 = 3 \times 6 + 0$ . ¿Cuánto vale $\text{MCD}(60, 42)$ ?
1. a) $6$
2. b) $0$
3. c) $18$
4. d) $2$
Respuesta: $6$
El resto se hace $0$ en la fila $18 = 3 \times 6 + 0$ , así que el MCD es el divisor de esa fila: $6$ . No es $0$ (la señal de parar) ni $3$ (un cociente).
4.
Calcula $\text{MCD}(56, 21)$ con el algoritmo de Euclides.
Respuesta: 7
1. ¿Cuál es el resto al dividir $56$ entre $21$ ? 14
2. ¿Cuál es el resto al dividir $21$ entre $14$ ? 7
3. ¿Cuál es el resto al dividir $14$ entre $7$ ? 0
4. Entonces, ¿cuánto vale $\text{MCD}(56, 21)$ ? 7
5.
Con la versión con restas para $30$ y $12$ obtienes $30 - 12 = 18$ , $18 - 12 = 6$ , $12 - 6 = 6$ , $6 - 6 = 0$ . ¿Cuánto vale $\text{MCD}(30, 12)$ ?
Respuesta: 6
La pareja termina como $(6, 6)$ , así que $\text{MCD}(30, 12) = 6$ . Las dos restas de $12$ son la división $30 = 2 \times 12 + 6$ .
6.
¿Qué pareja de números es de primos entre sí (MCD $= 1$ )?
1. a) $(12, 18)$
2. b) $(15, 28)$
3. c) $(22, 33)$
4. d) $(14, 21)$
Respuesta: $(15, 28)$
$28 = 1 \times 15 + 13$ , $15 = 1 \times 13 + 2$ , $13 = 6 \times 2 + 1$ , $2 = 2 \times 1 + 0$ : $\text{MCD}(15, 28) = 1$ . Las otras comparten $7$ , $6$ y $11$ .
7.
Calcula $\text{MCD}(252, 105)$ con el algoritmo de Euclides.
Respuesta: 21
1. ¿Cuál es el resto al dividir $252$ entre $105$ ? 42
2. ¿Cuál es el resto al dividir $105$ entre $42$ ? 21
3. ¿Cuál es el resto al dividir $42$ entre $21$ ? 0
4. Entonces, ¿cuánto vale $\text{MCD}(252, 105)$ ? 21
8.
Usa el algoritmo de Euclides para calcular $\text{MCD}(391, 299)$ .
Respuesta: 23
$391 = 1 \times 299 + 92$ , $299 = 3 \times 92 + 23$ , $92 = 4 \times 23 + 0$ . Así que $\text{MCD}(391, 299) = 23$ ( $391 = 17 \times 23$ , $299 = 13 \times 23$ ).
9.
Simplifica $\frac{221}{247}$ hasta la fracción irreducible con el algoritmo de Euclides.
Respuesta: 17/19
1. ¿Cuál es el resto al dividir $247$ entre $221$ ? 26
2. ¿Cuál es el resto al dividir $221$ entre $26$ ? 13
3. $26 = 2 \times 13 + 0$ . Entonces, ¿cuánto vale $\text{MCD}(221, 247)$ ? 13
4. Divide el numerador: ¿cuánto es $221 \div 13$ ? 17
5. Divide el denominador: ¿cuánto es $247 \div 13$ ? 19
10.
Calcula $\text{mcm}(45, 75)$ con el algoritmo de Euclides y $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$ .
Respuesta: 225
1. ¿Cuál es el resto al dividir $75$ entre $45$ ? 30
2. ¿Cuál es el resto al dividir $45$ entre $30$ ? 15
3. $30 = 2 \times 15 + 0$ . Entonces, ¿cuánto vale $\text{MCD}(45, 75)$ ? 15
4. ¿Cuánto vale $\text{mcm}(45, 75) = \frac{45 \times 75}{15}$ ? 225
11.
Un número $d$ divide a la vez a $a$ y a $b$ , y $a = q \times b + r$ . ¿A qué número tiene que dividir también $d$ ?
1. a) $q$
2. b) $r$
3. c) $a + q$
4. d) $q + r$
Respuesta: $r$
$r = a - q \times b$ . Si $d$ divide a $a$ y a $b$ , divide a $a$ menos un múltiplo de $b$ , así que divide a $r$ . Por eso $\text{MCD}(a, b) = \text{MCD}(b, r)$ .
12.
Un rectángulo mide $77$ por $28$ . ¿Cuál es el lado del cuadrado más grande que lo cubre exactamente, sin huecos y sin cortes?
Respuesta: 7
$77 = 2 \times 28 + 21$ , $28 = 1 \times 21 + 7$ , $21 = 3 \times 7 + 0$ , así que $\text{MCD}(77, 28) = 7$ : cuadrados de lado $7$ , en total $11 \times 4 = 44$ .
13.
Un tablero de madera mide $96$ cm por $60$ cm. Se corta en cuadrados iguales lo más grandes posible, sin que sobre nada. ¿Cuántos cuadrados obtienes?
Respuesta: 40
1. ¿Cuál es el resto al dividir $96$ entre $60$ ? 36
2. ¿Cuál es el resto al dividir $60$ entre $36$ ? 24
3. ¿Cuál es el resto al dividir $36$ entre $24$ ? 12
4. $24 = 2 \times 12 + 0$ . ¿Cuál es el lado del cuadrado más grande, en cm? 12
5. ¿Cuántos cuadrados así obtienes del tablero? 40
14.
Los números de Fibonacci $144$ y $89$ : aplica el algoritmo de Euclides y halla su MCD.
Respuesta: 1
1. ¿Cuál es el resto al dividir $144$ entre $89$ ? 55
2. ¿Cuál es el resto al dividir $89$ entre $55$ ? 34
3. ¿Cuál es el resto al dividir $55$ entre $34$ ? 21
4. Los restos siguen así: $13, 8, 5, 3, 2, 1, 0$ . ¿Cuánto vale $\text{MCD}(144, 89)$ ? 1
15.
Para dos números naturales cualesquiera $a$ y $b$ , ¿a qué es igual $\text{MCD}(a, b) \times \text{mcm}(a, b)$ ?
1. a) $a \times b$
2. b) $\frac{a}{b}$
3. c) $a + b$
4. d) $a - b$
Respuesta: $a \times b$
$\text{MCD}(a, b) \times \text{mcm}(a, b) = a \times b$ . Para $4$ y $6$ : $2 \times 12 = 24 = 4 \times 6$ . Por eso $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$ .
16.
Calcula $\text{mcm}(126, 588)$ . Halla primero el MCD con el algoritmo de Euclides.
Respuesta: 1764
$588 = 4 \times 126 + 84$ , $126 = 1 \times 84 + 42$ , $84 = 2 \times 42 + 0$ , así que el MCD es $42$ y el mcm es $\frac{126 \times 588}{42} = 126 \times 14 = 1764$ .
17.
Calcula $\text{MCD}(1309, 1001)$ con el algoritmo de Euclides.
Respuesta: 77
1. ¿Cuál es el resto al dividir $1309$ entre $1001$ ? 308
2. Ahora divide $1001$ entre $308$ . ¿Cuál es el cociente $q$ ? 3
3. ¿Y el resto en $1001 = 3 \times 308 + r$ ? 77
4. ¿Cuál es el resto al dividir $308$ entre $77$ ? 0
5. Entonces, ¿cuánto vale $\text{MCD}(1309, 1001)$ ? 77
18.
Halla el MCD de $840$ , $1176$ y $1260$ : primero $\text{MCD}(840, 1176)$ y después el MCD de ese resultado y $1260$ .
Respuesta: 84
1. ¿Cuál es el resto al dividir $1176$ entre $840$ ? 336
2. ¿Cuál es el resto al dividir $840$ entre $336$ ? 168
3. $336 = 2 \times 168 + 0$ . Entonces, ¿cuánto vale $\text{MCD}(840, 1176)$ ? 168
4. ¿Cuál es el resto al dividir $1260$ entre $168$ ? 84
5. $168 = 2 \times 84 + 0$ . Entonces, ¿cuánto vale $\text{MCD}(168, 1260)$ ? 84