Bézout' lemma

Bézout' lemma on väide, et täisarvude suurima ühisteguri saab esitada nende arvude täisarvuliste kordajatega lineaarkombinatsioonina.

See on nimetatud Étienne Bézout' auks.

Formuleeringud

Olgu $a$, $b$ täisarv, millest vähemalt üks ei ole null. Siis leiduvad täisarvud $x,y$ nii, et kehtib seos

SÜT$(a,b)=x\cdot a+y\cdot b.$

Seda väidet nimetatakse Bézout' lemmaks või Bézout' samasuseks. Täisarve $x,y$ nimetatakse Bézout' kordajateks.

Kui $a$ ja $b$ on ühisteguriteta (see on erijuht, kus SÜT$(a,b)=1$), siis leiduvad $s,t\in \mathbb {Z}$ nii, et

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

Peale selle kehtib ka pöördväide: kui leiduvad $s,t\in \mathbb {Z}$ nii, et $sa+tb=1$, siis SÜT$(a,b)=1$.

Kordajaid $s$ ja $t$ saab laiendatud Eukleidese algoritmi abil efektiivselt arvutada.

Lemmat saab üldistada enamale kui kahele täisarvule: kui $a_{1},\dotsc ,a_{n}$ on täisarvud, siis leiduvad täisarvulised kordajad $s_{1},\dotsc ,s_{n}$ nii, et

$s_{1}a_{1}+\dotsb +s_{n}a_{n}=$ SÜT$(a_{1},\dotsc ,a_{n})$.

Küsimusega, milliseid arve saab esitada isegi naturaalarvuliste kordajatega, tegeleb mündiprobleem.

On ka Bézout' lemma variant, mis piirdub naturaalarvudega:

Olgu $a$, $b$ naturaalarvud. Siis leiduvad naturaalarvud $x,y$ nii, et kehtib seos

SÜT$(a,b)=x\cdot a-y\cdot b.$

Kui kasutada ringi ideaali mõistet, siis peaideaalid $aR$ ja $bR$ sisalduvad peaideaalis SÜT$(a,b)\;R.$ Järelikult sisaldub ka ideaal $aR+bR$ ideaalis SÜT$(a,b)\;R.$ Bézout' lemma võib formuleerida ka nii, et täisarvude ringis $R=\mathbb {Z}$ (või üldse Eukleidese ringides) kehtib

$aR+bR=cR$, kui $c=$ SÜT$(a,b).$

Näited

• SÜT$(12,30)=6.$ Kehtib

  $6=3\cdot 12+(-1)\cdot 30$

  • Suurimat ühistegurit saab liidetavateks lahutada ka teisiti, näiteks: $6=(-2)\cdot 12+1\cdot 30.$

Tõestus

Lemma tõestus põhineb jäägiga jagamisel. Seetõttu on seda kerge üle kanda Eukleidese ringidele.

Juhul, kui $a=0,$ võib võtta $s=0$ ja $t=\pm 1$, järelikult võib üldisust kitsendamata eeldada, et $a\neq 0.$. Kõikide arvude $x=s\cdot a+t\cdot b$ seas, kus $s,t\in \mathbb {Z} ,$ on kindlasti ka positiivseid arve. Olgu $d=s\cdot a+t\cdot b$ vähim nende seas (see samm kasutab positiivsete täisarvude hulga täielikku järjestatust). Et SÜT$(a,b)$ jagab nii arvu $a$ kui ka arvu $b$, jagab SÜT$(a,b)$ ka arvu $d$.

Näitame nüüd, et $d$ on ka arvude $a$ ja $b$ jagaja. Jäägiga jagamine annab arvu $a$ esituse kujul $q\cdot d+r$, kus $0\leq r<d$. Asendades $d$ esitusega $s\cdot a+t\cdot b$ ning avaldades võrrandist $r,$ saame $r=(1-q\cdot s)\cdot a+(-q\cdot t)\cdot b$. Et $d$ on minimaalne, siis $r=0$, järelikult $d$ on arvu $a$ jagaja. Samamoodi on $d$ arvu $b$ jagaja, nii et $d\leq$SÜT$(a,b)$. Nägime juba, et SÜT$(a,b)$ on arvu $d$ jagaja. Järelikult $d=$SÜT$(a,b)$.

