Le PGCD et les théorèmes de Bézout et de Gauss sont le cœur de l'arithmétique des entiers : l'algorithme d'Euclide figure déjà dans les Éléments, et sa version étendue est due à Bachet (1612) puis à Bézout (1766). Ces outils servent à résoudre des équations en nombres entiers comme , à trouver un inverse modulo ou à étudier des problèmes de chiffrement. À la fin du chapitre, tu sauras calculer un PGCD, écrire une relation de Bézout, prouver que deux entiers sont premiers entre eux et résoudre une équation diophantienne.
Diviseurs et PGCD
Diviseurs d'un entier
Rappel : divise s'il existe un entier tel que . Pour lister les diviseurs positifs d'un entier , teste les entiers de à : chaque diviseur trouvé en fournit un second, .
Exemple
Diviseurs positifs de : on teste de à . On a , et ne divise pas . Les diviseurs positifs de sont donc , , , , , , , et .
Définition du PGCD
Soient et deux entiers non tous deux nuls. Leur plus grand commun diviseur, noté , est le plus grand entier qui divise à la fois et . On a , et si divise , alors .
Exemple
Les diviseurs positifs de sont , , , , , , et . Ceux qui divisent aussi sont , , , , et , donc . Pour de grands nombres, cette méthode est trop longue : on utilise l'algorithme d'Euclide.
L'algorithme d'Euclide
Propriété. Si avec et , entiers, alors les diviseurs communs à et sont exactement les diviseurs communs à et . Donc .
En effet, un diviseur commun à et divise , et un diviseur commun à et divise .
L'algorithme. Pour , divise par , puis par le reste obtenu, puis ce reste par le nouveau reste, et ainsi de suite. Les restes sont des entiers naturels strictement décroissants, donc l'un d'eux finit par être nul. Le PGCD est le dernier reste non nul.
Exemple
Calcul de :
Le dernier reste non nul est , donc .
Conséquence. Chaque division conserve les diviseurs communs : les diviseurs communs à et sont exactement les diviseurs de leur PGCD. Ici, ce sont ceux de : , , , , et , et leurs opposés.
L'identité de Bézout
Théorème. Soient et deux entiers non tous deux nuls, et . Il existe deux entiers et tels que . Un tel couple est un couple de Bézout ; il n'est pas unique.
Trouver un couple : l'algorithme d'Euclide étendu
Dans l'algorithme d'Euclide, isole chaque reste, puis remonte depuis l'avant-dernière division en remplaçant les restes un à un.
Exemple
Avec et : , et . On remonte :
Vérification : . Le couple convient.
Démonstration (à connaître)
Soit l'ensemble des entiers strictement positifs de la forme , avec et entiers. contient , donc il est non vide et admet un plus petit élément .
- divise : la division euclidienne donne avec , donc est de la forme . Si , serait un élément de plus petit que : impossible. Donc . De même, divise . Ainsi est un diviseur commun positif, et .
- divise et , donc divise , d'où .
Donc , c'est-à-dire .
Entiers premiers entre eux et théorème de Bézout
Deux entiers et sont premiers entre eux lorsque : leurs seuls diviseurs communs sont et . Ainsi et sont premiers entre eux, sans qu'aucun des deux soit premier : les diviseurs positifs de sont , , , , et seul divise .
Théorème de Bézout. et sont premiers entre eux si et seulement s'il existe deux entiers et tels que .
Exemples. Pour tout entier :
- , donc et sont premiers entre eux ;
- , donc et sont premiers entre eux.
Démonstration : si , l'identité de Bézout fournit et . Réciproquement, si , tout diviseur commun à et divise , donc vaut ou .
Attention
une égalité ne prouve pas que , seulement que le PGCD divise . Par exemple, , alors que .
Diviser par le PGCD
Propriété. Si , avec et , alors et sont premiers entre eux. En effet, s'écrit , et en divisant par : . Exemple : et , donc et sont premiers entre eux.
Application : inverse modulo
Si et sont premiers entre eux, une relation donne : est un inverse de modulo . Il permet de résoudre .
Exemple
Inverse de modulo . Euclide : , et . On remonte :
Donc . Comme , est un inverse de modulo : . Pour résoudre , multiplie par : , soit car et modulo . Réciproquement, si , alors .
Le théorème de Gauss
Théorème. Soient , et des entiers. Si divise et si et sont premiers entre eux, alors divise .
Exemple
Cherchons les couples d'entiers tels que . divise , et car . D'après le théorème de Gauss, divise : avec . Alors , soit . Réciproquement, . Les solutions sont les couples , .
L'hypothèse est indispensable : divise , mais ne divise ni ni ; ici .
Démonstration (à connaître). Comme , le théorème de Bézout donne deux entiers et tels que . En multipliant par : . Or divise , et divise donc : divise leur somme, c'est-à-dire .
Conséquence. Si et divisent et sont premiers entre eux, alors divise . En effet, et divise en étant premier avec , donc divise (Gauss) : et . Sans l'hypothèse, c'est faux : et divisent , mais ne divise pas .
Équations diophantiennes
On cherche les couples d'entiers tels que , avec , , entiers et , non nuls.
Existence de solutions
Propriété. L'équation admet des solutions entières si et seulement si divise .
- Si est solution, divise et , donc .
- Si , un couple de Bézout donne .
Ainsi, n'a aucune solution entière : ne divise pas .
La méthode, pas à pas
Exemple
Résoudre dans l'équation : .
- Simplifier. divise . En divisant par , équivaut à , avec et premiers entre eux.
- Solution particulière. : le couple convient. Si aucune ne saute aux yeux, multiplie un couple de Bézout par : donne .
- Soustraire. Si , en retranchant , on obtient , soit .
- Appliquer Gauss. divise et , donc divise : , . En reportant, , d'où et .
- Vérifier la réciproque. pour tout .
Les solutions de sont les couples , . Pour , on retrouve .
Les pièges
- Gauss sans son hypothèse. Avant d'écrire « divise », justifie que et sont premiers entre eux.
- Un PGCD lu dans n'importe quelle relation. ne donne pas : seule l'égalité permet de conclure.
- L'équation non simplifiée. Dans , Gauss ne s'applique pas à et : divise d'abord par leur PGCD.
- La réciproque oubliée. La méthode donne des conditions nécessaires : vérifie que les couples trouvés sont solutions.
- Deux paramètres différents. Dans , c'est le même dans les deux coordonnées.
- Une erreur de signe en remontant Euclide. Recalcule toujours à la fin.
- Une congruence divisée. De , on ne déduit pas : convient aussi. On ne simplifie que par un nombre inversible modulo , en multipliant par son inverse.
- « Premiers entre eux » confondu avec « premiers ». et sont premiers entre eux sans être premiers.
Ce qu'il faut retenir
- est le plus grand diviseur commun à et ; leurs diviseurs communs sont les diviseurs de leur PGCD.
- Si , alors ; par l'algorithme d'Euclide, le PGCD est le dernier reste non nul.
- Il existe des entiers et tels que (identité de Bézout).
- Théorème de Bézout : et sont premiers entre eux si et seulement s'il existe , entiers tels que .
- Si , et , alors et sont premiers entre eux.
- Si , alors est un inverse de modulo .
- Théorème de Gauss : si divise et , alors divise .
- a des solutions entières si et seulement si divise ; on les trouve par solution particulière, Gauss, puis réciproque.
À l'épreuve
En devoir surveillé, les calculs se posent à la main et les questions sont très codifiées :
- « Calculer par l'algorithme d'Euclide » : écris toutes les divisions et conclus par « le dernier reste non nul est… ».
- « Déterminer un couple tel que » : remonte ligne par ligne et termine par la vérification.
- « Montrer que et sont premiers entre eux » : exhibe une relation et cite le théorème de Bézout.
- « Résoudre dans l'équation » : souvent découpé en sous-questions (solution particulière, puis solutions générales). Le professeur attend le théorème de Gauss cité avec son hypothèse, la réciproque et l'ensemble des couples avec « ».
- Les démonstrations du cours, l'écriture du PGCD sous la forme et le théorème de Gauss, peuvent être demandées telles quelles.
Ce qui coûte des points : un théorème appliqué sans vérifier ses hypothèses, une réciproque oubliée, un couple de Bézout non vérifié, une réponse sans phrase de conclusion.