Bézout-lemma

A Bézout-lemma Étienne Bézout (1730-1783) nyomán a számelméletben azt állítja, hogy két egész szám, a és b legnagyobb közös osztója előáll a és b egész együtthatós lineáris kombinációjaként:

$\mathrm{lnko}(a,b)=s\cdot a+t\cdot b$, ahol $s,t\in \mathbb{Z}$, tehát egyik vagy mindkettő negatív is lehet. Ha a két szám relatív prím, akkor

$1=s\cdot a+t\cdot b$

Az s és a t együtthatók a kibővített euklideszi algoritmussal hatásosan számolhatók.

Az összefüggés minden főideálgyűrűben érvényes, még a nem kommutatívokban is.

Története

A lemmát Étienne Bézout (1730–1783) után nevezték el, aki polinomokra bizonyította. Azonban az egészekre vonatkozó bizonyítást már Claude Gaspard Bachet de Méziriac (1581–1638) ismerte.

Nem egyértelmű

A legnagyobb közös osztónak ez az előállítása nem egyértelmű, sőt, végtelen sok megoldás van. Adott (x, y) együtthatók esetén a többi megoldás így számolható:

$\{(x+\frac{kb}{\mathrm{lnko}(a,b)},y-\frac{ka}{\mathrm{lnko}(a,b)})\mid k\in \mathbb{Z}\}.$

Példa

Legyen a = 12 és b = 42, lnko(12, 42) = 6. Ekkor

$\begin{array}{c}⋮\\ 12& \times (-10)& +42& \times 3& =6\\ 12& \times (-3)& +42& \times 1& =6\\ 12& \times 4& +42& \times (-1)& =6\\ 12& \times 11& +42& \times (-3)& =6\\ 12& \times 18& +42& \times (-5)& =6\\ ⋮\end{array}$

Következményei

A Bézout-lemmának számos következménye van a matematikában, különösen a számelméletben, ahol elemi jelentőséggel bír. Levezethető belőle az Euklidesz-lemma, amiből bizonyítható a prímtényezős felbontás egyértelműsége.

Bizonyítása

A bizonyítás a maradékos osztás műveletén alapul, így minden euklideszi gyűrűre könnyen átvihető. Az s és a t együtthatók pozitívok és negatívok is lehetnek, így előállnak pozitív és negatív számok is $x=s\cdot a+t\cdot b$ alakban, ahol $s,t\in \mathbb{Z}$. Legyen ezek között $d=s\cdot a+t\cdot b$ a legkisebb abszolút értékű. Mivel $\mathrm{lnko}(a,b)$ osztója a-nak és b-nek is, így minden, az előző módon előálló számnak is osztója, tehát d-nek is. A maradékos osztás miatt $a=q\cdot d+r$, valamely egész q-ra és $0\le r<d$-re. Visszahelyettesítve az $s\cdot a+t\cdot b$ egyenletbe, és r-re megoldva kapjuk, hogy $r=(1-q\cdot s)\cdot a+(-q\cdot t)\cdot b$. A d szám minimalitása miatt $r=0$, ezért d osztója a-nak. Hasonlóan, d osztója b-nek is, emiatt $d\le \mathrm{lnko}(a,b)$. De már láttuk, hogy d osztható $\mathrm{lnko}(a,b)$-val. Tehát $d=\mathrm{lnko}(a,b)$.

Főideálgyűrűkben

A gyűrűelmélet ideáljait használva van egy $\mathrm{lnko}(a,b)R$ főideál, amely tartalmazza az $aR$ és az $bR$ ideálokat. Az ideálok szintén gyűrűk, ezért $aR+nR$ is része ennek az ideálnak. Speciálisan, ha $R=\mathbb{Z}$, vagy a gyűrű euklideszi, akkor $aR+bR=cR$, ahol $c=\mathrm{lnko}(a,b)$, mivel a főideálgyűrűkben minden ideál egy elemmel generálható. Ez az egyenlőség azt fejezi ki, hogy a c elem a és b lineáris kombinációként előáll, de közös osztójuk is, hiszen az általa generált ideál mindkettőt tartalmazza. Tehát főideálgyűrűkben a Bézout-lemma közvetlenül a definícióból adódik.

Több egészre

A lemma több egészre is általánosítható:

$\mathrm{lnko}(a_1,a_2,\dots ,a_n)=d,$

ekkor vannak $x_1,x_2,\dots ,x_n$ egészek, hogy

$a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=d,$

ahol d a legkisebb ilyen pozitív egész, és az összes ilyen alakú szám osztható d-vel. Az együtthatók előjelére nincs megkötés, lehetnek pozitívok, negatívok, vagy akár nullák is.

További információk

• Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat
• Alice és Bob - 21. rész: Alice és Bob titkosít

Források

• Kurt Meyberg: Algebra - Teil 1. Hanser 1980, Sablon:ISBN, S. 43
• Stephen Fletcher Hewson: A Mathematical Bridge: An Intuitive Journey in Higher Mathematics. World Scientific 2003, Sablon:ISBN, S. 53ff