QCM : Arithmétique dans $\mathbb{Z}$ (Prépa, 1re année)
Ce chapitre étudie la divisibilité dans $\mathbb{Z}$ : division euclidienne, PGCD et PPCM, nombres premiers, congruences. Ces outils servent à résoudre des équations en nombres entiers, à calculer des restes de grandes puissances, et ils préparent l'étude des anneaux $\mathbb{Z}/n\mathbb{Z}$ et de l'arithmétique des polynômes.
Quel est le couple (quotient, reste) de la division euclidienne de $-23$ par $6$ ?
On a $q = \lfloor -23/6 \rfloor = \lfloor -3{,}83\ldots \rfloor = -4$ et $r = -23 - 6 \times (-4) = 1$, avec bien $0 \leqslant 1 < 6$. Le piège principal est $(-3, -5)$ : l'égalité $-23 = 6 \times (-3) - 5$ est exacte, mais le reste doit être positif ou nul. Le choix $(-3, 5)$ ne vérifie même pas l'égalité, car $6 \times (-3) + 5 = -13$.
Que vaut $252 \wedge 198$ ?
Algorithme d'Euclide : $252 = 1 \times 198 + 54$, $198 = 3 \times 54 + 36$, $54 = 1 \times 36 + 18$, $36 = 2 \times 18 + 0$. Le dernier reste non nul est $18$. Les choix $54$ et $36$ viennent d'un arrêt prématuré de l'algorithme : on a pris un reste intermédiaire au lieu du dernier reste non nul. On peut vérifier avec les décompositions $252 = 2^2 \times 3^2 \times 7$ et $198 = 2 \times 3^2 \times 11$, qui donnent $2 \times 3^2 = 18$.
Soient $a, b \in \mathbb{Z}$ non tous deux nuls. On suppose qu'il existe $(u, v) \in \mathbb{Z}^2$ tel que $au + bv = 6$. Que peut-on conclure à coup sûr ?
$a \wedge b$ divise $a$ et $b$, donc il divise toute combinaison $au + bv$, en particulier $6$. On ne peut rien dire de plus : $2 \times 3 + 0 \times 5 = 6$ avec $2 \wedge 0 = 2$, et $1 \times 6 + 1 \times 0 = 6$ avec $1 \wedge 0 = 1$. Le piège est de croire qu'une relation $au + bv = d$ donne toujours le PGCD. La réciproque du théorème de Bézout ne vaut que pour $d = 1$.
Quel est l'ensemble des solutions dans $\mathbb{Z}^2$ de l'équation $10x + 4y = 6$ ?
$10 \wedge 4 = 2$ divise $6$, donc il y a des solutions. On se ramène à $5x + 2y = 3$, avec la solution particulière $(1, -1)$. Alors $5(x - 1) = 2(-1 - y)$ ; par Gauss, $2 \mid x - 1$, d'où $x = 1 + 2k$ et $y = -1 - 5k$. La réciproque se vérifie : $5(1 + 2k) + 2(-1 - 5k) = 3$. Le choix avec les pas $4$ et $10$ oublie de diviser par le PGCD : il ne donne qu'une partie des solutions, et il manque par exemple $(3, -6)$. Le choix avec $-1 + 5k$ comporte une erreur de signe. L'ensemble vide confond « premiers entre eux » et « le PGCD divise le second membre ».
Que vaut $84 \vee 90$ ?
$84 = 2^2 \times 3 \times 7$ et $90 = 2 \times 3^2 \times 5$. On prend le maximum des valuations : $2^2 \times 3^2 \times 5 \times 7 = 1260$. On retrouve ce résultat avec $84 \times 90 / (84 \wedge 90) = 7560 / 6 = 1260$. Le choix $7560$ est le produit, qui n'est égal au PPCM que si les entiers sont premiers entre eux. Le choix $6$ est le PGCD. Le choix $630$ vient d'une erreur sur la valuation en $2$, où l'on a pris $2^1$ au lieu de $2^2$.
Combien l'entier $720$ possède-t-il de diviseurs positifs ?
$720 = 2^4 \times 3^2 \times 5$, donc le nombre de diviseurs positifs est $(4+1)(2+1)(1+1) = 30$. Le choix $8 = 4 \times 2 \times 1$ oublie le $+1$, alors que chaque exposant $\beta_i$ peut valoir $0$. Le choix $7 = 4 + 2 + 1$ additionne les exposants au lieu de multiplier. Le choix $15 = 5 \times 3$ oublie le facteur premier $5$.
Quel est le reste de la division euclidienne de $5^{100}$ par $7$ ?
$7$ est premier et ne divise pas $5$, donc, par le petit théorème de Fermat, $5^6 \equiv 1 \;[7]$. Comme $100 = 6 \times 16 + 4$, on a $5^{100} \equiv 5^4 \;[7]$. Or $5^2 = 25 \equiv 4$, puis $5^4 \equiv 16 \equiv 2 \;[7]$. Le piège $4$ vient d'une réduction de l'exposant modulo $7$ ($100 \equiv 2 \;[7]$) au lieu de modulo $p - 1 = 6$. Le choix $1$ applique Fermat sans tenir compte de l'exposant réel.
Parmi les entiers suivants, lequel est un inverse de $5$ modulo $17$ ?
$5 \times 7 = 35 = 2 \times 17 + 1$, donc $5 \times 7 \equiv 1 \;[17]$. On a $5 \times 10 = 50 = 2 \times 17 + 16 \equiv -1 \;[17]$ : $10 \equiv -7$ est l'opposé de l'inverse, ce qui correspond à une erreur de signe en remontant l'algorithme d'Euclide. Le choix $3$ est un quotient de l'algorithme ($17 = 3 \times 5 + 2$), et non un coefficient de Bézout. Enfin $5 \times 12 = 60 \equiv 9 \;[17]$.
Soient $a, b, c, n \in \mathbb{Z}$. Laquelle des implications suivantes est toujours vraie ?
La première implication est le lemme de Gauss. La deuxième n'est vraie que si $a$ est premier (lemme d'Euclide) : $6 \mid 4 \times 3$, alors que $6 \nmid 4$ et $6 \nmid 3$. La troisième exige $a \wedge b = 1$ : $4 \mid 12$ et $6 \mid 12$, mais $24 \nmid 12$. La quatrième est fausse : $1 \wedge 2 = 1$ et $1 \wedge 4 = 1$, mais $2 \wedge 4 = 2$.
Quelles sont les solutions dans $\mathbb{Z}$ de la congruence $6x \equiv 4 \;[10]$ ?
$6x \equiv 4 \;[10]$ équivaut à $10 \mid 6x - 4$, soit $5 \mid 3x - 2$, c'est-à-dire $3x \equiv 2 \;[5]$. L'inverse de $3$ modulo $5$ est $2$, donc $x \equiv 4 \;[5]$. Vérification : $x = 4$ donne $24 - 4 = 20$ et $x = 9$ donne $54 - 4 = 50$, tous deux multiples de $10$. Le choix « $x \equiv 4 \;[10]$ » oublie que le module est divisé par $2$ en même temps que les coefficients, ce qui fait perdre la solution $x = 9$. L'absence de solution serait correcte si $2 = 6 \wedge 10$ ne divisait pas $4$. Le choix $x \equiv 2 \;[5]$ vient d'une simplification abusive de $3x \equiv 2$ en $x \equiv 2$.