Équations diophantiennes et valuations : corrigé du contrôle de maths en MPSI

Équations diophantiennes et valuations – Corrigé du contrôle en Maths sup (MPSI) sur Maths-pdf.fr

Couverture : Livre de contrôles corrigés de maths MPSI en PDF

Télécharger en PDF Le livre des 25 contrôles corrigés en MPSI PDF à imprimer Voir le livre ›

Sommaire

Voici le corrigé du contrôle de maths en MPSI sur le thème « équations diophantiennes et valuations », question par question.

Cette correction suit l’ordre du sujet et rédige chaque réponse comme une copie complète. Pour Bézout, elle présente d’abord les divisions successives, puis la remontée ligne par ligne, et enfin la vérification numérique. L’équation diophantienne est ensuite résolue avec le lemme de Gauss, et une figure place les trois solutions positives sur la droite. Les questions de valuations montrent comment remplacer un calcul de PGCD par une simple comparaison d’exposants. Dans le vrai/faux, chaque assertion fausse reçoit un contre-exemple explicite, tandis que chaque assertion vraie est démontrée. Le problème justifie enfin le déchiffrement grâce au petit théorème de Fermat, sans oublier le cas du message nul. Un barème détaillé accompagne chaque exercice.

L’énoncé complet se trouve ici : Équations diophantiennes et valuations : contrôle de maths en MPSI.

Barème du contrôle corrigé : équations diophantiennes et valuations

Exercice	Points
1. Euclide étendu sur 47 et 17	4 points
2. Une équation diophantienne et ses solutions positives	4 points
3. Valuations p-adiques	3 points
4. Vrai ou faux justifié	4 points
5. Problème : un chiffrement par puissances modulo 17	5 points
Total	20 points

Le corrigé détaillé : équations diophantiennes et valuations

Exercice 1 – Euclide étendu sur 47 et 17 (4 points)

Les divisions euclidiennes successives sont les suivantes :

\(47 = 2 \times 17 + 13\)
\(17 = 1 \times 13 + 4\)
\(13 = 3 \times 4 + 1\)
\(4 = 4 \times 1 + 0\)

Chaque quotient compte les carrés d’une même taille : deux carrés de côté 17, un de côté 13, trois de côté 4, puis quatre de côté 1. Le dernier reste non nul vaut 1. Le côté du plus petit carré est donc le PGCD de 47 et 17, qui vaut 1 : ces entiers sont premiers entre eux.
On remonte les égalités en partant de l’avant-dernière ligne :

\(1 = 13 – 3 \times 4\)
\(1 = 13 – 3 \times (17 – 13) = 4 \times 13 – 3 \times 17\)
\(1 = 4 \times (47 – 2 \times 17) – 3 \times 17 = 4 \times 47 – 11 \times 17\)

Vérification : \(4 \times 47 = 188\) et \(11 \times 17 = 187\). On peut donc prendre \(u = 4\) et \(v = -11\).
La relation précédente donne \(17 \times (-11) \equiv 1 \pmod{47}\). Or \(-11 \equiv 36 \pmod{47}\), et l’on contrôle que \(17 \times 36 = 612 = 13 \times 47 + 1\). L’inverse de 17 modulo 47 est donc 36.
Comme 17 est inversible modulo 47, on peut multiplier par 36 sans perdre d’équivalence : \(17x \equiv 5 \pmod{47}\) équivaut à \(x \equiv 180 \pmod{47}\). Puis \(180 = 3 \times 47 + 39\). Vérification : \(17 \times 39 = 663 = 14 \times 47 + 5\). Les solutions sont les entiers \(x = 39 + 47k\), avec \(k \in \mathbb{Z}\).

Barème : 1) divisions (0,5) et lecture de la figure (0,5) ; 2) remontée (0,75) et vérification (0,25) ; 3) 1 point ; 4) multiplication par l’inverse justifiée (0,5) et ensemble des solutions (0,5).

