Algorithme d'Euclide

Écris ta démarche pour chaque exercice.

1.
Dans l'algorithme d'Euclide, tu écris $a = q \times b + r$ avec $0 \le r < b$ . Quel couple divises-tu ensuite ?
1. a) $(a, b - r)$
2. b) $(b, r)$
3. c) $(q, r)$
4. d) $(a, r)$
Réponse: $(b, r)$
Le couple suivant est $(b, r)$ , car $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ . Le nombre $a$ ne sert plus.
2.
Quel est le reste de la division de $245$ par $63$ ?
Réponse: 56
$245 = 3 \times 63 + 56$ , car $63 \times 3 = 189$ et $245 - 189 = 56$ . Le reste $56$ est bien plus petit que $63$ .
3.
L'algorithme d'Euclide pour $60$ et $42$ donne $60 = 1 \times 42 + 18$ , $42 = 2 \times 18 + 6$ , $18 = 3 \times 6 + 0$ . Combien vaut $\text{PGCD}(60, 42)$ ?
1. a) $6$
2. b) $0$
3. c) $18$
4. d) $2$
Réponse: $6$
Le reste devient $0$ à la ligne $18 = 3 \times 6 + 0$ , donc le PGCD est le diviseur de cette ligne : $6$ . Ni $0$ (le signal d'arrêt), ni $3$ (un quotient).
4.
Calcule $\text{PGCD}(56, 21)$ avec l'algorithme d'Euclide.
Réponse: 7
1. Quel est le reste de la division de $56$ par $21$ ? 14
2. Quel est le reste de la division de $21$ par $14$ ? 7
3. Quel est le reste de la division de $14$ par $7$ ? 0
4. Combien vaut donc $\text{PGCD}(56, 21)$ ? 7
5.
Avec la méthode des soustractions sur $30$ et $12$ , tu obtiens $30 - 12 = 18$ , $18 - 12 = 6$ , $12 - 6 = 6$ , $6 - 6 = 0$ . Combien vaut $\text{PGCD}(30, 12)$ ?
Réponse: 6
Le couple finit en $(6, 6)$ , donc $\text{PGCD}(30, 12) = 6$ . Les deux soustractions de $12$ forment la division $30 = 2 \times 12 + 6$ .
6.
Quel couple de nombres est formé de nombres premiers entre eux (PGCD $= 1$ ) ?
1. a) $(12, 18)$
2. b) $(15, 28)$
3. c) $(22, 33)$
4. d) $(14, 21)$
Réponse: $(15, 28)$
$28 = 1 \times 15 + 13$ , $15 = 1 \times 13 + 2$ , $13 = 6 \times 2 + 1$ , $2 = 2 \times 1 + 0$ : $\text{PGCD}(15, 28) = 1$ . Les autres ont les diviseurs communs $7$ , $6$ et $11$ .
7.
Calcule $\text{PGCD}(252, 105)$ avec l'algorithme d'Euclide.
Réponse: 21
1. Quel est le reste de la division de $252$ par $105$ ? 42
2. Quel est le reste de la division de $105$ par $42$ ? 21
3. Quel est le reste de la division de $42$ par $21$ ? 0
4. Combien vaut donc $\text{PGCD}(252, 105)$ ? 21
8.
Utilise l'algorithme d'Euclide pour calculer $\text{PGCD}(391, 299)$ .
Réponse: 23
$391 = 1 \times 299 + 92$ , $299 = 3 \times 92 + 23$ , $92 = 4 \times 23 + 0$ . Donc $\text{PGCD}(391, 299) = 23$ ( $391 = 17 \times 23$ , $299 = 13 \times 23$ ).
9.
Rends $\frac{221}{247}$ irréductible avec l'algorithme d'Euclide.
Réponse: 17/19
1. Quel est le reste de la division de $247$ par $221$ ? 26
2. Quel est le reste de la division de $221$ par $26$ ? 13
3. $26 = 2 \times 13 + 0$ . Combien vaut donc $\text{PGCD}(221, 247)$ ? 13
4. Divise le numérateur : combien fait $221 \div 13$ ? 17
5. Divise le dénominateur : combien fait $247 \div 13$ ? 19
10.
Calcule $\text{PPCM}(45, 75)$ avec l'algorithme d'Euclide et $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$ .
Réponse: 225
1. Quel est le reste de la division de $75$ par $45$ ? 30
2. Quel est le reste de la division de $45$ par $30$ ? 15
3. $30 = 2 \times 15 + 0$ . Combien vaut donc $\text{PGCD}(45, 75)$ ? 15
4. Combien vaut $\text{PPCM}(45, 75) = \frac{45 \times 75}{15}$ ? 225
11.
Un nombre $d$ divise à la fois $a$ et $b$ , et $a = q \times b + r$ . Quel nombre $d$ doit-il aussi diviser ?
1. a) $q$
2. b) $r$
3. c) $a + q$
4. d) $q + r$
Réponse: $r$
$r = a - q \times b$ . Si $d$ divise $a$ et $b$ , il divise $a$ moins un multiple de $b$ , donc il divise $r$ . C'est pourquoi $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ .
12.
Un rectangle mesure $77$ sur $28$ . Quel est le côté du plus grand carré qui le pave exactement, sans espace et sans découpe ?
Réponse: 7
$77 = 2 \times 28 + 21$ , $28 = 1 \times 21 + 7$ , $21 = 3 \times 7 + 0$ , donc $\text{PGCD}(77, 28) = 7$ : des carrés de côté $7$ , au nombre de $11 \times 4 = 44$ .
13.
Une planche mesure $96$ cm sur $60$ cm. On la découpe en carrés identiques les plus grands possibles, sans chute. Combien de carrés obtiens-tu ?
Réponse: 40
1. Quel est le reste de la division de $96$ par $60$ ? 36
2. Quel est le reste de la division de $60$ par $36$ ? 24
3. Quel est le reste de la division de $36$ par $24$ ? 12
4. $24 = 2 \times 12 + 0$ . Quel est le côté du plus grand carré, en cm ? 12
5. Combien de carrés de ce type obtiens-tu dans la planche ? 40
14.
Les nombres de Fibonacci $144$ et $89$ : applique l'algorithme d'Euclide et trouve leur PGCD.
Réponse: 1
1. Quel est le reste de la division de $144$ par $89$ ? 55
2. Quel est le reste de la division de $89$ par $55$ ? 34
3. Quel est le reste de la division de $55$ par $34$ ? 21
4. Les restes continuent : $13, 8, 5, 3, 2, 1, 0$ . Combien vaut $\text{PGCD}(144, 89)$ ? 1
15.
Pour deux entiers positifs quelconques $a$ et $b$ , à quoi est égal $\text{PGCD}(a, b) \times \text{PPCM}(a, b)$ ?
1. a) $a \times b$
2. b) $\frac{a}{b}$
3. c) $a + b$
4. d) $a - b$
Réponse: $a \times b$
$\text{PGCD}(a, b) \times \text{PPCM}(a, b) = a \times b$ . Pour $4$ et $6$ : $2 \times 12 = 24 = 4 \times 6$ . C'est pourquoi $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$ .
16.
Calcule $\text{PPCM}(126, 588)$ . Trouve d'abord le PGCD avec l'algorithme d'Euclide.
Réponse: 1764
$588 = 4 \times 126 + 84$ , $126 = 1 \times 84 + 42$ , $84 = 2 \times 42 + 0$ , donc le PGCD vaut $42$ et le PPCM $\frac{126 \times 588}{42} = 126 \times 14 = 1764$ .
17.
Calcule $\text{PGCD}(1309, 1001)$ avec l'algorithme d'Euclide.
Réponse: 77
1. Quel est le reste de la division de $1309$ par $1001$ ? 308
2. Divise maintenant $1001$ par $308$ . Quel est le quotient $q$ ? 3
3. Et le reste dans $1001 = 3 \times 308 + r$ ? 77
4. Quel est le reste de la division de $308$ par $77$ ? 0
5. Combien vaut donc $\text{PGCD}(1309, 1001)$ ? 77
18.
Calcule le PGCD de $840$ , $1176$ et $1260$ : d'abord $\text{PGCD}(840, 1176)$ , puis le PGCD de ce résultat et de $1260$ .
Réponse: 84
1. Quel est le reste de la division de $1176$ par $840$ ? 336
2. Quel est le reste de la division de $840$ par $336$ ? 168
3. $336 = 2 \times 168 + 0$ . Combien vaut donc $\text{PGCD}(840, 1176)$ ? 168
4. Quel est le reste de la division de $1260$ par $168$ ? 84
5. $168 = 2 \times 84 + 0$ . Combien vaut donc $\text{PGCD}(168, 1260)$ ? 84