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:

$\operatorname {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ó:

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

Példa

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

${\begin{aligned}\vdots \\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\\\vdots \end{aligned}}$

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 $\operatorname {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\leq 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\leq \operatorname {lnko} (a,b)$. De már láttuk, hogy d osztható $\operatorname {lnko} (a,b)$-val. Tehát $d=\operatorname {lnko} (a,b)$.

Főideálgyűrűkben

A gyűrűelmélet ideáljait használva van egy $\operatorname {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=\operatorname {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ó:

$\operatorname {lnko} (a_{1},a_{2},\ldots ,a_{n})=d,$

ekkor vannak $x_{1},x_{2},\ldots ,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, ISBN 3-446-13079-9, S. 43
• Stephen Fletcher Hewson: A Mathematical Bridge: An Intuitive Journey in Higher Mathematics. World Scientific 2003, ISBN 9789812385550, S. 53ff