Piège classique : développer les produits à chaque étape de la remontée. On garde au contraire 47 et 17 comme « variables », sinon la relation se perd dans les calculs.

Exercice 2 – Une équation diophantienne et ses solutions positives (4 points)

Pour tous entiers \(x\) et \(y\), on a \(21x + 15y = 3(7x + 5y)\), qui est un multiple de 3. Or \(313 = 3 \times 104 + 1\) n’est pas divisible par 3. Une dépense de 313 € est donc impossible.
Puisque \(312 = 3 \times 104\), l’équation \((E)\) équivaut, après division par 3, à \(7x + 5y = 104\), où \(\text{PGCD}(7, 5) = 1\). Par exemple, \(7 \times 2 + 5 \times 18 = 14 + 90 = 104\). Le couple \((2, 18)\) est une solution particulière.

Questions 3 et 4 : toutes les solutions, puis les solutions positives

Soit \((x, y)\) une solution. En soustrayant l’égalité \(7 \times 2 + 5 \times 18 = 104\), on obtient \(7(x – 2) = 5(18 – y)\). Ainsi 5 divise \(7(x – 2)\). Or 5 et 7 sont premiers entre eux, donc, d’après le lemme de Gauss, 5 divise \(x – 2\) : il existe \(k \in \mathbb{Z}\) tel que \(x = 2 + 5k\). En reportant, \(35k = 5(18 – y)\), d’où \(y = 18 – 7k\).

Réciproquement, \(7(2 + 5k) + 5(18 – 7k) = 14 + 35k + 90 – 35k = 104\). Les solutions de \((E)\) sont donc les couples \((2 + 5k,\, 18 – 7k)\), avec \(k \in \mathbb{Z}\).
On veut \(x \geq 0\) et \(y \geq 0\), c’est-à-dire \(k \geq -\frac{2}{5}\) et \(k \leq \frac{18}{7}\). Comme \(k\) est entier, \(k \in \{0\,;1\,;2\}\). On obtient alors \((2, 18)\), \((7, 11)\) et \((12, 4)\). Il y a donc trois compositions possibles : 2 adultes et 18 enfants, 7 adultes et 11 enfants, ou 12 adultes et 4 enfants. Ces trois points sont les seuls points à coordonnées entières de \(D\) dans le quart de plan.

Droite D avec les trois points à coordonnées entières positives marqués en orange : (2 ; 18), (7 ; 11) et (12 ; 4)

Barème : 1) 0,5 point ; 2) simplification (0,5) et solution particulière (0,5) ; 3) lemme de Gauss cité (0,5), forme des solutions (0,5), réciproque (0,5) ; 4) encadrement de \(k\) (0,5), trois couples et figure (0,5).

Piège classique : oublier la réciproque. Le raisonnement par condition nécessaire donne seulement des candidats, qu’il faut ensuite reporter dans l’équation.

Exercice 3 – Valuations p-adiques (3 points)

On divise 18144 cinq fois par 2 et l’on obtient \(567 = 81 \times 7\), donc \(N = 2^5 \times 3^4 \times 7\). De même, \(145800 = 1458 \times 100\), avec \(1458 = 2 \times 729 = 2 \times 3^6\) et \(100 = 2^2 \times 5^2\), donc \(M = 2^3 \times 3^6 \times 5^2\). La valuation du PGCD est le minimum des valuations, celle du PPCM en est le maximum. Ainsi \(\text{PGCD}(N, M) = 2^3 \times 3^4 = 648\) et \(\text{PPCM}(N, M) = 2^5 \times 3^6 \times 5^2 \times 7\).

Questions 2 et 3 : compter des facteurs premiers

