Algorithme d’Euclide et diophantiennes : contrôle de maths en L1
Voici un contrôle de maths en L1 sur le thème « algorithme d’Euclide et diophantiennes », avec son barème et un corrigé détaillé.
Ce contrôle continu d’une heure trente évalue le chapitre d’arithmétique des entiers relatifs. Vous commencerez par l’algorithme d’Euclide étendu, présenté en tableau, qui fournit un PGCD et une relation de Bézout. Ensuite, ces coefficients servent à résoudre une équation diophantienne, dont la solution générale repose sur le lemme de Gauss.
Un exercice de congruences mobilise alors le petit théorème de Fermat, puis vous démontrerez l’infinité des nombres premiers. Enfin, le problème décrit les scores obtenus avec deux valeurs de points. Faites ce sujet à la fin du chapitre, avant les polynômes, car il ne demande aucune notion sur ces derniers.
Ce qu’évalue le contrôle : algorithme d’Euclide et diophantiennes
L’essentiel du sujet
- NiveauL1
- Durée1 h 30
- Calculatriceinterdite
- Barèmesur 20
Chapitre : Divisibilité, algorithme d’Euclide et congruences (5 exercices)
Ce que ce devoir vérifie :
- Présenter l’algorithme d’Euclide étendu en tableau pour obtenir un PGCD et des coefficients de Bézout
- Résoudre une équation diophantienne du premier degré en justifiant la forme générale par le lemme de Gauss
- Calculer des restes modulo n grâce aux cycles de puissances et au petit théorème de Fermat
- Rédiger la preuve de l’infinité des nombres premiers et construire de longues suites d’entiers composés
- Décrire tous les scores obtenus avec deux valeurs entières premières entre elles
Avant de commencer le devoir
Dans le tableau d’Euclide, vérifiez chaque ligne par la relation \(r_k = a u_k + b v_k\) avant de passer à la suivante. Pour l’équation diophantienne, divisez d’abord par le PGCD, puis cherchez une solution particulière. Ensuite, une puissance modulo n se réduit grâce à un exposant qui donne 1, par exemple celui de Fermat. Enfin, contrôlez vos solutions en les reportant dans l’équation de départ, car une erreur de signe arrive vite.
Le sujet du contrôle : algorithme d’Euclide et diophantiennes
Exercice 1 – Algorithme d’Euclide étendu (4 points)
On pose \(a = 1147\) et \(b = 851\). La figure découpe un rectangle de côtés \(1147\) et \(851\) en carrés, en retirant chaque fois le plus grand carré possible.
On note \(r_0 = a\), \(r_1 = b\), puis \(r_{k+1}\) le reste de la division de \(r_{k-1}\) par \(r_k\), de quotient \(q_k\). Les entiers \(u_k\) et \(v_k\) vérifient \(r_k = a\,u_k + b\,v_k\) à chaque ligne.
| \(k\) | \(r_k\) | \(q_k\) | \(u_k\) | \(v_k\) |
| \(0\) | \(1147\) | \(1\) | \(0\) | |
| \(1\) | \(851\) | \(1\) | \(0\) | \(1\) |
| \(2\) | ||||
| \(3\) | ||||
| \(4\) |
- Recopier puis compléter le tableau, et en déduire \(d = \mathrm{pgcd}(1147, 851)\).
- Donner deux entiers \(u\) et \(v\) tels que \(1147u + 851v = d\), puis vérifier cette égalité par un calcul direct.
- Écrire \(1147\) et \(851\) comme produits de nombres premiers. Calculer ensuite leur PPCM.
- Expliquer pourquoi le côté des plus petits carrés de la figure est égal à \(d\).
Exercice 2 – Une équation diophantienne (4 points)
On cherche les couples d’entiers relatifs \((x, y)\) solutions de l’équation \((E) : 1147x + 851y = 185\). On pourra utiliser les résultats de l’exercice 1.
- Justifier que \((E)\) admet des solutions, puis qu’elle équivaut à \(31x + 23y = 5\).
- Déduire de l’exercice 1 une solution particulière \((x_0, y_0)\) de \((E)\).
- Énoncer le lemme de Gauss. Déterminer alors l’ensemble de toutes les solutions de \((E)\).
- Trouver l’unique solution telle que \(-10 \leq x \leq 10\). Montrer aussi qu’aucune solution n’a ses deux composantes strictement positives.
Exercice 3 – Calculs modulo n et petit théorème de Fermat (4 points)
La figure donne les restes modulo \(7\) des puissances successives de \(3\) : chaque flèche correspond à une multiplication par \(3\).
- Lire sur la figure le plus petit exposant \(m \geq 1\) tel que \(3^m \equiv 1 \pmod{7}\). En déduire le reste de \(3^{2026}\) modulo \(7\), puis montrer que \(7\) divise \(3^{6n+2} + 5\) pour tout \(n \in \mathbb{N}\).
- Énoncer le petit théorème de Fermat. Calculer ensuite le reste de la division de \(5^{122}\) par \(13\).
- Vérifier que \(11 \times 19 \equiv 1 \pmod{26}\), puis résoudre dans \(\mathbb{Z}\) la congruence \(11x \equiv 7 \pmod{26}\).
- Prouver que \(n^7 – n\) est divisible par \(42\) pour tout entier relatif \(n\).
Exercice 4 – Nombres premiers (3 points)
Dans cet exercice, on admet que tout entier \(N \geq 2\) possède au moins un diviseur premier.
- Démontrer que l’ensemble des nombres premiers est infini.
- Soit \(n \geq 2\). Montrer que les \(n – 1\) entiers consécutifs \(n! + 2, n! + 3, \ldots, n! + n\) sont tous composés. En déduire qu’il existe \(1000\) entiers consécutifs dont aucun n’est premier.
Exercice 5 – Problème : les scores atteignables (5 points)
Dans un jeu de fléchettes simplifié, chaque lancer rapporte soit \(9\) points, soit \(14\) points. Un entier \(n \geq 0\) est un score atteignable s’il existe deux entiers naturels \(x\) et \(y\) tels que \(n = 9x + 14y\). Par exemple, \(41 = 9 \times 3 + 14 \times 1\) est atteignable.
- Soit \(x, y, x^{\prime}, y^{\prime}\) des entiers relatifs tels que \(9x + 14y = 9x^{\prime} + 14y^{\prime}\). Prouver que \(14\) divise \(x – x^{\prime}\), puis exprimer \(y – y^{\prime}\) en fonction de \(x – x^{\prime}\).
- Vérifier que \(9 \times (-3) + 14 \times 2 = 1\). Démontrer ensuite que tout entier relatif \(n\) s’écrit de façon unique \(n = 9x + 14y\) avec \(x \in \{0, 1, \ldots, 13\}\) et \(y \in \mathbb{Z}\).
- Avec l’écriture de la question b, établir qu’un entier \(n \geq 0\) est atteignable si et seulement si \(y \geq 0\). Montrer alors que \(103\) n’est pas un score atteignable.
- Démontrer enfin que tout entier \(n \geq 104\) est un score atteignable.
Réviser algorithme d’Euclide et diophantiennes avant le contrôle
La page contrôles de maths en L1 regroupe les 25 sujets de l’année, et la page maths post-bac permet de changer d’année.
Sujets proches à faire ensuite
Télécharger ou imprimer cette fiche «algorithme d'Euclide et diophantiennes : contrôle de maths en L1» au format PDF afin de pouvoir travailler en totale autonomie.
![Multiplicités et factorisation dans R[X]](https://maths-pdf.fr/wp-content/uploads/2026/10/postbac-24702-300x169.jpg)
