QCM : PGCD, Bézout et nombres premiers en maths sup (MPSI)

Réponse C.

On a \(5\times(-4)+3=-17\) avec \(0\le 3<5\), donc le couple \((-4,3)\) convient, et il est unique. La réponse \(q=-3,\ r=-2\) donne bien \(-17\), cependant son reste est négatif : elle tronque le quotient vers zéro comme une calculatrice. Quant à \(q=-3,\ r=2\), elle reprend la division de \(17\) en changeant seulement le signe du quotient, ce qui donne \(-13\).

Réponse B.

L’algorithme d’Euclide donne \(252=198+54\), puis \(198=3\times54+36\), \(54=36+18\) et \(36=2\times18\). Le dernier reste non nul est donc \(18\). Ensuite, \(\operatorname{pgcd}\times\operatorname{ppcm}=252\times198\), d’où un PPCM égal à \(252\times11=2772\). La réponse \(49896\) prend le produit lui-même pour le PPCM. Les couples \((36,1386)\) et \((9,5544)\) respectent bien le produit, mais avec un PGCD faux : \(36\) ne divise pas \(54\).

Réponse B.

Les divisions successives sont \(41=2\times15+11\), \(15=11+4\), \(11=2\times4+3\) et \(4=3+1\). En remontant, \(1=3\times4-11=3\times15-4\times11=11\times15-4\times41\). Ainsi \(41\times(-4)+15\times11=1\). Le couple \((4,-11)\) inverse tous les signes et donne \(-1\). Le couple \((11,-4)\) échange les rôles de \(u\) et \(v\). Enfin, \((3,-8)\) donne \(3\) : la remontée s’est arrêtée trop tôt.

Réponse D.

Comme \(\operatorname{pgcd}(6,35)=1\), le lemme de Gauss s’applique : \(6\mid 35k\) entraîne \(6\mid k\). En revanche, \(6\) et \(4\) ne sont pas premiers entre eux, et \(k=3\) donne \(6\mid12\) sans \(6\mid3\). Pour \(k=6\), on a \(6\mid36\), mais \(36\) ne divise pas \(6\). Enfin, \(a=2\) et \(b=3\) réfutent la dernière implication, qui ne vaut que pour un diviseur premier.

Réponse B.

On part de \(4\times2+7\times(-1)=1\), puis on multiplie par \(3\) : \((6,-3)\) est une solution particulière. Par différence, \(4(x-6)=-7(y+3)\). Comme \(4\) et \(7\) sont premiers entre eux, Gauss donne \(x-6=7k\), puis \(y+3=-4k\). La réponse avec \(6+4k\) échange les coefficients. Celle avec \(-3+4k\) perd le signe moins. Enfin, \((2,-1)\) résout \(4x+7y=1\) et non l’équation posée.

Réponse A.

Les PGCD deux à deux valent \(2\), \(5\) et \(7\) : aucune paire n’est formée d’entiers premiers entre eux. Cependant, aucun nombre premier ne divise les trois entiers à la fois, donc \(\operatorname{pgcd}(10,14,35)=1\). D’ailleurs, \(10\times(-2)+14\times(-1)+35=1\) en fournit une relation de Bézout. Conclure « ni l’un ni l’autre » à partir d’une seule paire confond donc les deux notions.

Réponse A.

Comme \(N\ge2\), il admet un diviseur premier \(p\). Si \(p\) é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. Croire que \(N\) est toujours premier est une erreur classique : \(2\times3\times5\times7\times11\times13+1=30031=59\times509\). À l’inverse, \(N\) n’est pas toujours composé, puisque \(2\times3+1=7\) est premier. Enfin, \(N\) laisse le reste \(1\) dans la division par chaque \(p_i\).

Réponse D.

Il suffit de tester les premiers \(p\) tels que \(p^2\le391\), soit jusqu’à \(19\), car \(\sqrt{391}\approx19{,}8\). Or \(17\times23=391\), donc \(391\) est composé. S’arrêter à \(13\) revient à mal estimer la racine carrée : on conclurait à tort qu’il est premier. Par ailleurs, \(13\times31=403\) et \(7\times57=399\), si bien que ces deux factorisations sont fausses. Il faut donc vérifier chaque produit avant de conclure.

Réponse C.

On compte les multiples de \(3\), puis ceux de \(9\) et de \(27\), qui apportent chacun un facteur supplémentaire. Ainsi \(v_3(50!)=\lfloor50/3\rfloor+\lfloor50/9\rfloor+\lfloor50/27\rfloor=16+5+1=22\). La réponse \(16\) ne compte que les multiples de \(3\). La réponse \(21\) oublie le facteur de plus apporté par \(27\). Quant à \(17\), elle arrondit \(50/3\) au-dessus au lieu de prendre la partie entière.

Réponse A.

Comme \(\operatorname{pgcd}(7,30)=1\), la classe de \(7\) est inversible, même si \(30\) n’est pas premier. En effet, \(7\times13=91=3\times30+1\), donc \(13\) convient. La classe de \(17\) vaut \(-13\) modulo \(30\) : elle donne \(7\times17=119\equiv-1\), c’est donc une erreur de signe. Enfin, \(\frac{1}{7}\) n’est pas un entier : l’inverse se cherche parmi les classes de congruence.

Réponse D.

Comme \(11\) est premier et ne divise pas \(5\), le petit théorème de Fermat donne \(5^{10}\equiv1 \pmod{11}\). Or \(123=12\times10+3\), donc \(5^{123}\equiv5^3=125=11\times11+4\). La réponse \(3\) réduit l’exposant modulo \(11\) au lieu de \(10\), ce qui donne \(5^2=25\). La réponse \(5\) applique \(a^p\equiv a\) avec le mauvais exposant. Enfin, \(1\) suppose à tort que \(123\) est un multiple de \(10\).

Réponse C.

Le théorème de Fermat affirme : si \(p\) est premier et ne divise pas \(a\), alors \(a^{p-1}\equiv1\). Ici, la conclusion est vérifiée alors que \(341\) est composé. Par conséquent, la réciproque est fausse, et ce test ne prouve pas la primalité. Le théorème n’est pas contredit pour autant, puisque son hypothèse n’est pas remplie. Enfin, l’égalité obtenue montre au contraire que \(2\) est inversible modulo \(341\), donc premier avec lui.