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:

${\displaystyle \operatorname {lnko} (a,b)=s\cdot a+t\cdot b}$, ahol ${\displaystyle 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

${\displaystyle 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.^[1] Azonban az egészekre vonatkozó bizonyítást már Claude Gaspard Bachet de Méziriac (1581–1638) ismerte.^[2][3][4]

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ó:

${\displaystyle \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

${\displaystyle {\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 ${\displaystyle x=s\cdot a+t\cdot b}$ alakban, ahol ${\displaystyle s,t\in \mathbb {Z} }$. Legyen ezek között ${\displaystyle d=s\cdot a+t\cdot b}$ a legkisebb abszolút értékű. Mivel ${\displaystyle \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 ${\displaystyle a=q\cdot d+r}$, valamely egész q-ra és ${\displaystyle 0\leq r<d}$-re. Visszahelyettesítve az ${\displaystyle s\cdot a+t\cdot b}$ egyenletbe, és r-re megoldva kapjuk, hogy ${\displaystyle r=(1-q\cdot s)\cdot a+(-q\cdot t)\cdot b}$. A d szám minimalitása miatt ${\displaystyle r=0}$, ezért d osztója a-nak. Hasonlóan, d osztója b-nek is, emiatt ${\displaystyle d\leq \operatorname {lnko} (a,b)}$. De már láttuk, hogy d osztható ${\displaystyle \operatorname {lnko} (a,b)}$-val. Tehát ${\displaystyle d=\operatorname {lnko} (a,b)}$.

Főideálgyűrűkben

A gyűrűelmélet ideáljait használva van egy ${\displaystyle \operatorname {lnko} (a,b)\;R}$ főideál, amely tartalmazza az ${\displaystyle aR}$ és az ${\displaystyle bR}$ ideálokat. Az ideálok szintén gyűrűk, ezért ${\displaystyle aR+nR}$ is része ennek az ideálnak. Speciálisan, ha ${\displaystyle R=\mathbb {Z} }$, vagy a gyűrű euklideszi, akkor ${\displaystyle aR+bR=cR}$, ahol ${\displaystyle 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ó:

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

ekkor vannak ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ egészek, hogy

${\displaystyle 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