Bézout' lemma

Bézout' lemma on väide, et täisarvude suurima ühisteguri saab esitada nende arvude täisarvuliste kordajatega lineaarkombinatsioonina.Хассе Г. Лекции по теории чисел, М.: Изд. иностранной литературы, 1953, lk 29. 

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 ,  täisarv, millest vähemalt üks ei ole null. Siis leiduvad täisarvud  nii, et kehtib seos
 SÜT

Seda väidet nimetatakse Bézout' lemmaks või Bézout' samasuseksJones, G. A., Jones, J. M. §1.2. Bezout's Identity. – Elementary Number Theory, Berlin: Springer-Verlag 1998, lk 7—11.. Täisarve  nimetatakse Bézout' kordajateks'.

Kui  ja  on ühisteguriteta (see on erijuht, kus  SÜT), siis leiduvad  nii, et

Peale selle kehtib ka pöördväide: kui leiduvad  nii, et , siis SÜT.Tõepoolest, kui  on arvude  ja  ühine jagaja, järelikult  ja , siis , järelikult on  arvu 1 jagaja. ■

Kordajaid  ja  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Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел,  М.: Наука 1965, lk 28.:
Olgu ,  naturaalarvud. Siis leiduvad naturaalarvud  nii, et kehtib seos 
 SÜT

Kui kasutada ringi ideaali mõistet, siis peaideaalid  ja  sisalduvad peaideaalis SÜT  Järelikult sisaldub ka ideaal  ideaalis SÜT Bézout' lemma võib formuleerida ka nii, et täisarvude ringis  (või üldse Eukleidese ringides) kehtib
 , kui  SÜT

Näited
SÜT Kehtib

Suurimat ühistegurit saab liidetavateks lahutada ka teisiti, näiteks: 
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 jagamisel. Seetõttu on seda kerge üle kanda Eukleidese ringidele.

Juhul, kui  võib võtta  ja , järelikult võib üldisust kitsendamata eeldada, et . Kõikide arvude   seas, kus  on kindlasti ka positiivseid arve. Olgu   vähim nende seas (see samm kasutab positiivsete täisarvude hulga 
täielikku järjestatust). Et SÜT jagab nii arvu   kui ka arvu , jagab SÜT ka arvu .

