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.
Olgu formula_1, formula_2 täisarv, millest vähemalt üks ei ole null. Siis leiduvad täisarvud formula_3 nii, et kehtib seos
 SÜTformula_4
Formuleeringud.
Seda väidet nimetatakse Bézout' lemmaks või Bézout' samasuseks. Täisarve formula_3 nimetatakse Bézout' kordajateks.
Kui formula_1 ja formula_2 on ühisteguriteta (see on erijuht, kus SÜTformula_8), siis leiduvad formula_9 nii, et
 formula_10
Peale selle kehtib ka pöördväide: kui leiduvad formula_11 nii, et formula_12, siis SÜTformula_8.
Kordajaid formula_14 ja formula_15 saab laiendatud Eukleidese algoritmi abil efektiivselt arvutada.
Küsimusega, milliseid arve saab esitada isegi naturaalarvuliste kordajatega, tegeleb mündiprobleem.
On ka Bézout' lemma variant, mis piirdub naturaalarvudega:
Olgu formula_1, formula_2 naturaalarvud. Siis leiduvad naturaalarvud formula_3 nii, et kehtib seos 
 SÜTformula_19
Kui kasutada ringi ideaali mõistet, siis peaideaalid formula_20 ja formula_21 sisalduvad peaideaalis SÜTformula_22 Järelikult sisaldub ka ideaal formula_23 ideaalis SÜTformula_22 Bézout' lemma võib formuleerida ka nii, et täisarvude ringis formula_25 (või üldse Eukleidese ringides) kehtib
 formula_26, kui formula_27 SÜTformula_28
