PGCD, théorèmes de Bézout et de Gauss

Introduction :

Dans ce cours, nous allons d’abord aborder la notion de PGCD\text{PGCD} de deux nombres entiers, et montrer comment le déterminer à l’aide de l’algorithme d’Euclide. Dans le cas où le PGCD\text{PGCD} des deux nombres est égal à 11, nous verrons que les deux nombres entiers seront dits « premiers entre eux ».
Ensuite, nous présenterons deux théorèmes importants d’arithmétique, les théorèmes de Bézout et de Gauss, et nous les utiliserons pour résoudre des équations diophantiennes. 

PGCD\text{PGCD} et algorithme d’Euclide

PGCD\text{PGCD}

Tout d’abord, il faut noter que par convention dans ce cours, lorsqu’on parlera de diviseurs d’un entier naturel, il s’agira toujours de diviseurs positifs.
Commençons par voir les diviseurs communs à deux nombres. Pour cela, quelques notations sont à connaître.

  • Pour tout entier naturel aa, on note D(a)\text D(a) l’ensemble des diviseurs de aa.
bannière exemple

Exemple

  • L’ensemble des diviseurs de 00 est l’ensemble des entiers naturels : D(0)=N\text D(0)=\mathbb N.
  • L’ensemble des diviseurs de 11 est 11 : D(1)={1}\text D(1)=\lbrace1\rbrace.
bannière propriete

Propriété

Comme 11 peut diviser tous les entiers, l’ensemble D(a)\text D(a) des diviseurs de aa contient toujours au moins 11 et aa lui-même.
Par ailleurs, le plus grand élément des diviseurs de aa est aa (quand a0a\neq 0).

  • Pour tous entiers naturels aa et bb non nuls, on note D(a ;b)\text D(a\ ;\,b) l’ensemble des diviseurs communs à aa et à bb.
bannière à retenir

À retenir

Quelques remarques s’imposent :

  • D(a ;b)\text D(a\ ;\,b) est non vide puisqu’il contient toujours au moins 11.
  • Tous les nombres que contient D(a ;b)\text D(a\ ;\,b) sont inférieurs ou égaux à aa et à bb.
bannière exemple

Exemple

Intéressons-nous aux diviseurs de 2828 et 6363 :

D(28)={1,2,4,7,14,28}D(63)={1,3,7,9,21,63}\begin{aligned} \text{D}(28)&=\lbrace 1,\,2,\,4,\,7,\,14,\,28 \rbrace \ \text{D}(63)&=\lbrace 1,\,3,\,7,\,9,\,21,\,63 \rbrace \ \end{aligned}

Ainsi, les diviseurs communs à 2121 et 6363 sont 11 et 77 :

D(28 ;63)={1,7}\text{D}(28\ ;\,63)= \lbrace 1,\,7 \rbrace

Dans l’exemple ci-dessus, nous voyons que 77 est le plus grand diviseur commun à 2828 et 6363.

  • Nous allons ainsi définir la notion de plus grand commun diviseur (PGCD\text{PGCD}).
bannière definition

Définition

PGCD\bold{PGCD} :

aa et bb sont deux entiers naturels non nuls.
En admettant que toute partie non vide et majorée de N\mathbb N possède un plus grand élément, le plus grand élément de D(a ;b)\text D(a\ ;\,b) est appellé plus grand commun diviseur (PGCD\text{PGCD}) de aa et bb.

  • Il est noté : PGCD(a ;b)\text{PGCD} (a\ ;\,b) .
bannière à retenir

À retenir

Cette définition peut s’étendre aux entiers relatifs.
Dans le cas d’entiers négatifs, nous nous ramenons à des entiers positifs en prenant leurs valeurs absolues.
Et nous avons, avec aa et bb des entiers relatifs :

PGCD(a ;b)=PGCD(a ;b)\text{PGCD}(a\ ;\,b)=\text{PGCD}(\vert a \vert\ ;\,\vert b \vert)

Ainsi, si aa divise bb, alors le PGCD\text {PGCD} de aa et bb est égal à la valeur absolue de aa :

PGCD(a ;b)=a\text{PGCD} (a\ ;\,b)=\vert a\vert