Bézout' kordajad

Et juhtum, kus vähemalt üks arvudest $a,b$ võrdub nulliga, on triviaalne, siis on selles jaotises edaspidi eeldatud, et kumbki neist arvudest ei võrdu nulliga.

Mitteühesus

Bézout' kordajate leidmine on ekvivalentne kahe tundmatuga esimest järku diofantilise võrrandi

$ax+by=d,$ kus $d=$ SÜT$(a,b),$

lahendamisega.

Selle võrrandi samaväärne kuju on:

${\frac {a}{d}}x+{\frac {b}{d}}y=1.$

Siit järeldub, et Bézout' kordajad $x,y$ on määratud mitteüheselt — kui mingid nende väärtused $x_{0},y_{0}$ on teada, siis kogu kordajate hulga annab valem

$\left\{\left(x_{0}+{\frac {kb}{d}},y_{0}-{\frac {ka}{d}}\right)\mid k=0,\pm 1,\pm 2,\pm 3\dots \right\}.$

Allpool on näidatud, et leiduvad Bézout' kordajad, mis rahuldavad võrratusi $|x|<\left|{\frac {b}{d}}\right|$ ja $|y|<\left|{\frac {a}{d}}\right|$.

Kordajate arvutamine Eukleidese algoritmi abil

Bézout' kordajate leidmiseks saab kasutada Eukleidese laiendatud algoritmi SÜT-i leidmiseks ning esitada jäägid arvude a ja b lineaarkombinatsioonidena. Algoritmi sammudel on järgmine kuju:

$r_{1}=a-bq_{0},$

$r_{2}=b-r_{1}q_{1}=b-(a-bq_{0})q_{1}=b(1+q_{0}q_{1})-aq_{1},$

$r_{3}=r_{1}-r_{2}q_{2}=(a-bq_{0})-(b(1+q_{0}q_{1})-aq_{1})q_{2}=a(1+q_{1}q_{2})-b(q_{0}+q_{2}+q_{0}q_{1}q_{2}),$

…

$r_{n}=r_{n-2}-r_{n-1}q_{n-1}=\dots =ax+by.$

Näide

Leiame Bézout' samasuse $a=991,b=981$ korral. Eukleidese algoritmi valemitel on kuju

$991={\boldsymbol {981}}\cdot 1+10,$

${\boldsymbol {981}}=10\cdot 98+1,$

$10=1\cdot 10.$

Seega SÜT$(991,981)=1.$ Nendest valemitest saame:

$10={\boldsymbol {991}}-1\cdot {\boldsymbol {981}},$

$1={\boldsymbol {981}}-10\cdot 98={\boldsymbol {981}}-98\cdot ({\boldsymbol {991}}-{\boldsymbol {981}})=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.$

Bézout' samasusel on seega kuju

$1=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.$

Kordajate arvutamine ahelmurdude abil

Võrrandi $ax+by=d$ arvutamise alternatiivne (ekvivalentne) viis kasutab ahelmurde. Jagame võrrandi mõlemad pooled SÜT-iga: $a_{1}x+b_{1}y=1$. Edasi arendame murru ${\frac {|a_{1}|}{|b_{1}|}}$ ahelmurruks ja arvutame lähismurrud ${\frac {p_{k}}{q_{k}}}$. Neist viimane ($n$-is) võrdub ${\frac {|a_{1}|}{|b_{1}|}}$ ning on eelmisega seotud tavalise seosega:

$p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}.$

Asetame sellesse valemisse $p_{n}=a_{1};q_{n}=b_{1}$ ja korrutame mõlemad pooled arvuga $d$, saame

$aq_{n-1}-bp_{n-1}=\pm d.$

Märgi täpsusega on see Bézout' samasus, sellepärast annab eelviimane lähismurd ${\frac {p_{n-1}}{q_{n-1}}}$ lahendi absoluutväärtused: $|x|$ on selle murru nimetaja ning $|y|$ on selle lugeja. Jääb üle leida arvude $x,y$ märk, lähtudes algsest võrrandist; selleks piisab, kui leida viimased numbrid korrutistes $|ax|,|by|$.

