QCM : Divisibilité et congruences en L1 de maths
Ce QCM congruences L1 passe en revue l’arithmétique de première année, de la division euclidienne jusqu’au petit théorème de Fermat. Les douze questions vont du plus simple au plus exigeant : un reste négatif à éviter, un PGCD obtenu par l’algorithme d’Euclide, des coefficients de Bézout, une équation diophantienne, un inverse modulaire et une puissance réduite modulo un nombre premier.
Pour en tirer profit, réponds d’abord sans ouvrir ton cours, au brouillon, en refaisant chaque calcul. Ensuite, lis toutes les explications, même quand ta réponse est juste. En effet, chaque mauvaise proposition correspond à une erreur fréquente : hypothèse oubliée dans le lemme de Gauss, exposant réduit modulo le mauvais entier, solution particulière confondue avec la solution générale. Si tu bloques sur une question, reprends la notion correspondante avant de recommencer le test.
Les 12 questions
Question 1
On effectue la division euclidienne de \(-23\) par \(5\), avec un reste \(r\) vérifiant \(0 \leq r < 5\). Quels sont le quotient et le reste ?
- Quotient \(-4\), reste \(-3\)
- Quotient \(-5\), reste \(2\)
- Quotient \(-5\), reste \(-2\)
- Quotient \(4\), reste \(3\)
Réponse B.
On cherche \(q\) tel que \(5q \leq -23 < 5q+5\). Ainsi \(q=-5\), car \(-25 \leq -23 < -20\), et donc \(r=-23+25=2\). Le piège classique consiste à diviser \(23\) par \(5\) puis à changer les signes : on obtient \(-23=5\times(-4)-3\), écriture juste mais dont le reste est négatif, donc interdit.
Question 2
L’algorithme d’Euclide appliqué à \(391\) et \(299\) donne le PGCD de ces deux entiers. Lequel ?
- \(23\)
- \(13\)
- \(92\)
- \(1\)
Réponse A.
On écrit \(391=299+92\), puis \(299=3\times 92+23\), enfin \(92=4\times 23+0\). Le PGCD est le dernier reste non nul, donc \(23\). Le piège \(92\) vient d’un arrêt prématuré au premier reste. Par ailleurs, \(13\) est seulement le cofacteur de \(299=13\times 23\), et \(1\) suppose à tort que deux nombres impairs sont premiers entre eux.
Question 3
On sait que \(\gcd(391,299)=23\). En remontant l’algorithme d’Euclide, quel couple \((u,v)\) vérifie \(391u+299v=23\) ?
- \((u,v)=(3,\,-4)\)
- \((u,v)=(4,\,-3)\)
- \((u,v)=(-4,\,3)\)
- \((u,v)=(-3,\,4)\)
Réponse D.
On part de \(23=299-3\times 92\) et on remplace \(92\) par \(391-299\). On obtient \(23=299-3(391-299)=4\times 299-3\times 391\), donc \(u=-3\) et \(v=4\). Vérification : \(-1173+1196=23\). Le couple \((3,-4)\) donne \(-23\), erreur de signe fréquente ; les couples \((4,-3)\) et \((-4,3)\) inversent les rôles de \(u\) et \(v\).
Question 4
Que peut-on dire de l’équation \(14x+21y=5\), d’inconnues \(x\) et \(y\) entières ?
- Elle a une infinité de solutions, comme toute équation de Bézout.
- Elle n’a aucune solution entière.
- Elle a exactement une solution entière.
- Elle a des solutions, car \(\gcd(14,21)\) divise \(21\).
Réponse B.
Pour tous entiers \(x\) et \(y\), le nombre \(14x+21y\) est un multiple de \(\gcd(14,21)=7\). Or \(7\) ne divise pas \(5\), par conséquent l’équation n’a aucune solution. Le piège consiste à appliquer Bézout sans vérifier que le second membre est un multiple du PGCD. Par ailleurs, quand une telle équation a une solution, elle en a toujours une infinité, jamais une seule.
Question 5
Parmi ces énoncés, lequel est exactement le lemme de Gauss, pour \(a\), \(b\), \(c\) entiers non nuls ?
- Si \(a \mid bc\), alors \(a \mid b\) ou \(a \mid c\).
- Si \(a \mid bc\) et \(\gcd(b,c)=1\), alors \(a \mid c\).
- Si \(a \mid bc\) et \(\gcd(a,b)=1\), alors \(a \mid c\).
- Si \(a \mid c\) et \(b \mid c\), alors \(ab \mid c\).
Réponse C.
Le lemme de Gauss exige que \(a\) soit premier avec le facteur \(b\) qu’on élimine. Sans cette hypothèse, tout s’écroule : \(6\) divise \(4\times 9\), cependant \(6\) ne divise ni \(4\) ni \(9\). L’énoncé qui conclut à \(ab \mid c\) est faux aussi, puisque \(2\) et \(4\) divisent \(4\) alors que \(8\) ne le divise pas ; il devient vrai seulement si \(a\) et \(b\) sont premiers entre eux.
Question 6
Deux entiers strictement positifs \(a\) et \(b\) vérifient \(\gcd(a,b)=6\) et \(ab=540\). Que vaut leur PPCM ?
- \(540\)
- \(45\)
- \(90\)
- \(3240\)
Réponse C.
Pour des entiers positifs, on a toujours \(\gcd(a,b)\times\operatorname{ppcm}(a,b)=ab\). Donc le PPCM vaut \(540/6=90\). Par exemple, \(a=18\) et \(b=30\) conviennent. Le piège \(540\) confond le produit et le PPCM, ce qui n’est vrai que pour des nombres premiers entre eux. Ensuite, \(3240\) multiplie au lieu de diviser, tandis que \(45\) divise par \(12\).
Question 7
Dans la preuve d’Euclide de l’infinité des nombres premiers, on suppose que \(p_1,\dots,p_n\) sont tous les nombres premiers et l’on pose \(N=p_1p_2\cdots p_n+1\). Que justifie-t-on ensuite ?
- \(N\) a un diviseur premier différent de tous les \(p_i\).
- \(N\) est forcément un nombre premier.
- \(N\) est divisible par le plus grand des \(p_i\).
- \(N\) est premier avec \(N-1\), donc premier.
Réponse A.
Comme \(N \geq 2\), il admet un diviseur premier \(q\). Si \(q\) était l’un des \(p_i\), il diviserait \(N-p_1\cdots p_n=1\), ce qui est absurde. Ainsi la liste n’était pas complète. En revanche, \(N\) n’est pas toujours premier : \(2\times 3\times 5\times 7\times 11\times 13+1=30031=59\times 509\). C’est le piège le plus courant sur cette preuve.
Question 8
On donne \(756=2^2\times 3^3\times 7\). Combien \(756\) possède-t-il de diviseurs positifs ?
- \(6\)
- \(24\)
- \(12\)
- \(7\)
Réponse B.
Un diviseur positif s’écrit \(2^{\alpha}3^{\beta}7^{\gamma}\) avec \(0\leq\alpha\leq 2\), \(0\leq\beta\leq 3\) et \(0\leq\gamma\leq 1\). On a donc \(3\times 4\times 2=24\) choix. Le piège \(6\) multiplie les exposants sans ajouter \(1\) à chacun. De même, \(12\) oublie le cas \(\beta=0\) ou un autre facteur, tandis que \(7\) additionne les exposants augmentés au lieu de les multiplier.
Question 9
Pour un entier \(n \geq 2\), lequel de ces énoncés est vrai ?
- Si \(n\) est premier, alors \(a^{n-1}\equiv 1 \pmod n\) pour tout entier \(a\).
- Si \(\gcd(a,n)=1\), alors \(a^{n-1}\equiv 1 \pmod n\).
- Si \(2^{n-1}\equiv 1 \pmod n\), alors \(n\) est premier.
- Si \(n\) est premier, alors \(a^n\equiv a \pmod n\) pour tout entier \(a\).
Réponse D.
La forme \(a^p\equiv a\) du petit théorème de Fermat vaut pour tout entier \(a\). En revanche, la forme \(a^{p-1}\equiv 1\) exige que \(p\) ne divise pas \(a\) : pour \(a=0\), elle est fausse. Ensuite, \(n=9\) et \(a=2\) donnent \(2^8=256\equiv 4 \pmod 9\). Enfin, \(341=11\times 31\) vérifie \(2^{340}\equiv 1\) sans être premier : la réciproque est fausse.
Question 10
Quel est le reste de la division euclidienne de \(5^{123}\) par \(11\) ?
- \(4\)
- \(3\)
- \(1\)
- \(9\)
Réponse A.
Comme \(11\) est premier et ne divise pas \(5\), Fermat donne \(5^{10}\equiv 1 \pmod{11}\). Or \(123=12\times 10+3\), donc \(5^{123}\equiv 5^3=125\equiv 4\). Le piège \(3\) réduit l’exposant modulo \(11\) au lieu de \(10\), d’où \(5^2=25\equiv 3\). Par ailleurs, \(9\) correspond à \(5^4\), obtenu par une erreur de division de l’exposant.
Question 11
Quel entier \(x\) de \(\{0,\dots,29\}\) vérifie \(7x\equiv 1 \pmod{30}\) ?
- \(x=17\)
- \(x=23\)
- \(x=13\)
- Aucun, car \(30\) n’est pas premier
Réponse C.
L’inverse existe dès que \(\gcd(7,30)=1\), même si \(30\) n’est pas premier : c’est le piège principal. Bézout donne \(7\times 13-3\times 30=1\), donc \(x=13\). Vérification : \(91=3\times 30+1\). Ensuite, \(17\) donne \(119\equiv -1\), erreur de signe typique. Enfin, \(23\) donne \(161\equiv 11\), ce qui ne convient pas.
Question 12
On remarque que \((x,y)=(-1,1)\) vérifie \(5x+8y=3\). Quelles sont toutes les solutions entières de cette équation ?
- \(x=-1+5k,\ y=1-8k\), avec \(k\in\mathbb{Z}\)
- \(x=-1+8k,\ y=1+5k\), avec \(k\in\mathbb{Z}\)
- \(x=-1+16k,\ y=1-10k\), avec \(k\in\mathbb{Z}\)
- \(x=-1+8k,\ y=1-5k\), avec \(k\in\mathbb{Z}\)
Réponse D.
Par différence avec la solution particulière, on obtient \(5(x+1)=-8(y-1)\). Puisque \(5\) et \(8\) sont premiers entre eux, le lemme de Gauss donne \(8 \mid x+1\), donc \(x=-1+8k\), puis \(y=1-5k\). Échanger les coefficients ou oublier le signe moins donne des couples qui ne vérifient pas l’équation. Enfin, le couple \(x=-1+16k,\ y=1-10k\) ne fournit qu’une partie des solutions.
Pour aller plus loin
- Revoir la leçon : cours de L1 de maths sur divisibilité et congruences
- S’exercer : exercices corrigés sur divisibilité et congruences
- QCM précédent : QCM : Fonctions arc et hyperboliques en L1 de maths
- QCM suivant : QCM : Polynômes et théorème de d'Alembert en L1 de maths
- Tous les chapitres : le sommaire de la L1 de maths
