Algorithme d'Euclide

Nom:

Classe:

Date:

É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)$
2.
Quel est le reste de la division de $245$ par $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$
4.
Calcule $\text{PGCD}(56, 21)$ avec l'algorithme d'Euclide.
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)$ ?
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)$
7.
Calcule $\text{PGCD}(252, 105)$ avec l'algorithme d'Euclide.
8.
Utilise l'algorithme d'Euclide pour calculer $\text{PGCD}(391, 299)$ .
9.
Rends $\frac{221}{247}$ irréductible avec l'algorithme d'Euclide.
10.
Calcule $\text{PPCM}(45, 75)$ avec l'algorithme d'Euclide et $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$ .
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$
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 ?
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 ?
14.
Les nombres de Fibonacci $144$ et $89$ : applique l'algorithme d'Euclide et trouve leur PGCD.
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$
16.
Calcule $\text{PPCM}(126, 588)$ . Trouve d'abord le PGCD avec l'algorithme d'Euclide.
17.
Calcule $\text{PGCD}(1309, 1001)$ avec l'algorithme d'Euclide.
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$ .