Donnons maintenant quelques propriétés qui vont compléter cette notion de PGCD\text {PGCD}.

bannière propriete

Propriété

aa et bb sont deux entiers naturels supérieurs ou égaux à 22.

  • Si, dans leur décomposition en produit de facteurs premiers, aa et bb n’ont pas de facteur premier commun, leur PGCD\text {PGCD} est 11 :

PGCD(a ;b)=1\text {PGCD}(a\ ;\,b)=1

  • Sinon, le PGCD\text {PGCD} de aa et de bb est égal au produit des facteurs premiers communs à aa et à bb, chacun d’eux étant affecté du plus petit exposant figurant dans la décomposition de aa et dans celle de bb.
bannière exemple

Exemple

Pour déterminer le PGCD\text {PGCD} de 20702\,070 et 368368, on décompose ces nombres en produits de facteurs premiers :

2070=2×32×5×23368=24×23\begin{aligned} 2\,070&=2\times3^2\times5\times23 \ 368&=2^4\times23 \end{aligned}

Donc le PGCD\text {PGCD} de 20702\,070 et 368368 est égal au produit de leurs facteurs premiers commun, 22 et 2323, soit 4646 :

PGCD(2070 ;368)=2×23=46\begin{aligned} \text{PGCD} (2\,070\ ;\,368)&=2\times23 \ &=46 \end{aligned}

Nous reviendrons plus longuement sur la décomposition en facteurs premiers dans le prochain cours.

bannière propriete

Propriété

Si le PGCD(a ;b)\text{PGCD}(a\ ;\, b) est un entier strictement positif, nous avons :

PGCD(a ;a)=aPGCD(a ;1)=1PGCD(a ;0)=aPGCD(a ;b)=PGCD(b ;a)=PGCD(a ;b)\begin{aligned} \text{PGCD} (a\ ;\,-a)&=\vert a\vert \ \text{PGCD} (a\ ;\,1)&=1 \ \text {PGCD} (a\ ;\,0)&=\vert a\vert \ \ \text{PGCD} (a\ ;\,b)&=\text{PGCD} (b\ ;\,a) \ &=\text{PGCD} (\vert a\vert\ ;\,\vert b\vert) \end{aligned}

Les diviseurs communs à aa et bb sont les diviseurs de leur PGCD\text{PGCD}.

Pour tous les entiers relatifs non nuls aa et bb, et tout cc de l’ensemble des entiers naturels strictement positifs N\mathbb N^* :

PGCD(ac ;bc)=c×PGCD(a ;b) \text{PGCD} (ac\ ;\,bc)=c\times\text{PGCD} (a\ ;\,b)

Algorithme d’Euclide

Nous allons dans cette partie voir un algorithme qui permet de déterminer le PGCD\text{PGCD} de deux nombres : l’algorithme d’Euclide.
Il s’agit d’effecteur plusieurs divisions euclidiennes consécutives en utilisant, lors d’une dernière étape, une propriété pour obtenir le PGCD\text{PGCD}.

bannière theoreme

Théorème

aa et bb sont deux entiers naturels non nuls tels que la division euclidienne de aa par bb se traduit par a=bq+ra=bq+r, avec 0r<b0 \leq r < b.

Alors l’ensemble des diviseurs communs à aa et bb est identique à ceux communs à bb et rr, car r=abqr=a-bq :

