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.

Täisarvude *a* ja *b* suurim ühistegur *d* on ka vähim positiivne täisarv, mida saab esitada kujul *ax* + *by*, kus *x* ja *y* on täisarvud.

## 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 <math>a</math> ja <math>b</math> on [[ühisteguriteta arvud|ühisteguriteta]] (see on erijuht, kus  SÜT<math>(a,b) = 1</math>), siis leiduvad <math>s,t\in\mathbb{Z}</math> nii, et
: <math>1 = s \cdot a + t \cdot b.</math>
Peale selle kehtib ka pöördväide: kui leiduvad <math>s,t\in \Z </math> nii, et <math> s a + t b = 1</math>, siis SÜT<math>(a,b) = 1</math>.

Kordajaid <math>s</math> ja <math>t</math> saab [[laiendatud Eukleidese algoritm]]i abil efektiivselt arvutada.

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

On ka Bézout' lemma variant, mis piirdub [[naturaalarv]]udega:
:Olgu <math>a</math>, <math>b</math> naturaalarvud. Siis leiduvad naturaalarvud <math>x, y</math> nii, et kehtib seos 
: SÜT<math>(a, b) = x \cdot a - y \cdot b.</math>

Kui kasutada [[ringi ideaal]]i mõistet, siis [[peaideaal]]id <math>a R</math> ja <math>b R</math> sisalduvad peaideaalis SÜT<math>(a,b)\;R.</math>  Järelikult sisaldub ka ideaal <math>a R + b R</math> ideaalis SÜT<math>(a,b)\;R.</math> Bézout' lemma võib formuleerida ka nii, et [[täisarvude ring]]is <math>R=\Z</math> (või üldse [[Eukleidese ring]]ides) kehtib
: <math>a R + b R = c R</math>, kui <math>c =</math> SÜT<math>(a,b).</math>

==Näited==
*SÜT<math>(12, 30) = 6.</math> Kehtib
*: <math>6=3 \cdot 12 + (-1) \cdot 30</math>
**Suurimat ühistegurit saab liidetavateks lahutada ka teisiti, näiteks: <math>6=(-2) \cdot 12 + 1 \cdot 30.</math>
*Arvude 12 ja 42 suurim ühistegur on  6, ja selle saab esitada kujul 
(−3)⋅12 + 1⋅42 = 6
ning ka 1 kujul
4⋅12 + (−1)⋅42 = 6.

==Tõestus==
===Tõestus jäägiga jagamise kaudu=== 
Lemma tõestus põhineb [[jäägiga jagamine|jäägiga jagamisel]]. Seetõttu on seda kerge üle kanda [[Eukleidese ring]]idele.

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

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

===Tõestus kongruentside kaudu===
Olgu *d* arvude *a* a *b* suurim ühistegur, *p* = *a* / *d* ja *q* = *b* / *d*, siis *p* ja *q* on [[ühisteguriteta arvud]]. Vaatleme nüüd arve *p*, 2*p*, …, (*q*−1)*p*. Ükski neist arvudest ei ole [[kongruents (arvuteooria)|kongruentne]] nulliga modulo *q* ning  (*p*, 2*p*, …, (*q*−1)*p*) modulo *q* on arvude (1, 2, …, *q* − 1) [[permutatsioon]]. Sellepärast peab leiduma arv *α*, 1 ≤ *α* ≤ *q* − 1 nii, et *αp* (mod *q*) ≡ 1 (mod *q*). Järelikult leidub ka arv *β* nii, et *αp* + *βq* = 1. Po Korrutades võrduse mõlemad pooled arvuga *d*, saame Bézout' samasuse *αa*+ *βb* = *d*.

== Bézout' kordajad ==
Et juhtum, kus vähemalt üks arvudest <math>a,b</math> 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 [[diofantiline võrrand|diofantilise võrrandi]]
: <math>a x  + b y = d, </math> kus <math>d=</math> SÜT<math>(a, b),</math>
lahendamisega.

Selle võrrandi samaväärne kuju on:
: <math>\frac{a}{d} x  + \frac{b}{d} y = 1.</math>
Siit järeldub, et Bézout' kordajad <math>x, y</math> on määratud mitteüheselt – kui mingid nende väärtused <math>x_0, y_0</math> on teada, siis kogu kordajate hulga annab valem
: <math> \left\{ \left(x_0 + \frac{kb}{d}, y_0 - \frac{ka}{d}\right) \mid k = 0, \pm 1, \pm 2, \pm 3 \dots \right\}.</math>

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

