Algoritmo di Euclide

Scrivi il procedimento per ogni esercizio.

1.
Nell'algoritmo di Euclide scrivi $a = q \times b + r$ con $0 \le r < b$ . Quale coppia dividi dopo?
1. a) $(a, b - r)$
2. b) $(b, r)$
3. c) $(q, r)$
4. d) $(a, r)$
Risposta: $(b, r)$
La coppia successiva è $(b, r)$ , perché $\text{MCD}(a, b) = \text{MCD}(b, r)$ . Il numero $a$ non serve più.
2.
Qual è il resto della divisione di $245$ per $63$ ?
Risposta: 56
$245 = 3 \times 63 + 56$ , perché $63 \times 3 = 189$ e $245 - 189 = 56$ . Il resto $56$ è più piccolo di $63$ , come deve essere.
3.
L'algoritmo di Euclide per $60$ e $42$ dà $60 = 1 \times 42 + 18$ , $42 = 2 \times 18 + 6$ , $18 = 3 \times 6 + 0$ . Quanto vale $\text{MCD}(60, 42)$ ?
1. a) $6$
2. b) $0$
3. c) $18$
4. d) $2$
Risposta: $6$
Il resto diventa $0$ nella riga $18 = 3 \times 6 + 0$ , quindi il MCD è il divisore di quella riga: $6$ . Non $0$ (il segnale di stop) e non $3$ (un quoziente).
4.
Calcola $\text{MCD}(56, 21)$ con l'algoritmo di Euclide.
Risposta: 7
1. Qual è il resto della divisione di $56$ per $21$ ? 14
2. Qual è il resto della divisione di $21$ per $14$ ? 7
3. Qual è il resto della divisione di $14$ per $7$ ? 0
4. Quanto vale quindi $\text{MCD}(56, 21)$ ? 7
5.
Con il metodo delle sottrazioni su $30$ e $12$ ottieni $30 - 12 = 18$ , $18 - 12 = 6$ , $12 - 6 = 6$ , $6 - 6 = 0$ . Quanto vale $\text{MCD}(30, 12)$ ?
Risposta: 6
La coppia finisce come $(6, 6)$ , quindi $\text{MCD}(30, 12) = 6$ . Le due sottrazioni di $12$ sono la divisione $30 = 2 \times 12 + 6$ .
6.
Quale coppia di numeri è formata da numeri primi tra loro (MCD $= 1$ )?
1. a) $(12, 18)$
2. b) $(15, 28)$
3. c) $(22, 33)$
4. d) $(14, 21)$
Risposta: $(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$ . Le altre hanno in comune $7$ , $6$ e $11$ .
7.
Calcola $\text{MCD}(252, 105)$ con l'algoritmo di Euclide.
Risposta: 21
1. Qual è il resto della divisione di $252$ per $105$ ? 42
2. Qual è il resto della divisione di $105$ per $42$ ? 21
3. Qual è il resto della divisione di $42$ per $21$ ? 0
4. Quanto vale quindi $\text{MCD}(252, 105)$ ? 21
8.
Usa l'algoritmo di Euclide per calcolare $\text{MCD}(391, 299)$ .
Risposta: 23
$391 = 1 \times 299 + 92$ , $299 = 3 \times 92 + 23$ , $92 = 4 \times 23 + 0$ . Quindi $\text{MCD}(391, 299) = 23$ ( $391 = 17 \times 23$ , $299 = 13 \times 23$ ).
9.
Riduci $\frac{221}{247}$ ai minimi termini con l'algoritmo di Euclide.
Risposta: 17/19
1. Qual è il resto della divisione di $247$ per $221$ ? 26
2. Qual è il resto della divisione di $221$ per $26$ ? 13
3. $26 = 2 \times 13 + 0$ . Quanto vale quindi $\text{MCD}(221, 247)$ ? 13
4. Dividi il numeratore: quanto fa $221 \div 13$ ? 17
5. Dividi il denominatore: quanto fa $247 \div 13$ ? 19
10.
Calcola $\text{mcm}(45, 75)$ con l'algoritmo di Euclide e $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$ .
Risposta: 225
1. Qual è il resto della divisione di $75$ per $45$ ? 30
2. Qual è il resto della divisione di $45$ per $30$ ? 15
3. $30 = 2 \times 15 + 0$ . Quanto vale quindi $\text{MCD}(45, 75)$ ? 15
4. Quanto vale $\text{mcm}(45, 75) = \frac{45 \times 75}{15}$ ? 225
11.
Un numero $d$ divide sia $a$ sia $b$ , e $a = q \times b + r$ . Quale numero deve essere diviso anche da $d$ ?
1. a) $q$
2. b) $r$
3. c) $a + q$
4. d) $q + r$
Risposta: $r$
$r = a - q \times b$ . Se $d$ divide $a$ e $b$ , divide $a$ meno un multiplo di $b$ , quindi divide $r$ . Ecco perché $\text{MCD}(a, b) = \text{MCD}(b, r)$ .
12.
Un rettangolo misura $77$ per $28$ . Qual è il lato del quadrato più grande che lo ricopre esattamente, senza spazi e senza tagli?
Risposta: 7
$77 = 2 \times 28 + 21$ , $28 = 1 \times 21 + 7$ , $21 = 3 \times 7 + 0$ , quindi $\text{MCD}(77, 28) = 7$ : quadrati di lato $7$ , in tutto $11 \times 4 = 44$ .
13.
Una tavola di legno misura $96$ cm per $60$ cm. Viene tagliata in quadrati uguali più grandi possibile, senza scarti. Quanti quadrati ottieni?
Risposta: 40
1. Qual è il resto della divisione di $96$ per $60$ ? 36
2. Qual è il resto della divisione di $60$ per $36$ ? 24
3. Qual è il resto della divisione di $36$ per $24$ ? 12
4. $24 = 2 \times 12 + 0$ . Qual è il lato del quadrato più grande, in cm? 12
5. Quanti quadrati così ottieni dalla tavola? 40
14.
I numeri di Fibonacci $144$ e $89$ : applica l'algoritmo di Euclide e trova il loro MCD.
Risposta: 1
1. Qual è il resto della divisione di $144$ per $89$ ? 55
2. Qual è il resto della divisione di $89$ per $55$ ? 34
3. Qual è il resto della divisione di $55$ per $34$ ? 21
4. I resti continuano con $13, 8, 5, 3, 2, 1, 0$ . Quanto vale $\text{MCD}(144, 89)$ ? 1
15.
Per due numeri naturali qualsiasi $a$ e $b$ , a che cosa è uguale $\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$
Risposta: $a \times b$
$\text{MCD}(a, b) \times \text{mcm}(a, b) = a \times b$ . Per $4$ e $6$ : $2 \times 12 = 24 = 4 \times 6$ . Ecco perché $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$ .
16.
Calcola $\text{mcm}(126, 588)$ . Trova prima il MCD con l'algoritmo di Euclide.
Risposta: 1764
$588 = 4 \times 126 + 84$ , $126 = 1 \times 84 + 42$ , $84 = 2 \times 42 + 0$ , quindi il MCD è $42$ e il mcm è $\frac{126 \times 588}{42} = 126 \times 14 = 1764$ .
17.
Calcola $\text{MCD}(1309, 1001)$ con l'algoritmo di Euclide.
Risposta: 77
1. Qual è il resto della divisione di $1309$ per $1001$ ? 308
2. Ora dividi $1001$ per $308$ . Qual è il quoziente $q$ ? 3
3. E il resto in $1001 = 3 \times 308 + r$ ? 77
4. Qual è il resto della divisione di $308$ per $77$ ? 0
5. Quanto vale quindi $\text{MCD}(1309, 1001)$ ? 77
18.
Trova il MCD di $840$ , $1176$ e $1260$ : prima $\text{MCD}(840, 1176)$ , poi il MCD di quel risultato e $1260$ .
Risposta: 84
1. Qual è il resto della divisione di $1176$ per $840$ ? 336
2. Qual è il resto della divisione di $840$ per $336$ ? 168
3. $336 = 2 \times 168 + 0$ . Quanto vale quindi $\text{MCD}(840, 1176)$ ? 168
4. Qual è il resto della divisione di $1260$ per $168$ ? 84
5. $168 = 2 \times 84 + 0$ . Quanto vale quindi $\text{MCD}(168, 1260)$ ? 84