Algorithme d’Euclide et diophantiennes : corrigé du contrôle de maths en L1
Voici le corrigé du contrôle de maths en L1 sur le thème « algorithme d’Euclide et diophantiennes », question par question.
Cette correction rédige le sujet comme une copie de licence complète. Le tableau d’Euclide étendu est rempli ligne par ligne, et chaque relation de Bézout est vérifiée par un calcul direct. Pour l’équation, vous verrez pourquoi le lemme de Gauss donne toutes les solutions, et pas seulement quelques-unes.
Les calculs de congruences détaillent ensuite chaque réduction d’exposant. La preuve d’Euclide sur les nombres premiers est rédigée avec soin, puis le problème s’achève sur une figure qui colore les scores atteignables. Comparez votre rédaction à celle-ci après avoir cherché seul, car le barème sépare toujours la justification du résultat.
L’énoncé complet se trouve ici : Algorithme d’Euclide et diophantiennes : contrôle de maths en L1.
Barème du contrôle corrigé : algorithme d’Euclide et diophantiennes
| Exercice | Points |
|---|---|
| 1. Algorithme d’Euclide étendu | 4 points |
| 2. Une équation diophantienne | 4 points |
| 3. Calculs modulo n et petit théorème de Fermat | 4 points |
| 4. Nombres premiers | 3 points |
| 5. Problème : les scores atteignables | 5 points |
| Total | 20 points |
Le corrigé détaillé : algorithme d’Euclide et diophantiennes
Exercice 1 – Algorithme d’Euclide étendu (4 points)
-
Les divisions successives s’écrivent \(1147 = 1 \times 851 + 296\), puis \(851 = 2 \times 296 + 259\), ensuite \(296 = 1 \times 259 + 37\) et enfin \(259 = 7 \times 37 + 0\). Les coefficients suivent la règle \(u_{k+1} = u_{k-1} – q_k u_k\), et de même pour \(v\).
\(k\) \(r_k\) \(q_k\) \(u_k\) \(v_k\) \(0\) \(1147\) \(1\) \(0\) \(1\) \(851\) \(1\) \(0\) \(1\) \(2\) \(296\) \(2\) \(1\) \(-1\) \(3\) \(259\) \(1\) \(-2\) \(3\) \(4\) \(37\) \(7\) \(3\) \(-4\) Le reste suivant est nul, donc le dernier reste non nul donne \(d = \mathrm{pgcd}(1147, 851) = 37\).
-
La dernière ligne fournit \(u = 3\) et \(v = -4\). En effet, \(1147 \times 3 = 3441\) et \(851 \times 4 = 3404\), donc \(1147 \times 3 – 851 \times 4 = 37\).
-
On divise par \(37\) : \(1147 = 31 \times 37\) et \(851 = 23 \times 37\), où \(23\), \(31\) et \(37\) sont premiers. Le PPCM prend alors chaque facteur premier avec son plus grand exposant : \(\mathrm{ppcm}(1147, 851) = 23 \times 31 \times 37 = 26381\). On retrouve d’ailleurs \(\frac{1147 \times 851}{37} = 31 \times 851 = 26381\).
-
Retirer d’un rectangle le plus grand carré possible revient à soustraire le petit côté du grand. Le nombre de carrés retirés à chaque étape est donc le quotient \(q_k\), et le rectangle restant a pour côtés deux restes consécutifs. Le découpage s’arrête quand le rectangle \(259 \times 37\) est pavé exactement, c’est-à-dire quand le reste devient nul. Ainsi, le côté des plus petits carrés est le dernier reste non nul, soit \(d = 37\).
Piège classique : calculer \(u_{k+1}\) avec le mauvais quotient. Chaque ligne se contrôle aussitôt, car \(1147\,u_k + 851\,v_k\) doit redonner \(r_k\).
Exercice 2 – Une équation diophantienne (4 points)
-
On a \(185 = 5 \times 37\), donc \(d = 37\) divise le second membre. En multipliant la relation de Bézout par \(5\), on obtient \(1147 \times 15 + 851 \times (-20) = 185\) : l’équation \((E)\) admet des solutions. De plus, \(1147 = 37 \times 31\), \(851 = 37 \times 23\) et \(185 = 37 \times 5\). Diviser par \(37\) donne alors une équation équivalente : \((E) \iff 31x + 23y = 5\).
-
D’après la question a, \((x_0, y_0) = (15, -20)\) convient. Vérification : \(31 \times 15 – 23 \times 20 = 465 – 460 = 5\).
-
Lemme de Gauss : si un entier \(a\) divise \(bc\) et si \(a\) est premier avec \(b\), alors \(a\) divise \(c\).
Soit \((x, y)\) une solution. Par différence avec \((x_0, y_0)\), il vient :
\[31(x – 15) = -23(y + 20).\]
Ainsi, \(23\) divise \(31(x – 15)\). Or \(23\) et \(31\) sont deux nombres premiers distincts, donc premiers entre eux. Le lemme de Gauss donne alors \(x – 15 = 23k\) avec \(k \in \mathbb{Z}\). En reportant, on obtient \(31 \times 23k = -23(y + 20)\), d’où \(y = -20 – 31k\).
Réciproquement, \(31(15 + 23k) + 23(-20 – 31k) = 465 – 460 = 5\) pour tout \(k\). Par conséquent, les solutions sont les couples \((15 + 23k, -20 – 31k)\) avec \(k \in \mathbb{Z}\).
-
La condition \(-10 \leq 15 + 23k \leq 10\) équivaut à \(-25 \leq 23k \leq -5\), donc à \(k = -1\). La solution cherchée est \((x, y) = (-8, 11)\) ; en effet, \(1147 \times (-8) + 851 \times 11 = -9176 + 9361 = 185\).
D’une part, \(x > 0\) équivaut à \(k > -\frac{15}{23}\), soit \(k \geq 0\). D’autre part, \(y > 0\) équivaut à \(k < -\frac{20}{31}\), soit \(k \leq -1\). Ces deux conditions sont incompatibles, donc aucune solution n’a ses deux composantes strictement positives.
Piège classique : écrire les solutions \((15 + 1147k, -20 – 851k)\). Sans diviser d’abord par le PGCD, on oublie une grande partie des solutions.
Exercice 3 – Calculs modulo n et petit théorème de Fermat (4 points)
-
Le cycle revient à \(1\) après six flèches, donc \(m = 6\). Comme \(2026 = 6 \times 337 + 4\), on obtient \(3^{2026} = \left(3^6\right)^{337} \times 3^4 \equiv 3^4 = 81 \pmod{7}\). Or \(81 = 11 \times 7 + 4\), donc le reste de \(3^{2026}\) modulo \(7\) vaut \(4\).
De même, pour tout \(n \in \mathbb{N}\), \(3^{6n+2} = \left(3^6\right)^n \times 9 \equiv 9 \equiv 2 \pmod{7}\). Il en résulte \(3^{6n+2} + 5 \equiv 7 \equiv 0 \pmod{7}\) : \(7\) divise \(3^{6n+2} + 5\).
-
Petit théorème de Fermat : si \(p\) est premier et ne divise pas \(a\), alors \(a^{p-1} \equiv 1 \pmod{p}\).
Ici, \(13\) est premier et ne divise pas \(5\), donc \(5^{12} \equiv 1 \pmod{13}\). Puisque \(122 = 12 \times 10 + 2\), on a \(5^{122} \equiv 5^2 = 25 \equiv 12 \pmod{13}\). Ainsi, le reste vaut \(12\).
-
On a \(11 \times 19 = 209 = 8 \times 26 + 1\), donc \(19\) est un inverse de \(11\) modulo \(26\). Si \(11x \equiv 7\), on multiplie par \(19\) : \(x \equiv 133 \equiv 3 \pmod{26}\), car \(133 = 5 \times 26 + 3\). Réciproquement, \(x \equiv 3\) donne \(11x \equiv 33 \equiv 7 \pmod{26}\). Finalement, les solutions sont les entiers \(x = 3 + 26k\), avec \(k \in \mathbb{Z}\).
-
On a \(42 = 2 \times 3 \times 7\). D’abord, \(n^7 \equiv n \pmod{7}\) pour tout \(n\) : c’est évident si \(7\) divise \(n\), et sinon Fermat donne \(n^6 \equiv 1\). Ensuite, modulo \(3\), Fermat donne de même \(n^3 \equiv n\), donc \(n^7 = \left(n^3\right)^2 n \equiv n^3 \equiv n\). Enfin, \(n^7\) et \(n\) ont la même parité, donc \(n^7 – n\) est pair.
Les nombres premiers distincts \(2\), \(3\) et \(7\) divisent donc \(n^7 – n\). Comme ils sont deux à deux premiers entre eux, leur produit le divise aussi. Par conséquent, \(42\) divise \(n^7 – n\) pour tout \(n \in \mathbb{Z}\).
Piège classique : appliquer Fermat sans vérifier que \(p\) ne divise pas \(a\). Dans la question d, le cas où \(7\) divise \(n\) se traite donc à part.
Exercice 4 – Nombres premiers (3 points)
-
Raisonnons par l’absurde : supposons qu’il n’existe qu’un nombre fini de nombres premiers \(p_1, p_2, \ldots, p_r\). Posons \(N = p_1 p_2 \cdots p_r + 1\). Comme \(N \geq 3\), il admet un diviseur premier \(p\), qui figure dans la liste : \(p = p_i\) pour un certain \(i\). Alors \(p\) divise \(N\) et le produit \(p_1 \cdots p_r\), donc il divise leur différence, égale à \(1\). C’est impossible, car \(p \geq 2\). Ainsi, l’ensemble des nombres premiers est infini.
-
Soit \(k\) un entier tel que \(2 \leq k \leq n\). Alors \(k\) divise \(n!\), puisque \(k\) en est un facteur, et \(k\) divise \(k\). Par suite, \(k\) divise \(n! + k\). De plus, \(1 < k < n! + k\), donc \(k\) est un diviseur strict de \(n! + k\) autre que \(1\). Par conséquent, \(n! + k\) est composé pour chaque \(k\) de \(2\) à \(n\).
Pour \(n = 1001\), on obtient les \(1000\) entiers consécutifs \(1001! + 2, \ldots, 1001! + 1001\). Aucun d’eux n’est premier, donc il existe \(1000\) entiers consécutifs composés.
Exercice 5 – Problème : les scores atteignables (5 points)
-
L’égalité se réécrit \(9(x – x^{\prime}) = 14(y^{\prime} – y)\). Ainsi, \(14\) divise \(9(x – x^{\prime})\). Or \(\mathrm{pgcd}(14, 9) = 1\), donc le lemme de Gauss donne \(14\) divise \(x – x^{\prime}\). Écrivons alors \(x – x^{\prime} = 14k\) : il vient \(9 \times 14k = 14(y^{\prime} – y)\), d’où \(y – y^{\prime} = -9k = -\frac{9}{14}(x – x^{\prime})\).
-
On a bien \(-27 + 28 = 1\). Soit \(n \in \mathbb{Z}\) : en multipliant par \(n\), on obtient \(n = 9(-3n) + 14(2n)\). La division euclidienne de \(-3n\) par \(14\) s’écrit ensuite \(-3n = 14q + x\) avec \(0 \leq x \leq 13\). Il en résulte :
\[n = 9(14q + x) + 28n = 9x + 14(9q + 2n).\]
Le couple \((x, y)\) avec \(y = 9q + 2n\) convient donc. Pour l’unicité, si \(n = 9x + 14y = 9x^{\prime} + 14y^{\prime}\) avec \(x, x^{\prime} \in \{0, \ldots, 13\}\), alors \(14\) divise \(x – x^{\prime}\), qui vérifie \(|x – x^{\prime}| \leq 13\). Ainsi \(x = x^{\prime}\), puis \(y = y^{\prime}\) d’après la question a. L’écriture existe et elle est unique.
-
Si \(y \geq 0\), l’écriture \(n = 9x + 14y\) utilise deux entiers naturels : \(n\) est atteignable. Réciproquement, supposons \(n = 9x^{\prime} + 14y^{\prime}\) avec \(x^{\prime}, y^{\prime} \in \mathbb{N}\). D’après la question a, \(x^{\prime} = x + 14k\) avec \(k \in \mathbb{Z}\). Comme \(x^{\prime} \geq 0\) et \(x \leq 13\), on a \(14k \geq -13\), donc \(k \geq 0\). De plus, \(y = y^{\prime} + 9k \geq 0\). Par conséquent, \(n\) est atteignable si et seulement si \(y \geq 0\).
Pour \(n = 103\), on a \(-3 \times 103 = -309 = 14 \times (-23) + 13\), donc \(x = 13\). Alors \(14y = 103 – 117 = -14\), soit \(y = -1 < 0\). Ainsi, \(103\) n’est pas atteignable, comme le confirme la figure.
-
Soit \(n \geq 104\), écrit \(n = 9x + 14y\) avec \(0 \leq x \leq 13\). Alors \(14y = n – 9x \geq 104 – 117 = -13\). Donc \(y > -1\), et comme \(y\) est entier, \(y \geq 0\). D’après la question c, tout entier \(n \geq 104\) est atteignable : \(103\) est le plus grand score impossible.
Piège classique : tester quelques valeurs de \(x\) et \(y\) pour conclure que \(103\) est impossible. Seule l’écriture unique de la question b permet une preuve complète.
À retenir de ce contrôle
- Dans l’algorithme d’Euclide étendu, chaque reste s’écrit a u + b v, et le dernier reste non nul est le PGCD.
- L’équation a x + b y = c a des solutions entières si et seulement si le PGCD de a et b divise c.
- Le lemme de Gauss donne la forme générale : on divise par le PGCD, puis on ajoute un multiple du coefficient opposé.
- Pour un nombre premier p qui ne divise pas a, la puissance a exposant p – 1 est congrue à 1 modulo p.
- Le produit des nombres premiers d’une liste finie, augmenté de 1, possède un diviseur premier absent de cette liste.
Revenir à l’énoncé du contrôle
Consolider algorithme d’Euclide et diophantiennes après ce corrigé
D’autres évaluations corrigées vous attendent sur la page contrôles de maths en L1.
Autres corrigés sur le même thème
Télécharger ou imprimer cette fiche «algorithme d'Euclide et diophantiennes : corrigé du contrôle de maths en L1» au format PDF afin de pouvoir travailler en totale autonomie.