Parmi les entiers de 1 à 30, six sont multiples de 5 et un seul, 25, est multiple de 25 ; par conséquent \(v_5(30!) = 6 + 1 = 7\). De même, on compte 15 multiples de 2, 7 multiples de 4, 3 multiples de 8 et 1 multiple de 16, donc \(v_2(30!) = 15 + 7 + 3 + 1 = 26\). Le nombre de zéros finaux est la plus grande puissance de \(10 = 2 \times 5\) qui divise \(30!\), soit \(\min(26, 7)\). L’entier \(30!\) se termine donc par exactement 7 zéros.
Supposons que \(a^3 = 12\,b^3\) avec \(a, b \geq 1\). Comme \(12 = 2^2 \times 3\), la valuation 2-adique donne \(3\,v_2(a) = 2 + 3\,v_2(b)\), donc \(3\left(v_2(a) – v_2(b)\right) = 2\). Or 3 ne divise pas 2 : c’est absurde. Si \(\sqrt[3]{12}\) était rationnel, il s’écrirait \(\frac{a}{b}\) avec \(a, b \geq 1\), car il est positif, et l’on aurait \(a^3 = 12\,b^3\). Le réel \(\sqrt[3]{12}\) est donc irrationnel.

Barème : 1) décompositions (0,5), PGCD et PPCM (0,5) ; 2) \(v_5\) (0,25), \(v_2\) (0,25), nombre de zéros justifié (0,5) ; 3) égalité des valuations (0,5) et conclusion (0,5).

Piège classique : compter les multiples de 5 sans ajouter ceux de 25. Le nombre 25 apporte en effet deux facteurs 5.

Exercice 4 – Vrai ou faux justifié (4 points)

Faux. Le nombre 13 est premier et ne divise pas 2, donc le petit théorème de Fermat donne \(2^{12} \equiv 1 \pmod{13}\), ce que confirme le retour à 1 sur la figure. Or \(2026 = 12 \times 168 + 10\), donc \(2^{2026} = \left(2^{12}\right)^{168} \times 2^{10} \equiv 2^{10} \pmod{13}\). Enfin \(2^{10} = 1024 = 78 \times 13 + 10\) : le reste vaut 10, et non 4.
Faux. Prenons \(a = 4\), \(b = 2\) et \(c = 6\) : 4 divise \(bc = 12\), mais 4 ne divise ni 2 ni 6. Le lemme de Gauss exige en effet que \(a\) et \(b\) soient premiers entre eux, ce qui n’est pas le cas ici.

Assertions 3 et 4 : deux résultats vrais à démontrer

Vrai. Soit \(d\) le PGCD de \(n\) et \(n + 6\). Alors \(d\) divise la différence \((n + 6) – n = 6\), donc \(d\) est un diviseur positif de 6, c’est-à-dire 1, 2, 3 ou 6. Le cas \(n = 0\) donne d’ailleurs \(\text{PGCD}(0, 6) = 6\), qui convient aussi.
Vrai. Modulo 7, le petit théorème de Fermat donne \(n^7 \equiv n\) pour tout entier \(n\). Modulo 3, il donne \(n^3 \equiv n\), donc \(n^7 = n^3 \times n^3 \times n \equiv n^3 \equiv n\). Modulo 2, enfin, \(n^7\) et \(n\) ont la même parité. Ainsi 2, 3 et 7 divisent \(n^7 – n\). Comme ces nombres premiers sont distincts, donc premiers entre eux deux à deux, leur produit 42 divise \(n^7 – n\).

Barème : 1 point par assertion, dont 0,25 pour la réponse et 0,75 pour la justification ; une réponse sans justification vaut 0.

Piège classique : conclure qu’un produit divise un entier parce que chaque facteur le divise, sans vérifier que ces facteurs sont premiers entre eux deux à deux.

Exercice 5 – Problème : un chiffrement par puissances modulo 17 (5 points)

