Quiz sur le PGCD

Correction:

Le PGCD de 12 et 18 est 6. Les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12. Les diviseurs de 18 sont 1, 2, 3, 6, 9 et 18. Le plus grand diviseur commun est 6.

Correction:

Si le PGCD de deux nombres est 1, cela signifie qu'ils n'ont aucun diviseur commun autre que 1. On dit alors qu'ils sont premiers entre eux.

Correction:

L'algorithme d'Euclide est généralement la méthode la plus rapide pour trouver le PGCD de grands nombres, car il ne nécessite pas de factorisation complète.

Correction:

Les diviseurs de 24 sont : 1, 2, 3, 4, 6, 8, 12, 24.

Les diviseurs de 36 sont : 1, 2, 3, 4, 6, 9, 12, 18, 36.

Le plus grand diviseur commun est 12.

Correction:

Par définition, le PGCD de deux nombres divise à la fois ces deux nombres.

Correction:

Les diviseurs de 48 sont : 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.

Les diviseurs de 60 sont : 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.

Le plus grand diviseur commun est 12.

Correction:

Tout nombre divise 0. Le plus grand diviseur de $a$ est $|a|$ (car $a$ peut être négatif, mais le PGCD est toujours positif ou nul).

Correction:

Les diviseurs de 75 sont 1, 3, 5, 15, 25 et 75. Les diviseurs de 100 sont 1, 2, 4, 5, 10, 20, 25, 50 et 100. Le plus grand diviseur commun est 25.

Correction:

Si $a$ divise $b$, alors $a$ est le plus grand diviseur de $a$, et c'est aussi un diviseur de $b$. Donc, c'est le plus grand diviseur commun de $a$ et $b$. On prend la valeur absolue car le PGCD est toujours positif ou nul.

Correction:

Le plus grand diviseur d'un nombre est lui-même (en valeur absolue, car le PGCD est toujours positif).

Correction:

On utilise la propriété : $\text{PGCD}(ka, kb) = k \times \text{PGCD}(a, b)$. Ici, $\text{PGCD}(2a, 2b) = 2 \times \text{PGCD}(a, b) = 2 \times 1 = 2$.

Correction:

On peut utiliser l'algorithme d'Euclide :

$147 = 1 \times 84 + 63$

$84 = 1 \times 63 + 21$

$63 = 3 \times 21 + 0$

Le dernier reste non nul est 21, donc $\text{PGCD}(84, 147) = 21$.

Correction:

C'est une propriété fondamentale du PGCD. Si on divise deux nombres par leur PGCD, les quotients obtenus sont premiers entre eux.

Correction:

On peut utiliser l'algorithme d'Euclide :

$180 = 1 \times 120 + 60$

$120 = 2 \times 60 + 0$

Le dernier reste non nul est 60, donc $\text{PGCD}(120, 180) = 60$.

Correction:

