QCM : PGCD et algorithme d’Euclide

[enonce]
Ce QCM porte sur le PGCD et l'algorithme d'Euclide. Pour chaque question, choisissez la bonne réponse parmi les quatre propositions.
[/enonce]

[etape]
Soient $a$ et $b$ deux entiers naturels non nuls et $r$ le reste de la division euclidienne de $a$ par $b$. Quelle égalité est correcte ?
[qcm]
[option]$\text{PGCD}(a\,;\,b) = \text{PGCD}(a\,;\,r)$[/option]
[option correct="true"]$\text{PGCD}(a\,;\,b) = \text{PGCD}(b\,;\,r)$[/option]
[option]$\text{PGCD}(a\,;\,b) = \text{PGCD}(r\,;\,a-b)$[/option]
[option]$\text{PGCD}(a\,;\,b) = b - r$[/option]
[reponse statut="correct"]Exactement !
C'est le théorème fondamental qui justifie l'algorithme d'Euclide : on remplace $(a\,;\,b)$ par $(b\,;\,r)$ sans changer le PGCD.[/reponse]
[reponse motif="$\text{PGCD}(a\,;\,b) = \text{PGCD}(a\,;\,r)$"]Non.
Attention à l'ordre des arguments. Dans l'algorithme d'Euclide, c'est l'ancien diviseur $b$ qui devient le nouveau dividende, pas $a$.[/reponse]
[reponse motif="$\text{PGCD}(a\,;\,b) = \text{PGCD}(r\,;\,a-b)$"]Non.
$a-b$ n'a pas de raison d'apparaître ici : on utilise la division euclidienne $a = bq + r$, pas une simple soustraction.[/reponse]
[reponse motif="$\text{PGCD}(a\,;\,b) = b - r$"]Non.
Le PGCD n'est pas une expression simple en fonction de $b$ et $r$ : il faut itérer le processus, et c'est seulement le dernier reste non nul qui donne le résultat.[/reponse]
[reponse statut="incorrect"]Non.
La propriété qui rend l'algorithme d'Euclide possible s'écrit $\text{PGCD}(a\,;\,b) = \text{PGCD}(b\,;\,r)$ : le diviseur devient le dividende, le reste devient le diviseur.[/reponse]
[/qcm]
[/etape]

[etape]
À l'aide de l'algorithme d'Euclide, calculer $\text{PGCD}(154\,;\,42)$.
[qcm]
[option]$7$[/option]
[option correct="true"]$14$[/option]
[option]$21$[/option]
[option]$28$[/option]
[reponse statut="correct"]Bonne réponse !
$154 = 42 \times 3 + 28$, puis $42 = 28 \times 1 + 14$, puis $28 = 14 \times 2 + 0$. Le dernier reste non nul est $14$, donc $\text{PGCD}(154\,;\,42) = 14$.[/reponse]
[reponse motif="$7$"]Non.
$7$ est bien un diviseur commun, mais l'algorithme s'arrête sur le dernier reste non nul, pas sur le plus petit diviseur trouvé. Reprendre les divisions successives.[/reponse]
[reponse motif="$21$"]Non.
Vérifier que la valeur proposée divise effectivement les deux nombres : $154 \div 21$ ne tombe pas juste, donc $21$ n'est pas un diviseur commun.[/reponse]
[reponse motif="$28$"]Non.
$28$ est le premier reste obtenu, mais ce n'est pas encore le dernier reste non nul. Continuer l'algorithme une étape de plus.[/reponse]
[reponse statut="incorrect"]Non.
Reprendre les divisions euclidiennes successives : $154 = 42 \times 3 + 28$, puis $42 = 28 \times 1 + 14$, puis $28 = 14 \times 2 + 0$. Le PGCD est le dernier reste non nul, soit $14$.[/reponse]
[/qcm]
[/etape]

[etape]
Lors de l'algorithme d'Euclide appliqué à deux entiers naturels non nuls, comment lit-on le PGCD à la fin du calcul ?
[qcm]
[option]C'est le dernier reste obtenu (donc $0$).[/option]
[option]C'est le dernier dividende.[/option]
[option correct="true"]C'est le dernier reste non nul.[/option]
[option]C'est le dernier quotient.[/option]
[reponse statut="correct"]C'est bien ça !
La suite des restes est strictement décroissante et finit par atteindre $0$. Le PGCD est le reste qui précède immédiatement le $0$ final.[/reponse]
[reponse motif="C'est le dernier reste obtenu (donc $0$)."]Non.
Le dernier reste vaut $0$ par construction, ce qui n'aurait aucun sens pour un PGCD (qui n'est jamais nul si l'un des nombres est non nul).[/reponse]
[reponse motif="C'est le dernier dividende."]Non.
Le dernier dividende est égal au reste obtenu une étape plus tôt : c'est bien lui qui correspond au PGCD, mais sa désignation correcte dans l'algorithme reste « dernier reste non nul ».[/reponse]
[reponse motif="C'est le dernier quotient."]Non.
Les quotients servent uniquement à exprimer la division euclidienne ; ils ne fournissent aucune information sur le PGCD.[/reponse]
[reponse statut="incorrect"]Non.
Dans l'algorithme d'Euclide, le PGCD se lit comme le dernier reste non nul de la suite des divisions successives.[/reponse]
[/qcm]
[/etape]