Näited.
(−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 jagamisel. Seetõttu on seda kerge üle kanda Eukleidese ringidele.
Juhul, kui formula_32 võib võtta formula_33 ja formula_34, järelikult võib üldisust kitsendamata eeldada, et formula_35. Kõikide arvude formula_36 seas, kus formula_37 on kindlasti ka positiivseid arve. Olgu formula_38 vähim nende seas (see samm kasutab positiivsete täisarvude hulga 
täielikku järjestatust). Et SÜTformula_39 jagab nii arvu formula_1 kui ka arvu formula_2, jagab SÜTformula_39 ka arvu formula_43.
Näitame nüüd, et formula_43 on ka arvude formula_1 ja formula_2 jagaja. Jäägiga jagamine annab arvu formula_1 esituse kujul formula_48, kus formula_49. Asendades formula_43 esitusega formula_51 ning avaldades võrrandist formula_52 saame formula_53. Et formula_43 on minimaalne, siis formula_55, järelikult formula_43 on arvu formula_1 jagaja. Samamoodi on formula_43 arvu formula_2 jagaja, nii et formula_60SÜTformula_39. Nägime juba, et SÜTformula_39 on arvu formula_43 jagaja. Järelikult formula_64SÜTformula_39.
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 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 formula_66 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
 formula_67 kus formula_68 SÜTformula_69
lahendamisega.
Selle võrrandi samaväärne kuju on:
 formula_70
Siit järeldub, et Bézout' kordajad formula_3 on määratud mitteüheselt – kui mingid nende väärtused formula_72 on teada, siis kogu kordajate hulga annab valem
 formula_73
Allpool on näidatud, et leiduvad Bézout' kordajad, mis rahuldavad võrratusi formula_74 ja formula_75.
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:
formula_76
formula_77
formula_78
formula_79
Leiame Bézout' samasuse formula_80 korral. Eukleidese algoritmi valemitel on kuju 
 formula_81
 formula_82
 formula_83
Seega SÜTformula_84 Nendest valemitest saame:
 formula_85
 formula_86
Bézout' samasusel on seega kuju 
 formula_87
Kordajate arvutamine ahelmurdude abil.
Võrrandi formula_88 arvutamise alternatiivne (ekvivalentne) viis kasutab ahelmurde. Jagame võrrandi mõlemad pooled SÜT-iga: formula_89. Edasi arendame murru formula_90 ahelmurruks ja arvutame lähismurrud formula_91. Neist viimane (formula_92-is) võrdub formula_90 ning on eelmisega seotud tavalise seosega:
 formula_94
Asetame sellesse valemisse formula_95 ja korrutame mõlemad pooled arvuga formula_43, saame
 formula_97
Märgi täpsusega on see Bézout' samasus, sellepärast annab eelviimane lähismurd formula_98 lahendi absoluutväärtused: formula_99 on selle murru nimetaja ning formula_100 on selle lugeja. Jääb üle leida arvude formula_3 märk, lähtudes algsest võrrandist; selleks piisab, kui leida viimased numbrid korrutistes formula_102.
Minimaalsed kordajate paarid.
Eelmises jaotises toodud algoritm ahelmurdude kaudu, nagu ka sellega ekvivalentne Eukleidese algoritm, annab tulemuseks paari formula_103, mis rahuldab võrratusi
 formula_104
See järeldub sellest, et nagu ülalpool näidatud, moodustavad murrud formula_90 ja formula_90 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 formula_107 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:
 formula_108
Järeldused.
Kui arvud formula_109 on ühismõõduta, siis võrrandil
 formula_110
on täisarvulisi lahendeid See oluline fakt hõlbustab esimest järku diofantiliste võrrandite lahendamist.
SÜTformula_111 on vähim naturaalarv, mida saab esitada arvude formula_1 ja formula_2 täisarvuliste kordajatega lineaarkombinatsioonina.
Täisarvuliste kordajatega lineaarkombinatsioonide hulk formula_114 langeb kokku arvu SÜTformula_39 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. 
Esimese astme diofantiliste võrrandite lahendamine.
Vaatleme diofantiliste võrrandite kujul
 formula_116
täisarvuliste lahendite leidmist. 
Täistame formula_117SÜTformula_118 On ilmne, et võrrandil on täisarvulisi lahendeid ainult juhul, kui formula_119 jagub arvuga formula_43. Eeldame, et see tingimus on täidetud, ja leiame ühega ülaltoodud algoritmidest Bézout' kordajad formula_3:
 formula_122
Siis on algse võrrandi lahendiks paar formula_123, kus formula_124.
Esimese astme kongruentside lahendamine.
Esimese astme kongruentsi 
 formula_125
lahendamiseks piisab selle teisendamisest kujule
 formula_126
Praktilise tähtsusega erijuht on pöördelemendi leidmine jäägiklassiringis, s.o kongruentsi
 formula_127
lahendamine.
Üldistused.
Lemmat saab üldistada enamale kui kahele täisarvule: kui formula_128 on täisarvud, mis ei võrdu kõik nulliga, siis leiduvad täisarvulised kordajad formula_129 nii, et
 formula_130 SÜTformula_131.
Integriteetkondi, kus Bézout' lemma kehtib, nimetatakse Bézout' ringideks. Nende seas on Gaussi täisarvude ring. 
Bézout' lemma kehtib 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.
Näide. Formuleering (ühe muutuja) polünoomide ringi korral: 
Olgu formula_132 mingi polünoomide pere, kusjuures need ei võrdu kõik nulliga. Tähistame tähega formula_133 nende suurima ühisteguri. Siis leidub polünoomide pere formula_134 nii, et kehtib seos:
 formula_135.
Kahe ühe muutuja polünoomi Bézout' kordajad saab arvutada analoogselt täisarvude juhtumiga (laiendatud Eukleidese algoritmi abil)
. Kahe polünoomi ühised juured on ka nende suurima ühisteguri juured, sellepärast järeldub Bézout' lemmast ja algebra põhiteoreemist järgmine tulemus:
Olgu antud polünoomid formula_136 ja formula_137 kordajatega mingis korpuses. Siis polünoomid formula_138 ja formula_139 nii, et formula_140, leiduvad siis ja ainult siis, kui polünoomidel formula_136 ja formula_137 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 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.