D(a ;b)=D(b ;r)Ce qui ameˋne aˋ : PGCD(a ;b)=PGCD(b ;r)\begin{aligned} \text D(a\ ;\,b)&=\text D(b\ ;\,r) \ \textcolor{#A9A9A9}{\text{Ce qui amène à\ : }} \text{PGCD}(a\ ;\,b)&=\text{PGCD}(b\ ;\,r) \end{aligned}

bannière demonstration

Démonstration

  • Démontrons que, si dd divise aa et bb, alors dd divise bb et rr.

Si dd divise aa et bb, dd divise toute combinaison linéaire de aa et bb, donc en particulier abqa-bq, soit rr.

  • Il en résulte que l’ensemble des diviseurs de aa et bb sont inclus dans les diviseurs de bb et rr :

D(a ;b)D(b ;r)\text D(a\ ;\,b)\subset\text D(b\ ;\,r)

  • Démontrons que, si δ\delta divise bb et rr, alors δ\delta divise aa et bb.

Si δ\delta divise bb et rr, δ\delta divise toute combinaison linéaire de bb et rr, donc en particulier bq+rbq+r, soit aa.

  • Il en résulte que l’ensemble des diviseurs de bb et rr figurent parmi les diviseurs de aa et bb :

D(b ;r)D(a ;b)\text D(b\ ;\,r)\subset\text D(a\ ;\,b)

  • La double inclusion équivaut donc à dire que l’ensemble des diviseurs communs à aa et bb sont communs à ceux de bb et rr :

D(a ;b)=D(b ;r)\text D(a\ ;\,b)=\text D(b\ ;r)

  • Ces deux ensembles étant identiques, ils ont le même plus grand élément, donc :

PGCD(a ;b)=PGCD(b ;r)\text{PGCD}(a\ ;\,b)=\text{PGCD}(b\ ;\,r)

bannière à retenir

À retenir

Lorsque bb ne divise pas aa, le PGCD\text{PGCD} de aa et bb est le dernier reste non nul dans la succession des divisions de l’algorithme d’Euclide, dont nous allons montrer un exemple ci-dessous.

bannière exemple

Exemple

Reprenons le calcul du PGCD\text{PGCD} de 20702\,070 et 368368.
On écrit les divisions euclidiennes successives sous la forme a=bq+ra=bq+r, en remplaçant à chaque fois aa par le précédent bb, et bb par le précédent rr :

2070a=368b×5q+230r368b=230r×1+138230=138×1+92138=92×1+4692=46×2+0\begin{aligned} \overbrace{2\,070}^\textcolor{#A9A9A9}a&=\overbrace{368}^\textcolor{#A9A9A9}b\times\overbrace 5^\textcolor{#A9A9A9}q+\overbrace{230}^\textcolor{#A9A9A9}r \ \overbrace{368}^\textcolor{#A9A9A9}b&=\overbrace{230}^\textcolor{#A9A9A9}r\times 1+138 \ 230&=138\times 1+92 \ 138&=92\times 1+46 \ 92&=46\times 2+0 \end{aligned}

  • PGCD(2070 ;368)=46\text{PGCD} (2\,070\ ; 368) = 46.

Donnons une rapide explication de ce résultat, en nous servant du théorème que nous avons vu plus haut :

PGCD(2070 ;368)=PGCD(368 ;230)[car PGCD(a ;b)=PGCD(b ;r)]=PGCD(230 ;138)=PGCD(138 ;92)=PGCD(92 ;46)=PGCD(46 ;0)=46 [car PGCD(a ;0)=a]\begin{aligned} \text{PGCD}(2\,070\ ;\,368) &= \text{PGCD}(368\ ;\,230) \ &\footnotesize{\textcolor{#A9A9A9}{\text{[car PGCD$(a\ ;\,b)=$PGCD$(b\ ;\,r)$]}}} \ &=\text{PGCD}(230\ ;\,138) \ &=\text{PGCD}(138\ ;\,92) \ &=\text{PGCD}(92\ ;\,46) \ &=\text{PGCD}(46\ ;\,0) \ &=46 \footnotesize{\textcolor{#A9A9A9}{\text{ [car PGCD$(a\ ;\,0)=\vert a\vert$]}}} \end{aligned}

Nombres entiers premiers entre eux

bannière definition

Définition

Nombres entiers premiers entre eux :

Dire que deux entiers naturels non nuls aa et bb sont premiers entre eux signifie que leur PGCD\text{PGCD} est égal à 11.

bannière attention

Attention

Ne pas confondre « nombres premiers entre eux » et « nombres premiers ».

  • Le prochain cours sera consacré à ces derniers.
bannière definition

Définition

Caractérisation du PGCD\text {PGCD} :

aa et bb sont deux entiers naturels non nuls.
Dire que dd est le PGCD\text {PGCD} de aa et bb équivaut à dire qu’il existe deux entiers naturels aa^{\prime} et bb^{\prime} tels que :

a=dab=dbPGCD(a ;b)=1\begin{aligned} a &= da^{\prime} \ b &= db^{\prime} \ \text {PGCD} (a^{\prime}\ ;\,b^{\prime}) &= 1 \end{aligned}

PGCD(a ;b)=1\text {PGCD} (a^{\prime}\ ;\, b^{\prime}) = 1 signifie que aa^{\prime} et bb^{\prime} sont premiers entre eux, c’est-à-dire qu’ils n’ont aucun diviseur en commun autre que 11.

bannière demonstration

Démonstration

Raisonnons par l’absurde et supposons que PGCD(a ;b)=d1\text {PGCD}(a^{\prime}\ ;\, b^{\prime}) = d^{\prime}\neq1, alors a=daa^{\prime}= d^{\prime}a^{\prime\prime} et b=dbb^{\prime} = d^{\prime}b^{\prime\prime}, où aa^{\prime\prime} et bb^{\prime\prime} sont des entiers naturels.

Par conséquent, a=ddaa = dd^{\prime}a^{\prime\prime} et b=ddbb = dd^{\prime}b^{\prime\prime}.
Ainsi, dddd^{\prime} (qui est strictement supérieur à dd) est un diviseur de aa et de bb, ce qui contredit PGCD(a ;b)=d\text {PGCD}(a\ ;\, b) = d.

  • Donc PGCD(a ;b)=1\text{PGCD}(a^{\prime}\ ;\, b^{\prime}) = 1.

Nous allons maintenant appliquer cette notion aux congruences, que nous avons découvertes dans le cours précédent.

bannière à retenir

À retenir

Pour deux entiers naturels non nuls aa et nn, si aa et nn sont premiers entre eux, alors aa admet un inverse modulo nn, c’est-à-dire qu’il existe un entier relatif xx tel que :

ax1[n]ax \equiv 1 \,\lbrack n\rbrack

Prenons un exemple, pour montrer comment déterminer l’inverse d’un nombre modulo nn.

bannière exemple

Exemple

Nous cherchons donc à déterminer un inverse de 33 modulo 1313.

33 et 1313 sont bien premiers entre eux, donc 33 admet bien un inverse modulo 1313.

  • Nous allons donc rechercher un entier relatif xx tel que 3x1[13]3x\equiv 1\,\lbrack13\rbrack.

3×1=33[13]3×2=66[13]3×3=99[13]3×4=1212[13]1[13]\begin{aligned} 3 \times 1 &= 3 \equiv 3 \,\lbrack13\rbrack \ 3 \times 2 &= 6 \equiv 6 \,\lbrack13\rbrack \ 3 \times 3 &= 9 \equiv 9 \,\lbrack13\rbrack \ 3 \times 4 &= 12 \equiv 12 \,\lbrack13\rbrack \equiv -1 \,\lbrack13\rbrack \end{aligned}

En multipliant par 1-1 la dernière relation, nous obtenons donc :

3×(4)1[13]3 \times (-4) \equiv 1 \,[13]

  • 4-4 est donc un inverse entier relatif de 33 modulo 1313.

Pour trouver une solution positive, nous pouvons passer la relation au carré :

(3×4)2(1)2[13]1[13]C’est-aˋ-dire : 3×4×3×41[13]Puis : 3×481[13]\begin{aligned} (3 \times 4)^2 &\equiv (-1)^2 \,\lbrack13\rbrack \ &\equiv 1\,\lbrack13\rbrack \ \textcolor{#A9A9A9}{\text{C’est-à-dire\ : }}3\times 4 \times 3 \times 4 &\equiv 1 \,\lbrack13\rbrack \ \textcolor{#A9A9A9}{\text{Puis\ : }}3\times 48 &\equiv 1 \,\lbrack13\rbrack \end{aligned}

  • 4848 est donc un inverse entier naturel de 33 modulo 1313.

Théorème de Bézout

Nous allons maintenant découvrir deux théorèmes importants d’arithmétique, en commençant par le théorème de Bézout, qui découle de l’égalité de Bézout (aussi appelée identité de Bézout).

bannière theoreme

Théorème

Égalité de Bézout :

Soit aa et bb sont deux entiers relatifs non nuls, et dd leur PGCD\text{PGCD}.
Il existe deux entiers relatifs uu et vv tels que au+bv=dau+bv = d.

bannière demonstration

Démonstration

Soit aa et bb sont deux entiers relatifs non nuls, et dd leur PGCD\text{PGCD}.

  • Démontrons que dd s’écrit sous la forme au+bvau+bv.
  • Soit ε\varepsilon l’ensemble des nombres de la forme au+bvau+bv, avec uZu \in\mathbb Z et vZv \in\mathbb Z.
  • L’ensemble ε\varepsilon n’est pas vide, car, par exemple pour u=1u = 1 et v=0v = 0, aεa\in \varepsilon. Il en est de même pour bb, en prenant u=0u = 0 et v=1v = 1.
  • ε\varepsilon contient des entiers strictement positifs (par exemple aa ou a-a) et, parmi eux, un plus petit que tous les autres.

Notons m=au1+bv1m = au1+bv1 ce plus petit élément, avec u1u1 et v1v1 deux entiers relatifs.

D’une part, d’après cette égalité, tout diviseur commun à aa et bb divise mm, donc leur PGCD d\text{PGCD}\ d divise mm.

  • On a donc dmd \leq m.
  • D’autre part, montrons que mm divise aa et bb.

La division euclidienne de aa par mm s’écrit a=mq+ra=mq+r, avec 0r<m0 \leq r < m. Soit :

r=amq=a(au1+bv1)q=a(1u1q)+b(v1q)=aU+bV [avec U=1u1q et V=v1q]\begin{aligned} r&=a-mq \ &=a-(au1+bv1)q \ &=a(1-u1q)+b(-v1q) \ &=aU+bV \footnotesize{\textcolor{#A9A9A9}{\text{ [avec $U=1-u_1q$ et $V=-v_1q$]}}} \end{aligned}

UU et VV, comme produit et somme d’entiers relatifs, sont aussi des entiers relatifs. Ainsi, rεr\in\varepsilon.

Or, mm est le plus petit entier strictement positif de ε\varepsilon, donc, comme 0r<m0\leq r, nécessairement r=0r=0.

  • Ainsi, mm divise aa. On montre de même que mm divise bb.
  • mm est un diviseur commun à aa et bb vérifiant dmd \leq m.

Or, dd est le plus grand nombre vérifiant cette propriété, donc d=md = m.

  • On a donc d=au1+bv1d = au1+bv1, avec u1u1 et v1v1 deux entiers relatifs.

Voyons maintenant le théorème de Bézout, cas particuliers lorsque les nombres aa et bb sont premiers entre eux.

bannière theoreme

Théorème

Théorème de Bézout :

Soit aa et bb deux entiers relatifs non nuls.
Dire que aa et bb sont premiers entre eux équivaut à dire qu’il existe deux entiers relatifs uu et vv tels que au+bv=1au+bv = 1.

bannière demonstration

Démonstration

Soit aa et bb sont deux entiers relatifs non nuls.

  • Si aa et bb sont premiers entre eux, alors leur PGCD\text{PGCD} est 11.
  • D’après l’égalité de Bézout, il existe deux entiers relatifs uu et vv tels que au+bv=1au+bv = 1, car d=1d = 1.
  • Réciproquement, s’il existe deux entiers relatifs uu et vv tels que au+bv=1au+bv = 1, le PGCD\text{PGCD} de aa et de bb divise auau ,\,et bvbv, et donc aussi leur somme au+bv=1au +bv = 1.
  • Le PGCD\text{PGCD} de aa et de bb est donc 11, c’est-à-dire que les nombres aa et bb sont premiers entre eux.
bannière à retenir

À retenir

En pratique, pour trouver uu et vv, on utilise d’abord l’algorithme d’Euclide pour démontrer que les deux nombres sont premiers entre eux.
Puis, on reprend chaque division euclidienne pour exprimer chaque reste au fur et à mesure.

  • On trouve ainsi le couple solution.

Nous allons prendre un exemple pour illustrer cette méthodologie.

bannière exemple

Exemple

Soit a=392a = 392 et b=33b = 33.

  • Nous cherchons uu et vv, entiers relatifs, tels que : au+bv=1au+bv=1.

Nous commençons par utiliser l’algorithme d’Euclide pour prouver que aa et bb sont premiers entre eux.
On écrit les divisions euclidiennes successives :

  • 392=33×11+29392= 33\times11+29
  • 33=29×1+433=29\times1+4
  • 29=4×7+129=4\times7+1
  • 4=1×4+04=1\times4+0

Donc PGCD(392 ;33)=1\text{PGCD}(392\ ; 33) = 1.

  • Ainsi, a=392a = 392 et b=33b = 33 sont premiers entre eux.

Ceci fait, et afin de trouver uu et vv, nous réécrivons les divisions euclidiennes en exprimant les restes.

  • 392=33×11+29392=33\times11+29, donc :

29=39233×11=a11b\begin{aligned} 29&=392-33\times11 \ &=a-11b \end{aligned}

  • 33=29×1+433=29\times1+4, donc :

4=3329×1=b(a11b)×1=12ba\begin{aligned} 4&=33-29\times1 \ &=b-(a-11b)\times 1 \ &=12b-a \end{aligned}

  • 29=4×7+129=4\times7+1, donc :

1=294×7=(a11b)(12ba)×7=8a95b\begin{aligned} 1&=29-4\times7 \ &=(a-11b)-(12b-a)\times 7 \ &=8a-95b \end{aligned}

  • Ainsi, a×8+b×(95)=1a\times8+b\times(-95)=1.
  • u=8u = 8 et v=95v = -95 sont les valeurs qui conviennent.

Théorèmes de Gauss et équation diophantienne

Voyons le deuxième théorème que nous évoquions, le théorème de Gauss.

Théorème de Gauss

bannière theoreme

Théorème

Théorème de Gauss :

Soit aa, bb et cc des entiers naturels non nuls.
Si aa divise le produit bcbc tout en étant premier avec bb, alors aa divise cc.

bannière à retenir

À retenir

Autrement dit, si un entier naturel divise un produit de deux facteurs et s’il est premier avec l’un d’eux, il divise l’autre.

Nous allons en donner la démonstration, rapide, et qui repose sur le théorème de Bézout.

bannière demonstration

Démonstration

Puisque aa et bb sont premiers entre eux, d’après le théorème de Bézout, il existe des entiers relatifs uu et vv tels que au+bv=1au + bv = 1.
Donc (ac)u+(bc)v=c(ac)u + (bc)v = c.

Or, aa divise acac et bcbc, donc aa divise acu+bcvacu + bcv.

  • Il en résulte que aa divise cc.
bannière theoreme

Théorème

Corollaires du théorème de Gauss :

  • Si un entier relatif nn est divisible par deux entiers relatifs aa et bb premiers entre eux, il est divisible par leur produit.
  • Si un nombre premier pp divise un produit abab, alors pp divise aa ou pp divise bb.

Entre autres, on se sert de ces notions dans la résolution d’équations diophantiennes, que nous allons découvrir dans le chapitre suivant.

Équation diophantienne 

bannière definition

Définition

Équation diophantienne :

Une équation diophantienne est une équation de la forme ax+by=cax+by=c où les coefficients aa, bb et cc sont des nombres entiers relatifs et dont les solutions recherchées xx et yy sont également des entiers relatifs.

bannière à retenir

À retenir

Pour que l’équation diophantienne ax+by=cax+by=c admette des solutions, il faut que cc soit un multiple de d=PGCD(a ;b)d = \text{PGCD}(a\ ;\,b).

Nous allons, à travers deux exemples, apprendre à résoudre des équations diophantiennes.

bannière exemple

Exemple

Commençons par déterminer les entiers xx et yy tels que 2x+3y=12x+3y=1.

  • On remarque que 2×(1)+3×1=12\times(-1)+ 3\times1= 1, donc le couple (1 ;1)(-1\ ;\, 1) est solution particulière de cette équation.
bannière astuce

Astuce

Une façon de trouver une solution particulière d’une équation diophantienne de la forme ax+by=cax+by=c (avec b0b\neq 0) est de l’écrire sous la forme y=caxby=\frac{c-ax}b, puis de chercher un xx tel que caxc-ax soit un multiple de bb.

  • Supposons que (x ;y)(x\ ;\, y) soit solution de 2x+3y=12x + 3y = 1.

2x+3y=12x + 3y = 1 implique :

2x+3y=2×(1)+3×12(x+1)=3(y+1)2x + 3y = 2\times(-1)+ 3\times 1\Leftrightarrow 2(x +1) = 3(-y +1)

  • Donc 33 divise 2(x+1)2(x +1).
  • Comme 33 est premier avec 22, d’après le théorème de Gauss, 33 divise (x+1)(x + 1).
  • Il existe donc un entier relatif kk tel que x+1=3kx + 1 = 3k, soit x=1+3kx = -1+ 3k.
  • En reportant la valeur de xx dans l’égalité 2(x+1)=3(y+1)2(x +1) = 3(-y +1), on obtient :

2×3k=3(y+1)y+1=2ky=12k\begin{aligned} 2\times 3k = 3(-y +1)&\Leftrightarrow -y +1= 2k \ &\Leftrightarrow y = 1- 2k \end{aligned}

  • Réciproquement, si x=1+3kx = -1+ 3k et y=12ky = 1- 2k, pour kk un entier relatif :

2x+3y=2(1+3k)+3(12k)=2+6k+36k=1\begin{aligned} 2x+3y &=2(-1+3k)+3(1-2k) \ &=-2+6k+3-6k \ &=1 \end{aligned}

  • Nous retrouvons bien : 2x+3y=12x+3y=1.
  • Les solutions de cette équation sont les couples (1+3k ;12k)(-1+3k\ ;\,1-2k) avec kZk\in\mathbb Z.
bannière exemple

Exemple

Déterminons maintenant les entiers xx et yy tels que 16x3y=416x - 3y = 4.

  • Donnons une façon d’identifier une solution particulière à cette équation :

16x3y=4y=16x43y=4(4x1)3\begin{aligned} 16x-3y=4 &\Leftrightarrow y=\dfrac{16x-4}3 \ &\Leftrightarrow y=\dfrac{4(4x-1)}3 \end{aligned}

Nous cherchons donc, pour le numérateur, un multiple de 44 et de 33.
Nous remarquons facilement que, avec x=1x=1, nous obtenons 4(4x1)=124(4x-1)=12.

  • Le couple (1 ;4)(1\ ;\,4) est une solution particulière de l’équation.

Nous allons appliquer la même méthodologie que dans le premier exemple.

  • Supposons que (x ;y)(x\ ;\, y) soit solution de 16x3y=416x - 3y=4.

16x3y=416x - 3y=4 implique :

16x3y=16×13×416(x1)=3(y4)16x - 3y = 16\times 1 - 3\times 4\Leftrightarrow16(x -1) = 3(y -4)

  • Donc 33 divise 16(x1)16(x -1).
  • Comme 33 est premier avec 1616, d’après le théorème de Gauss, 33 divise (x1)(x - 1).
  • Il existe donc un entier relatif kk tel que x1=3kx - 1 = 3k, soit x=1+3kx = 1+ 3k.
  • En reportant la valeur de xx dans l’égalité 16(x1)=3(y4)16(x -1) = 3(y -4), on obtient :

16×3k=3(y4)y4=16ky=4+16k\begin{aligned} 16\times 3k = 3(y - 4)&\Leftrightarrow y - 4 = 16k \ &\Leftrightarrow y = 4 + 16k \end{aligned}

  • Réciproquement, si x=1+3kx = 1+ 3k et y=4+16ky = 4 + 16k, pour kk un entier relatif :

16x3y=16(1+3k)3(4+16k)=16+48k1248k=4\begin{aligned} 16x - 3y &=16(1+3k) - 3(4+16k) \ &=16+48k-12-48k \ &=4 \end{aligned}

  • Nous retrouvons bien : 16x3y=416x-3y=4.
  • Les solutions de cette équation sont les couples (1+3k ;4+16k)(1+3k\ ;\, 4 + 16k), avec kZk\in\mathbb Z.

Conclusion :

Dans ce cours, nous avons vu la définition du PGCD\text{PGCD} de deux nombres entiers relatifs, qui est le plus grand diviseur commun de ces deux nombres, et du cas particulier des nombres premiers entre eux lorsque le PGCD\text{PGCD} est égal à 11.

Nous avons aussi vu l’égalité puis le théorème de Bézout, ainsi que le théorème de Gauss et son corollaire. Et enfin, nous avons introduit les équations diophantiennes et leur résolution.