Identitat de Bézout

Étienne Bézout

La identitat de Bézout o Lema de Bézout és una teorema elemental de teories de números que enuncia que si $a$ i $b$ són número entero diferents de zero en màxim comú divisor $d$, llavors existixen sancers $x$ i $y$ tals que:

$ax+by=d$.

Dit d'una atra manera, per a tot $a$ i $b$, existixen un $x$ i un $y$ tals que:

$ax+by=\mathrm{MCD}(a,b)$.

Més encara, $\mathrm{MCD}(a,b)$ és l'element mínim positiu del conjunt de combinacions llineals sanceres $\{ax+by\}$.

L'identitat va ser nomenada en honor del matemàtic francés Étienne Bézout (1730-1783).

Algoritme

Els números $x$ i $y$ de l'identitat de Bézout poden determinar-se per mig del algoritme estés de Euclides, pero no es determinen de forma unívoca, ya que:

$a(x-k\frac{b}{d})+b(y+k\frac{a}{d})=ax-k\frac{ab}{d}+by+k\frac{ab}{d}=ax+by$

en $d=\mathrm{MCD}(a,b)$ para tot $a,b,x,y$ i $k$. Aixina donant a $k$ qualsevol valor sancer i definint:

$x^{\prime }=x-kb{y}^{\prime }=y+ka$,

es té que:

$a{x}^{\prime }+b{y}^{\prime }=ax+by$.

De fet, el conjunt de totes les solucions

$(x,y)$

es pot construir com:

$(x-k\frac{b}{d},y+k\frac{a}{d}),$

en

$d=\mathrm{MCD}(a,b)$

i

$(x,y)$

una solució particular.

Demostració

La demostració clàssica inicia considerant el conjunt de les combinacions llineals sanceres $ax+by$ dels sancers $a,b$ daus: $S=\{ax+by:x,y\in \mathbb{Z}\text{ y }ax+by>0\}$. El conjunt $S$ és no buit, puix conté a $a$ o a $-a$ en funció del signe de $a$ (per a $x=\pm 1$, $y=0$). Com $S$ és un conjunt no buit de sancers positius, pel principi de bona ordenació, té un mínim.Siga puix $d$ el mínim element (positiu) d'eixe conjunt. Com $d\in S$, tenim que és de la forma $d=as+bt$, en $s,t\in \mathbb{Z}$. Vorem ara que, de fet, $d=\mathrm{MCD}(a,b)$. Per a demostrar-ho, devem vore que $d$ dividix a $a$ i a $b$ i que per a qualsevol atre divisor comú $c$, es té que $c\le d$.

La demostració d'açò es basa en l'algoritme de la divisió euclídea.

Considerem la divisió euclídea de $a$ entre $d$. Tenim que existixen $q,r\in \mathbb{Z}$ (el cocient i el restant, respectivament) tals que $a=qd+r,0\le r<d$. Observem que $r\in S\cup \{0\}$, puix $0\le r=a-qd=a-q(as+bt)=a(1-qs)-b(qt)$ i $1-qs,qt\in \mathbb{Z}$, puix $q,s,t\in \mathbb{Z}$. No obstant, $0\le r<d$ i $d$ és el sancer positiu més chicotet de $S$, per lo que $r\notin S$ i, necessàriament, $r=0$. Açò demostra que $d$ dividix a $a$, puix $r$ era el restant de la divisió. De manera similar, es demostra que $d$ dividix a $b$.

Finalment, siga $c$ qualsevol atre divisor comú de $a$ i $b$, açò és, existixen $u,v\in \mathbb{Z}$ tals que $a=cu,b=cv$. Es té llavors que $d=as+bt=cus+cvt=c(us+vt)$, és dir, $c$ dividix a $d$, pero com $d>0$ per ser un element de $S$, es té que $c\le d$.

Aixina, es conclou que $d=\mathrm{MCD}(a,b)$, de manera que $\mathrm{\exists }x,y\in \mathbb{Z}$ tals que $\mathrm{MCD}(a,b)=ax+by$. $◻$

Vore també

• Equació diofántica llineal