Näitame nüüd, et  on ka arvude  ja  jagaja. Jäägiga jagamine annab arvu  esituse kujul , kus . Asendades   esitusega  ning avaldades võrrandist  saame . Et  on minimaalne, siis , järelikult  on arvu  jagaja. Samamoodi on  arvu  jagaja, nii et SÜT. Nägime juba, et  SÜT on arvu  jagaja. Järelikult SÜT.

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, 2p, …, (q−1)p. Ükski neist arvudest ei ole kongruentne nulliga modulo q ning  (p, 2p, …, (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  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
  kus  SÜT
lahendamisega.

Selle võrrandi samaväärne kuju on:

Siit järeldub, et Bézout' kordajad  on määratud mitteüheselt – kui mingid nende väärtused  on teada, siis kogu kordajate hulga annab valemГельфонд А. О. Решение уравнений в целых числах, Наука 1983, |Популярные лекции по математике, 8, lk 9—10.


Allpool on näidatud,  et leiduvad Bézout' kordajad, mis rahuldavad võrratusi  ja .

 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Егоров Д. Ф. Элементы теории чисел, Москва—Петроград: Госиздат 1923, lk  14.. Algoritmi sammudel on järgmine kuju:

…

 Näide
Leiame Bézout' samasuse  korral. Eukleidese algoritmi valemitel on kuju 



Seega SÜT Nendest valemitest saame:


Bézout' samasusel on seega kuju 


 Kordajate arvutamine ahelmurdude abil 
Võrrandi  arvutamise alternatiivne (ekvivalentne) viis kasutab ahelmurde. Jagame võrrandi mõlemad pooled SÜT-iga: . Edasi arendame murru  ahelmurruks ja arvutame lähismurrud . Neist viimane (-is) võrdub  ning on eelmisega seotud tavalise seosega:

Asetame sellesse valemisse  ja korrutame mõlemad pooled arvuga , saame

Märgi täpsusega on see Bézout' samasus, sellepärast annab eelviimane lähismurd  lahendi absoluutväärtused:  on selle murru nimetaja ning  on selle lugeja. Jääb üle leida arvude  märk, lähtudes algsest võrrandist; selleks piisab, kui leida viimased numbrid korrutistes Сушкевич А. К. Теория чисел.  Элементарный курс, Харьков: Изд-во Харьковского университета 1954, lk 49—51..

Minimaalsed kordajate paarid 
Eelmises jaotises toodud algoritm ahelmurdude kaudu, nagu ka sellega ekvivalentne Eukleidese algoritm, annab tulemuseks paari , mis rahuldab võrratusi

See järeldub sellest, et nagu ülalpool näidatud, moodustavad murrud   ja  järjestikused lähismurrud ning järgmise murru lugeja ja nimetaja on alati suuremad kui eelmise omadХинчин А. Я. Цепные дроби, 3. trükk,  М.: ГИФМЛ 1961, lk 11—12.. Lühiduse mõttes võib niisugust paari nimetada minimaalseks, selliseid paare on alati kaks.

Näide. Olgu  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:


Järeldused
Kui arvud  on ühismõõduta, siis võrrandil

on täisarvulisi lahendeidХассе 1953: 33.  See oluline fakt hõlbustab esimest järku diofantiliste võrrandite lahendamist.

SÜT on vähim naturaalarv, mida  saab esitada arvude  ja   täisarvuliste kordajatega lineaarkombinatsiooninaФаддеев Д. К. Лекции по алгебре. Учебное пособие для вузов, Наука 1984, lk 9..

Täisarvuliste kordajatega lineaarkombinatsioonide hulk  langeb kokku arvu SÜT kordsete hulgagaBezout's identity, brilliant.org..

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

täisarvuliste lahendite leidmist. 
Täistame SÜT On ilmne, et võrrandil on täisarvulisi lahendeid ainult juhul, kui   jagub arvuga . Eeldame, et see tingimus on täidetud, ja leiame ühega ülaltoodud algoritmidest Bézout' kordajad :

Siis on algse võrrandi lahendiks paar , kus .

 Esimese astme kongruentside lahendamine 
Esimese astme kongruentsi 

lahendamiseks piisab selle teisendamisest kujule

Praktilise tähtsusega erijuht on pöördelemendi leidmine jäägiklassiringis, s.o kongruentsi

lahendamine.

Üldistused
Lemmat saab üldistada enamale kui kahele täisarvule: kui  on täisarvud, mis ei võrdu kõik nulliga, siis leiduvad täisarvulised kordajad  nii, et
  SÜT.

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  mingi polünoomide pere, kusjuures need ei võrdu kõik nulliga. Tähistame tähega  nende suurima ühisteguri. Siis leidub polünoomide pere  nii, et kehtib seos:
 .

Kahe ühe muutuja polünoomi Bézout' kordajad saab arvutada analoogselt täisarvude juhtumiga (laiendatud Eukleidese algoritmi abil)
Коблиц Н. Курс теории чисел и криптографии, М.: Научное изд-во ТВП 2001, lk 19, ISBN 5-94057-103-4.. 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  ja  kordajatega mingis korpuses. Siis polünoomid  ja  nii, et , leiduvad siis ja ainult siis, kui polünoomidel  ja   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Математика XVII столетия. – А. П. Юшкевич (toim). История математики, 3 kd, М.: Наука 1970, kd II, lk 75.. Bаchet' formuleering on järgmine: "Antud on kaks ühisteguriteta arvu, leidke kummagi vähim kordne, mis ületab ühe võrra teise kordset"Problèmes plaisants et délectables. – Claude Gaspard Bachet, sieur de Méziriac. Problemes plaisans, qui se font par nombres, 2. trükk, Lyons: Pierre Rigaud & Associates 1624, lk 18—33.. Ülesande lahendamiseks kasutas Bachet Eukleidese algoritmi.Wolfgang K. Seiler. Zahlentheorie, loengukonspekt, Uni Mannheim, 2018 

É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

Kategooria:Arvuteooria