=== Kordajate arvutamine Eukleidese algoritmi abil===

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

:<math>r_1 = a - bq_0,</math>
:<math>r_2 = b - r_1q_1 = b - (a - bq_0)q_1 = b(1 + q_0q_1) - aq_1,</math>
:<math>r_3 = r_1 - r_2q_2 = (a - bq_0) - (b(1 + q_0q_1) - aq_1)q_2 = a(1 + q_1q_2) - b(q_0 + q_2 + q_0q_1q_2),</math>
:…
:<math>r_n = r_{n-2} - r_{n-1}q_{n-1} = \dots = ax + by.</math>

; Näide
Leiame Bézout' samasuse <math>a = 991, b = 981</math> korral. Eukleidese algoritmi valemitel on kuju 
: <math>991 = \boldsymbol{981} \cdot 1 + 10,</math>
: <math>\boldsymbol{981} = 10 \cdot 98 + 1,</math>
: <math>10 = 1 \cdot 10.</math>
Seega SÜT<math>(991, 981) = 1.</math> Nendest valemitest saame:
: <math>10 = \boldsymbol{991} - 1 \cdot \boldsymbol{981},</math>
: <math>1 = \boldsymbol{981} - 10 \cdot 98 = \boldsymbol{981} - 98 \cdot (\boldsymbol{991} - \boldsymbol{981}) = 99 \cdot \boldsymbol{981} - 98 \cdot \boldsymbol{991}.</math>
Bézout' samasusel on seega kuju 
: <math>1 = 99 \cdot \boldsymbol{981} - 98 \cdot \boldsymbol{991}.</math>

=== Kordajate arvutamine ahelmurdude abil ===
Võrrandi <math>a x + b y = d </math> arvutamise alternatiivne (ekvivalentne) viis kasutab [[ahelmurd]]e. Jagame võrrandi mõlemad pooled SÜT-iga: <math>a_1 x  + b_1 y = 1</math>. Edasi arendame murru <math>\frac</math> ahelmurruks ja arvutame [[lähismurrud]] <math>\frac{p_k}{q_k}</math>. Neist viimane (<math>n</math>-is) võrdub <math>\frac</math> ning on eelmisega seotud tavalise seosega:
: <math>p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}.</math>
Asetame sellesse valemisse <math>p_n = a_1; q_n = b_1</math> ja korrutame mõlemad pooled arvuga <math>d</math>, saame
: <math>a q_{n-1} - b p_{n-1} = \pm d.</math>
[[Märk (matemaatika)|Märgi]] täpsusega on see Bézout' samasus, sellepärast annab eelviimane lähismurd <math>\frac{p_{n-1}}{q_{n-1}}</math> lahendi [[absoluutväärtus]]ed: <math>|x|</math> on selle murru [[nimetaja]] ning <math>|y|</math> on selle [[lugeja]]. Jääb üle leida arvude <math>x, y</math> märk, lähtudes algsest võrrandist; selleks piisab, kui leida viimased numbrid korrutistes <math>|ax|, |by|</math>.