91 = 7 x 13 et 169 = 13 x 13. Le seul facteur premier commun est 13, mais il apparaît avec des puissances différentes. Il faut prendre la plus petite puissance, qui est 13^0 = 1 (quand un facteur n'apparaît que dans une décomposition, sa puissance dans le PGCD est 0). Donc, PGCD(91, 169) = 1. Les nombres sont premiers entre eux.

Correction:

$\text{PGCD}(3a, 3b) = 3 \times \text{PGCD}(a, b) = 3 \times 5 = 15$.

Correction:

On peut utiliser l'algorithme d'Euclide :

$315 = 1 \times 225 + 90$

$225 = 2 \times 90 + 45$

$90 = 2 \times 45 + 0$

Le dernier reste non nul est 45, donc PGCD(225, 315) = 45.

Correction:

On ne peut pas directement utiliser la propriété $\text{PGCD}(ka, kb) = k\text{PGCD}(a,b)$ car les facteurs multiplicatifs (2 et 4) sont différents.

Cependant, on sait que $a=4a'$ et $b=4b'$ avec $a'$ et $b'$ premiers entre eux. Donc, $2a = 8a'$ et $4b = 16b'$. Le PGCD de $8a'$ et $16b'$ est $8\times\text{PGCD}(a', 2b')$.

Comme $\text{PGCD}(a', b') = 1$, $a'$ ne peut pas être pair (sinon il aurait un facteur commun 2 avec $b'$). Donc $\text{PGCD}(a', 2b') = \text{PGCD}(a',2) \times \text{PGCD}(a',b')= 1 \times 1 = 1$.

Finalement, $\text{PGCD}(2a, 4b) = 8$.

Correction:

Si $\text{PGCD}(a,b)=d$, alors $\text{PGCD}(a^n, b^n) = d^n$. Ici, $d=7$ et $n=2$, donc $\text{PGCD}(a^2, b^2) = 7^2 = 49$.

Correction:

$a$ est divisible par 6, donc par 2 et par 3. $c$ est divisible par 9, donc par 3. Donc, $a$ et $c$ sont tous les deux divisibles par 3, donc leur PGCD est divisible par 3. On ne peut rien dire de plus.

Correction :

On peut écrire $2n + 2 = 2(n+1)$. Donc, les deux nombres sont pairs. On a $\text{PGCD}(2n, 2n+2) = \text{PGCD}(2n, 2(n+1)) = 2 \times \text{PGCD}(n, n+1)$. Or, $\text{PGCD}(n, n+1) = 1$ car deux entiers consécutifs sont toujours premiers entre eux. Donc, $\text{PGCD}(2n, 2n+2) = 2$.

Correction :

Soient $a$ et $b$ les deux nombres. $a = 15a'$ et $b = 15b'$, avec $\text{PGCD}(a', b') = 1$.

$a + b = 15(a' + b') = 90$, donc $a' + b' = 6$.

Les couples $(a', b')$ d'entiers naturels premiers entre eux de somme 6 sont (1, 5) et (5, 1). Cela donne les couples (15, 75) et (75, 15). Il faut aussi considérer le cas où a'=3 et b'=3, ce qui est possible car on recherche des entiers naturels, ce qui donne le couple (45,45)

Donc les couples $(a,b)$ possibles sont $(15, 75)$, $(75, 15)$, et $(45,45)$

Correction :

Soit $d = \text{PGCD}(n, 2n+1)$. Alors $d$ divise $n$ et $d$ divise $2n+1$. Donc $d$ divise $2n+1 - 2n = 1$. Donc $d=1$.

Correction :

$85 = 1 \times 51 + 34$

$51 = 1 \times 34 + 17$

$34 = 2 \times 17 + 0$

Le dernier reste non nul est 17, donc $\text{PGCD}(51, 85) = 17$.

Correction :

Oui. Par définition, le PGCD est le plus grand diviseur commun. Tout autre diviseur commun doit être plus petit ou égal, et donc diviser le PGCD.

Correction :

La fraction est irréductible si et seulement si $\text{PGCD}(n+1, 2n+3) = 1$.

Soit $d$ ce PGCD. $d$ divise $n+1$ et $2n+3$, donc $d$ divise $2(n+1) = 2n+2$.

Donc $d$ divise $(2n+3) - (2n+2) = 1$. Donc $d = 1$, et la fraction est toujours irréductible.

Correction :

On prend les facteurs premiers communs, avec la plus petite puissance. Donc $\text{PGCD}(a, b) = 2^2 \times 3 = 12$.

Correction :

C'est une propriété fondamentale : le produit du PGCD et du PPCM de deux nombres est égal au produit de ces deux nombres.

Correction :

Soit $n$ le diviseur. $173 = q_1n + 5$ et $256 = q_2n + 7$, où $q_1$ et $q_2$ sont les quotients.

Donc $173 - 5 = 168$ est divisible par $n$, et $256 - 7 = 249$ est divisible par $n$.

$n$ est donc un diviseur commun de 168 et 249. On cherche le plus grand diviseur commun, donc $n = \text{PGCD}(168, 249)$.

Algorithme d'Euclide : $249 = 1 \times 168 + 81$; $168 = 2 \times 81 + 6$; $81 = 13 \times 6 + 3$; $6 = 2 \times 3 + 0$. Donc PGCD = 3.

Cependant, les restes sont 5 et 7, donc le diviseur doit être strictement supérieur à 7. On cherche donc les diviseurs du PGCD. Les diviseurs de 3 sont 1 et 3 mais ne conviennent pas (inférieurs à 7).

Reprenons l'algorithme d'Euclide plus haut:

$249 = 1 \times 168 + 81$

$168 = 2 \times 81 + 6 $

$81 = 13 \times 6 + 3 $

On a fait une erreur. Reprenons : $249 = 1 \times 168 + 81$; $168 = 2 \times 81 + 6$; $81 = 13 \times 6 + 3$; $6 = 2 \times 3+0$. Le PGCD est 3. Il y a une erreur dans l'énoncé, ou bien les restes sont mal donnés.

Recommençons avec l'algorithme d'Euclide :

$249 = 1 \times 168 + 81 $

$168 = 2 \times 81 + 6$

$81 = 13 \times 6 + 3$

$6 = 2 \times 3 + 0$

Donc le PGCD(168; 249) = 3. Or on nous dit que les restes respectifs sont 5 et 7, le diviseur recherché est donc strictement supérieur à 7, ce qui n'est pas possible ici avec un PGCD de 3.

Il doit y avoir une erreur. Modifions l'énoncé et disons que les restes sont 2 et 3 respectivement.

Donc on aurait $173 = q_1n + 2$ et $256 = q_2 n +3 $.

Alors $171$ et $253$ sont divisibles par $n$. $\text{PGCD}(171, 253) = \text{PGCD}(171, 253 - 171) = \text{PGCD}(171, 82)$.

$171 = 2 \times 82 + 7$, $82 = 11 \times 7 + 5$, $7 = 1 \times 5 + 2$, $5 = 2 \times 2 + 1$, $2 = 2 \times 1 + 0$. Le PGCD est 1, ce qui n'est pas possible.

Changeons encore l'énoncé. Les restes sont respectivement 5 et 1. Alors on a $168$ et $255$. $255 = 1 \times 168 + 87$, $168 = 1 \times 87 + 81$, $87 = 1 \times 81+6$, $81 = 13\times 6 + 3$. Toujours pas...

Prenons des restes plus petits : 2 et 4. Alors on aurait 171 et 252. $252 = 171 + 81$, $171 = 2\times 81 + 7$, et on retombe sur le cas précédent...

Si on divise 173 par 18, le reste est 11. $173 = 9\times 18 + 11$. Si on divise 256 par 18, le reste est 4 : $256 = 14\times 18 + 4$.

Essayons : on divise 173 et 256 par un même entier naturel non nul. Les restes sont respectivement 11 et 4. Quel est ce diviseur ?

$173 = q_1 n + 11$, $256 = q_2n + 4$. $173-11 = 162$ est divisible par $n$, $256 - 4 = 252$ est divisible par $n$. $n = \text{PGCD}(162, 252)$. $252 = 162 + 90$, $162 = 90 + 72$, $90 = 72 + 18$, $72 = 4 \times 18 + 0$. Donc PGCD = 18.

Donc 18 est bien le diviseur.

Correction :

Soit $d = \text{PGCD}(5n+3, 2n+1)$. Alors $d$ divise toute combinaison linéaire de $5n+3$ et $2n+1$.

$2(5n+3) - 5(2n+1) = 10n + 6 - 10n - 5 = 1$. Donc $d$ divise 1, et par conséquent, $d=1$.