Minimaalsed kordajate paarid

Eelmises jaotises toodud algoritm ahelmurdude kaudu, nagu ka sellega ekvivalentne Eukleidese algoritm, annab tulemuseks paari $(x,y)$, mis rahuldab võrratusi

$|x|<\left|{\frac {b}{d}}\right|;\quad |y|<\left|{\frac {a}{d}}\right|.$

See järeldub sellest, et nagu ülalpool näidatud, moodustavad murrud ${\frac {|y|}{|x|}}$ ja ${\frac {|a_{1}|}{|b_{1}|}}$ järjestikused lähismurrud ning järgmise murru lugeja ja nimetaja on alati suuremad kui eelmise omad. Lühiduse mõttes võib niisugust paari nimetada minimaalseks, selliseid paare on alati kaks.

Näide. Olgu $a=12,b=42.$ SÜT(12, 42) = 6. Järgnevas ära toodud mõned Bézout' kordajate paaride nimekirja elemendid, kusjuures minimaalsed paarid on välja toodud punasega:

${\begin{alignedat}{3}&\dots \\&12\times &\color {blue}{-10}&{}+42\times &\color {blue}{3}&{}=6\\&12\times &\color {red}{-3}&{}+42\times &\color {red}{1}&{}=6\\&12\times &\color {red}{4}&{}+42\times &\color {red}{-1}&{}=6\\&12\times &\color {blue}{11}&{}+42\times &\color {blue}{-3}&{}=6\\&12\times &\color {blue}{18}&{}+42\times &\color {blue}{-5}&{}=6\\&\dots \end{alignedat}}$

Järeldused

Kui arvud $a,b$ on ühismõõduta, siis võrrandil

$ax+by=1$

on täisarvulisi lahendeid See oluline fakt hõlbustab esimest järku diofantiliste võrrandite lahendamist.

SÜT$(a,b)$ on vähim naturaalarv, mida saab esitada arvude $a$ ja $b$ täisarvuliste kordajatega lineaarkombinatsioonina.

Täisarvuliste kordajatega lineaarkombinatsioonide hulk $\{ax+by\}$ langeb kokku arvu SÜT$(a,b)$ kordsete hulgaga.

Rakendused

Bézout' lemmal on matemaatikas ja eriti arvuteoorias põhjapanev tähtsus. Nii näiteks saab sellest tuletada Eukleidese lemma, millest järeldub algteguriteks lahutuse ühesus. Ka Hiina jäägiklassiteoreem järeldub Bézout' lemmast. Lineaarsete diofantiliste võrrandite korral annab Bézout' lemma nende lahenduvuse kriteeriumi. Bézout' lemmat kasutatakse ka kongruentside lahendamisel.

Üldistused

Üldisemalt kehtib Bézout' lemma igas peaideaaliringis, isegi ühes mittekommutatiivses ringis (Hurwitzi kvaternioonid). Lemma kehtib Eukleidese ringides.

Peaideaaliringid on integriteetkonnad, milles iga ideaal on peaideaal. Seal leidub ringi elementide a ja b korral alati element c nii, et ideaal aR+bR on peaideaal cR. Element c on siis ühelt poolt elementide a ja b ühine jagaja ning teiselt poolt a ja b lineaarkombinatsioon. Peaideaaliringides kehtib Bézout' lemma seetõttu otsekui definitsiooni kohaselt, kui võtta elementi c kui a ja b suurimat ühistegurit.

Ajalugu

Selle tulemuse avaldas esimesena 1624. aastal Claude-Gaspard Bachet de Méziriac ühisteguriteta arvude kohta. Bаchet' formuleering on järgmine: "Antud on kaks ühisteguriteta arvu, leidke kummagi vähim kordne, mis ületab ühe võrra teise kordset". Ülesande lahendamiseks kasutas Bachet Eukleidese algoritmi.

Étienne Bézout oma neljaköitelises "Matemaatikakursuses" (Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine, kd 3, 1766) üldistas teoreemi, laiendades selle suvalistele arvupaaridele ning ka polünoomidele.

Välislingid

• Eric W. Weisstein.Bezout’s Identity, MathWorld