On a \(16 = 5 \times 3 + 1\), donc \(3 \times (-5) = 1 – 16 \equiv 1 \pmod{16}\). Puis \(-5 \equiv 11 \pmod{16}\), et l’on vérifie que \(3 \times 11 = 33 = 2 \times 16 + 1\). Si \(d^{\prime}\) convient aussi, alors \(3d \equiv 3d^{\prime}\), et en multipliant par 11, \(d \equiv d^{\prime} \pmod{16}\). L’unique entier cherché est donc \(d = 11\).
Si \(p\) est un nombre premier et si \(a\) est un entier non divisible par \(p\), alors \(a^{p-1} \equiv 1 \pmod{p}\). Comme 17 est premier, on a donc \(m^{16} \equiv 1 \pmod{17}\) pour tout \(m \in \{1, \ldots, 16\}\).

Questions 3 à 5 : déchiffrer, puis comprendre le choix de l’exposant

Pour \(m = 0\), l’égalité \(0^{33} = 0\) suffit. Pour \(m \in \{1, \ldots, 16\}\), on écrit \(m^{33} = \left(m^{16}\right)^2 \times m \equiv 1 \times m \pmod{17}\). Ensuite, \(c \equiv m^3 \pmod{17}\), donc \(c^{11} \equiv m^{33} \equiv m \pmod{17}\). Comme \(m\) appartient à \(\{0, \ldots, 16\}\), c’est exactement le reste de \(c^{11}\) modulo 17 : Malik retrouve bien le message.
On calcule successivement \(5^2 = 25 \equiv 8\), puis \(5^4 \equiv 64 \equiv 13\), et \(5^8 \equiv 169 \equiv 16 \equiv -1 \pmod{17}\). Par conséquent, \(5^{11} = 5^8 \times 5^2 \times 5 \equiv -1 \times 8 \times 5 = -40 \equiv 11 \pmod{17}\). Vérification : \(11^3 = 1331 = 78 \times 17 + 5\). Le message envoyé est donc \(m = 11\).
Comme \(16 \equiv -1 \pmod{17}\), on a \(16^4 \equiv (-1)^4 = 1\), tandis que \(1^4 = 1\) : les messages 1 et 16 reçoivent le même code. Le codage n’est donc pas injectif, si bien qu’aucun décodage ne peut fonctionner. Ce défaut vient de ce que \(\text{PGCD}(4, 16) = 4 \neq 1\) : aucun entier \(d\) ne vérifie \(4d \equiv 1 \pmod{16}\), car \(4d – 16k\) est toujours multiple de 4. L’exposant de codage doit donc être premier avec 16.

Barème : 1) division et valeur de \(d\) (0,75), unicité (0,25) ; 2) 0,5 point ; 3) cas \(m = 0\) (0,25), calcul de \(m^{33}\) (0,75), conclusion sur le reste (0,5) ; 4) puissances successives (0,5), résultat (0,25) et vérification (0,25) ; 5) contre-exemple (0,5) et lien avec le PGCD (0,5).

Piège classique : appliquer le petit théorème de Fermat à \(m = 0\). L’hypothèse « \(p\) ne divise pas \(a\) » est alors fausse, donc ce cas se traite à part.

À retenir de ce contrôle

Pour remonter l’algorithme d’Euclide, on exprime chaque reste à partir des deux précédents, en partant de la dernière division non nulle.
L’équation ax + by = c a des solutions entières si et seulement si le PGCD de a et b divise c ; le lemme de Gauss donne alors toutes les solutions.
La valuation p-adique d’un produit est la somme des valuations, et celle du PGCD est le minimum des valuations des deux nombres.
Si p est premier et ne divise pas a, alors a puissance p − 1 est congru à 1 modulo p : on réduit donc l’exposant modulo p − 1.
Un contre-exemple numérique explicite suffit à réfuter une assertion universelle, alors qu’une assertion vraie exige une démonstration générale.

Revenir à l’énoncé du contrôle

Consolider équations diophantiennes et valuations après ce corrigé

Pour ne plus perdre de points sur ce thème, relisez le cours pgcd, bézout, gauss et nombres premiers dans z ; entraînez-vous sur les exercices pgcd, bézout, gauss et nombres premiers dans z.

D’autres évaluations corrigées vous attendent sur la page contrôles de maths en MPSI.

Autres corrigés sur le même thème

Voter.. post