Le théorème de Bezout - Le théorème de Gauss
Fondamental : Propriétés
Soient
et
deux entiers relatifs non tous les deux nuls et
Il existe
et
entiers relatifs tels que
.L'ensemble des entiers
(
et
entiers relatifs ) est l'ensemble des multiples de
.
Preuve : On supposera que
et
sont des entiers naturels car
On fait une recherche de PGCD par l'algorithme d'Euclide : ( on suppose
)
De
, on peut écrire que :
avec
et
.
De
on peut écrire que
soit que :
Avec :
et
.
etc....
A chaque pas on exprime le reste comme combinaison linéaire de
et
.
Et comme le dernier reste non nul est le PGCD, au final on obtient donc :
.
________________________________________________________________________
Si maintenant on considère un entier
, comme
divise
et
,
divise
et donc divise
.
est donc un multiple de
.
Réciproquement si
est un multiple de
alors il existe un entier
tel que
.
Comme
en multipliant par
on obtient :
, soit :
donc tout multiple de
est bien une combinaison linéaire de
et
.
________________________________________________________________________
:
et
.
On a :
Cherchons donc un couple d'entiers
tels que
.
ce qui donne :
ce qui donne en remplaçant
:
ce qui donne en remplaçant
et
:
ce qui donne en remplaçant
et
:
Le couple cherché est donc :
Fondamental : Le théorème de Bezout
Deux entiers relatifs
et
sont premiers entre eux si et seulement si il existe deux entiers relatifs
et
tels que
.
Preuve :
Si
et
sont premiers entre eux, leur PGCD :
;
Donc il existe bien des entiers
et
tels que
( propriété précédente).
Réciproquement, s'il existe
et
tels que
, un diviseur commun à
et
divise
donc 1.
Donc
, ce qui entraîne que
et
sont premiers entre eux.
Fondamental : Le théorème de Gauss
Soient
,
et
trois entiers non nuls.
Si
divise
et est premier avec
alors il divise
.
Preuve :
divise
, il existe donc un entier
tel que
.
Comme
et
sont premiers entre eux, d'après le théorème de Bezout, il existe des entiers
et
tels que
.
En multipliant par
on obtient :
.
Soit :
ou encore :
Ce qui signifie bien que
.
Méthode : Comment déterminer tous les couples (u,v) tels que 71u+19v=1 ?
Précédemment on a vu que le couple
vérifie l'égalité :
.
On dira que le couple
est une solution particulière de l'équation :
.
Nous avons : si le couple
est solution :
.
En égalisant ces deux lignes on obtient :
.
Soit :
Cette dernière égalité nous permet d'affirmer que :
Comme
divise
et que
et
sont premiers entre eux, d'après le
,
divise
;
Il existe donc un entier
tel que
, et donc
.
De la même manière il existe un entier
tel que :
soit :
.
Réciproquement le couple
est solution si et seulement si
.
En développant :
Soit :
Donc si et seulement si :
.
Autrement dit si et seulement si :
.
En conclusion :
En posant
, les couples
solutions de
sont les couples :
pour
Remarque : Les équations diophantiennes
Une équation diophantienne est une équation du type
où
,
et
sont trois entiers non nuls.
et
étant les inconnues .
Résoudre une équation diophantienne c'est déterminer les couples d'entiers relatifs
solutions de cette équation.
On utilise la méthode présentée plus haut :
On détermine une solution particulière :
.On égalise les deux lignes :
.Ce qui donne :
.En appliquant le théorème de Gauss on obtient :
et
, où
sont des entiers relatifs.On établit la réciproque en précisant que le couple trouvé est solution si et seulement si
. En remplaçant il vient toujours que
;On conclut.
______________________________________________________________________________
On commence par chercher une solution particulière
à
.Il suffit ensuite de préciser que le couple
est une solution particulière à
.Le reste de la procédure est la même que précédemment.
_______________________________________________________________________________
Si
, on simplifie par
et on est ramené au premier cas.Si
où
est le PGCD de
et
, on simplifie par
et on est ramené au second cas.Si
ne divise pas
il n'y a pas de solutions.