===Minimaalsed kordajate paarid=== 
Eelmises jaotises toodud algoritm ahelmurdude kaudu, nagu ka sellega ekvivalentne Eukleidese algoritm, annab tulemuseks paari <math>(x,y)</math>, mis rahuldab võrratusi
: <math>|x| < \left|\frac{b}{d}\right|; \quad |y| < \left|\frac{a}{d}\right|.</math>
See järeldub sellest, et nagu ülalpool näidatud, moodustavad murrud  <math>\frac</math> ja <math>\frac</math> 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 <math>a = 12, b = 42.</math> 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:
: <math>
\begin{alignat}{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{alignat}
</math>

==Järeldused==
Kui arvud <math>a, b</math> on [[ühismõõduta arvud|ühismõõduta]], siis võrrandil
: <math>ax + by = 1</math>
on täisarvulisi lahendeid  See oluline fakt hõlbustab esimest järku [[diofantiline võrrand|diofantiliste võrrandite]] lahendamist.

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

Täisarvuliste kordajatega lineaarkombinatsioonide hulk <math>\{ax + by\}</math> langeb kokku arvu SÜT<math>(a,b)</math> [[kordne|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 lahutus]]e ühesus. Ka [[Hiina jäägiklassiteoreem]] järeldub Bézout' lemmast.
[[Linearne diofantiline võrrand|Lineaarsete diofantiliste võrrandite]] korral annab Bézout' lemma nende lahenduvuse kriteeriumi. Bézout' lemmat kasutatakse ka [[kongruents (arvuteooria)|kongruents]]ide lahendamisel. 

=== Esimese astme diofantiliste võrrandite lahendamine===
Vaatleme [[diofantiline võrrand|diofantiliste võrrandite]] kujul
: <math>ax + by = c</math>
täisarvuliste lahendite leidmist. 
Täistame <math>d = {}</math>SÜT<math>(a, b).</math> On ilmne, et võrrandil on täisarvulisi lahendeid ainult juhul, kui  <math>c</math> jagub arvuga <math>d</math>. Eeldame, et see tingimus on täidetud, ja leiame ühega ülaltoodud algoritmidest Bézout' kordajad <math>x, y</math>:
: <math>ax + by = d.</math>
Siis on algse võrrandi lahendiks paar <math>c_1 x, c_1 y</math>, kus <math>c_1 = c / d</math>.

=== Esimese astme kongruentside lahendamine ===
Esimese astme [[kongruents (arvuteooria)|kongruents]]i 
: <math>ax \equiv b \pmod m</math>
lahendamiseks piisab selle teisendamisest kujule
: <math>ax + my = b.</math>
Praktilise tähtsusega erijuht on [[pöördelement|pöördelemendi]] leidmine [[jäägiklassiring]]is, s.o kongruentsi
: <math>ax \equiv 1 \pmod m</math>
lahendamine.

==Üldistused==
Lemmat saab üldistada enamale kui kahele täisarvule: kui <math>a_1, \dotsc, a_n</math> on täisarvud, mis ei võrdu kõik nulliga, siis leiduvad täisarvulised kordajad <math>s_1, \dotsc, s_n</math> nii, et
: <math>s_1 a_1 + \dotsb + s_n a_n = </math> SÜT<math>(a_1,\dotsc,a_n)</math>.

[[Integriteetkond]]i, kus Bézout' lemma kehtib, nimetatakse [[Bézout' ring]]ideks. Nende seas on [[Gaussi täisarvud]]e ring. 

Bézout' lemma kehtib igas [[peaideaaliring]]is, isegi ühes mittekommutatiivses ringis ([[Hurwitzi kvaternioonid]]). Lemma kehtib [[Eukleidese ring]]ides.

Peaideaaliringid on [[integriteetkond|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.

Näide.  Formuleering (ühe muutuja) [[polünoomide ring]]i korral:  
:Olgu <math>\left(P_i\right)_{i\in I}</math> mingi polünoomide pere, kusjuures need ei võrdu kõik nulliga. Tähistame tähega <math>\Delta</math> nende suurima ühisteguri. Siis leidub polünoomide pere <math>\left(A_i\right)_{i\in I}</math> nii, et kehtib seos:
: <math>\Delta = \sum_{i\in I} A_iP_i</math>.

Kahe ühe muutuja polünoomi Bézout' kordajad saab arvutada analoogselt täisarvude juhtumiga ([[laiendatud Eukleidese algoritm]]i abil)
. Kahe polünoomi ühised juured on ka nende suurima ühisteguri juured, sellepärast järeldub Bézout' lemmast ja [[algebra põhiteoreem]]ist järgmine tulemus:
:Olgu antud polünoomid <math>f(x)</math> ja <math>g(x)</math> kordajatega mingis korpuses. Siis polünoomid <math>a(x)</math> ja <math>b(x)</math> nii, et <math>af + bg = 1</math>, leiduvad siis ja ainult siis, kui polünoomidel <math>f(x)</math> ja  <math>g(x)</math> ei ole ühiseid juuri mitte üheski algebraliselt kinnises korpuses (viimaseks võetakse tavaliselt [[kompleksarvude korpus]]).  

Selle tulemuse üldistus kui tahes paljudele pölünoomidele ja tundmatutele on [[Hilberti teoreem nullkohtadest]].

==Ajalugu==
Selle tulemuse avaldas esimesena 1624. aastal [[Claude-Gaspard Bachet de Méziriac]] [[ühisteguriteta arvud]]e 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 algoritm]]i. 

[[É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.

## Viited

## Välislingid
*Eric W. Weisstein.  Bezout’s Identity, MathWorld
*Bézout' kordajate kalkulaator
* Bezout’s Identity
* Bezout’s identity, Euclidean algorithm