[etape]
Soient $a$ et $b$ deux entiers naturels non nuls. Lequel des énoncés suivants caractérise correctement les diviseurs communs à $a$ et $b$ ?
[qcm]
[option]Ce sont les multiples du PGCD de $a$ et $b$.[/option]
[option correct="true"]Ce sont les diviseurs du PGCD de $a$ et $b$.[/option]
[option]Ce sont les nombres premiers qui divisent à la fois $a$ et $b$.[/option]
[option]Ce sont uniquement $1$ et le PGCD de $a$ et $b$.[/option]
[reponse statut="correct"]Bravo !
L'ensemble des diviseurs communs à $a$ et $b$ coïncide exactement avec l'ensemble des diviseurs de $\text{PGCD}(a\,;\,b)$. C'est ce qui justifie le rôle central du PGCD.[/reponse]
[reponse motif="Ce sont les multiples du PGCD de $a$ et $b$."]Non.
Multiples et diviseurs sont deux notions opposées. Un multiple du PGCD peut être plus grand que $a$ ou $b$ et donc ne plus les diviser.[/reponse]
[reponse motif="Ce sont les nombres premiers qui divisent à la fois $a$ et $b$."]Non.
Tous les diviseurs communs ne sont pas premiers. Par exemple $4$ divise $12$ et $20$ sans être un nombre premier.[/reponse]
[reponse motif="Ce sont uniquement $1$ et le PGCD de $a$ et $b$."]Non.
Il y a en général d'autres diviseurs communs intermédiaires. Par exemple $\text{PGCD}(12\,;\,18) = 6$, et $2$ comme $3$ sont des diviseurs communs.[/reponse]
[reponse statut="incorrect"]Non.
La propriété à retenir est : les diviseurs communs à $a$ et $b$ sont exactement les diviseurs de $\text{PGCD}(a\,;\,b)$.[/reponse]
[/qcm]
[/etape]

[etape]
Le PGCD de $1071$ et $462$ est :
[qcm]
[option]$3$[/option]
[option]$7$[/option]
[option correct="true"]$21$[/option]
[option]$33$[/option]
[reponse statut="correct"]Tu as raison !
$1071 = 462 \times 2 + 147$, puis $462 = 147 \times 3 + 21$, puis $147 = 21 \times 7 + 0$. Le dernier reste non nul est $21$.[/reponse]
[reponse motif="$3$"]Non.
$3$ est bien un diviseur commun, mais ce n'est pas le plus grand. Poursuivre l'algorithme jusqu'à un reste nul et lire le reste précédent.[/reponse]
[reponse motif="$7$"]Non.
$7$ divise effectivement $1071$ et $462$, mais il existe un diviseur commun plus grand. Reprendre l'algorithme d'Euclide soigneusement.[/reponse]
[reponse motif="$33$"]Non.
Vérifier la divisibilité par la valeur proposée : $462 \div 33$ ne donne pas un quotient entier, donc $33$ ne divise pas $462$.[/reponse]
[reponse statut="incorrect"]Non.
Appliquer l'algorithme : $1071 = 462 \times 2 + 147$, $462 = 147 \times 3 + 21$, $147 = 21 \times 7 + 0$. Le PGCD est $21$.[/reponse]
[/qcm]
[/etape]

[etape]
On sait que $\text{PGCD}(a\,;\,b) = 12$. Lequel des nombres suivants ne peut pas être un diviseur commun à $a$ et $b$ ?
[qcm]
[option]$3$[/option]
[option]$4$[/option]
[option]$6$[/option]
[option correct="true"]$8$[/option]
[reponse statut="correct"]Parfait !
Les diviseurs communs sont exactement les diviseurs de $12$, c'est-à-dire $1$, $2$, $3$, $4$, $6$ et $12$. Or $8$ ne figure pas dans cette liste : il ne divise pas $12$.[/reponse]
[reponse motif="$3$"]Non.
$3$ divise $12$, donc $3$ est bien un diviseur commun à $a$ et $b$. Vérifier la liste des diviseurs de $12$.[/reponse]
[reponse motif="$4$"]Non.
$4$ figure dans la liste des diviseurs de $12$ : il divise donc $a$ et $b$. Chercher un nombre absent de la liste des diviseurs de $12$.[/reponse]
[reponse motif="$6$"]Non.
$6$ divise $12$, donc $6$ divise aussi tout multiple commun de $a$ et $b$ qui passe par $12$. Chercher plutôt un nombre qui n'apparaît pas parmi les diviseurs de $12$.[/reponse]
[reponse statut="incorrect"]Non.
Les diviseurs communs à $a$ et $b$ sont les diviseurs de leur PGCD, soit les diviseurs de $12$ : $1$, $2$, $3$, $4$, $6$, $12$. Tout nombre absent de cette liste ne peut pas diviser à la fois $a$ et $b$.[/reponse]
[/qcm]
[/etape]