Bezout-suhde

Bezout-suhde on esitys kokonaislukujen suurimmasta yhteisestä jakajasta niiden lineaarisena yhdistelmänä kokonaislukukertoimien kanssa [1] .

Nimetty ranskalaisen matemaatikon Étienne Bézoutin mukaan .

Historia

Ensimmäisen kerran tämän tosiasian julkaisi vuonna 1624 ranskalainen matemaatikko Claude Gaspard Bacher de Meziriac koprime - lukujen tapauksessa [2] . Baschen muotoilu on seuraava: " Kun on annettu kaksi [keskinäisesti] alkulukua, etsi kunkin pienin kerrannainen, joka on toisen kerrannainen " [3] . Ongelman ratkaisemiseksi Basche käytti Euclid-algoritmia .

Étienne Bezout yleisti neliosaisessa Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine , nide 3, 1766 teoreeman laajentamalla sen mielivaltaisiin lukupareihin sekä polynomeihin .

Sanamuoto

Antaa , olla kokonaislukuja , joista ainakin yksi ei ole nolla. Sitten on sellaisia kokonaislukuja, että relaatio $a$ $b$ $x,y$

GCD

(a, b) = x \cdot a + y \cdot b

Tätä väitettä kutsutaan Bezoutin relaatioksi (luvuille ja ), samoin kuin Bezoutin lemmaks tai Bezoutin identiteetiksi [4] . Tässä tapauksessa kokonaislukuja kutsutaan Bezout-kertoimiksi . $a$ $b$ $x,y$

Myös Bezout-relaatiossa on muunnos, joka on rajoitettu luonnollisiin lukuihin [5] :

Olkoon luonnollisia lukuja. Sitten on luonnollisia lukuja , kuten relaatio $a$ $b$ $x,y$

GCD

(a,b)=x\cdot ay\cdot b

Esimerkkejä

GCD Bezout-relaatiolla on muoto: $(12, 30) = 6.$ $6=3 \cdot 12 + (-1) \cdot 30$
- GCD:n hajottamiseen on muitakin vaihtoehtoja, esimerkiksi: $6=(-2) \cdot 12 + 1 \cdot 30.$

Seuraukset

Jos luvut ovat koprime , niin yhtälö $a,b$

ax+by=1

on kokonaislukuratkaisut [6] . Tämä tärkeä seikka helpottaa ensimmäisen asteen diofantiiniyhtälöiden ratkaisemista .

GCD on pienin luonnollinen luku, joka voidaan esittää lukujen lineaarisena yhdistelmänä ja kokonaislukukertoimilla [7] . $(a, b)$ $a$ $b$

Lineaaristen kokonaislukuyhdistelmien joukko osuu yhteen GCD : n kerrannaisten joukon kanssa [8] . $\{ax+by\}$ $(a, b)$

Bezout kertoimet

Koska tapaus, jossa ainakin yksi luvuista on nolla, on triviaali, tämän osan loppuosassa oletetaan, että kumpikaan näistä luvuista ei ole nolla. $a,b$

Epäselvyys

Bézout-kertoimien löytäminen vastaa ensimmäisen asteen diofantiiniyhtälön ratkaisemista kahdella tuntemattomalla:

ax+by=d,

missä gcd

d=

(a, b).

Tai mikä on sama:

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

Tästä seuraa, että Bezout-kertoimet määritellään epäselvästi - jos jotkut niiden arvoista ovat tiedossa, niin koko kerroinjoukko saadaan kaavalla [9] $x,y$ $x_{0},y_{0}$

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

Alla näytetään , että on olemassa Bezout-kertoimia, jotka tyydyttävät epäyhtälöt ja . $|x|<\left|{\frac {b}{d}}\right|$ $|y|<\left|{\frac {a}{d}}\right|$

Kertoimien laskenta Euklid-algoritmilla

Bezout-kertoimien löytämiseksi voit käyttää laajennettua euklidelaista algoritmia GCD:n löytämiseen ja esittää residuaalit a:n ja b :n lineaarisina yhdistelminä [10] . Algoritmin vaiheet on kirjoitettu seuraavassa muodossa:

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_{ yksi},

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.

Esimerkki

Etsitään Euklidisen algoritmin kaavojen Bezout-relaatiolla muoto $a=991,b=981.$

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

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

10=1\cdot 10.

Näin ollen GCD . Näistä kaavoista saamme: $(991 981)=1$

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}}.

Tämän seurauksena Bezout-relaatiolla on muoto

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

Kertoimien laskeminen jatkuvilla murto-osilla

Vaihtoehtoinen (olennaisesti vastaava) tapa yhtälön ratkaisemiseksi käyttää jatkuvia murtolukuja . Jaetaan yhtälön molemmat osat GCD:ksi: . Laajenna seuraavaksi jatkuvaksi murtoluvuksi ja laske konvergentit . Viimeiset niistä ovat yhtä suuret ja liittyvät edelliseen tavanomaisella suhteella: $ax+by=d$ $a_{1}x+b_{1}y=1$ ${\frac {|a_{1}|}{|b_{1}|}}$ ${\frac {p_{k}}{q_{k}}}$ $n$ ${\frac {|a_{1}|}{|b_{1}|}}$

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

Korvaamalla tähän kaavaan ja kertomalla molemmat puolet :lla , saamme ${\displaystyle p_{n}=a_{1};q_{n}=b_{1))$ $d$

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

Merkkiin asti tämä on Bezoutin suhde. siksi toiseksi viimeinen konvergentti antaa ratkaisun moduulit: on tämän murtoluvun nimittäjä ja osoittaja. Alkuperäisen yhtälön perusteella jää vielä löytää merkit ; tätä varten riittää, kun etsit tuotteiden viimeiset numerot [11] . ${\frac {p_{n-1}}{q_{n-1}}}$ $|x|$ $|y|$ $x,y$ $|kirves|,|by|$

Kerrointen vähimmäisparit

Edellisessä osassa annettu algoritmi jatkuvien murtolukujen sekä vastaavan Eukleideen algoritmin tuloksena saadaan pari, joka tyydyttää epäyhtälöt $(x,y)$

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

Tämä tosiasia johtuu siitä tosiasiasta, että murtoluvut ja muodostavat, kuten edellä mainittiin, peräkkäisiä suppenevia ja seuraavan suppenevan osoittaja ja nimittäjä on aina suurempi kuin edellisen [11] [12] . Lyhyyden vuoksi voimme kutsua tällaista paria minimaaliksi , tällaisia pareja on aina kaksi. ${\frac {|y|}{|x|}}$ ${\frac {|a_{1}|}{|b_{1}|}}$

Esimerkki. Anna . gcd(12, 42) = 6. Alla on joitain osia Bezout-kertoimien parien luettelosta, ja vähimmäisparit on korostettu punaisella: $a=12,b=42$

{\begin{alignedat}{3}&\dots \\&12\times &\color {sininen}{-10}&{}+42\times &\color {sininen}{3}&{}= 6\\&12\kertaa &\väri {punainen}{-3}&{}+42\kertaa &\väri {punainen}{1}&{}=6\\&12\kertaa &\väri {punainen}{4 }&{}+42\kertaa &\väri {punainen}{-1}&{}=6\\&12\kertaa &\väri {sininen}{11}&{}+42\kertaa &\väri {sininen} {-3}&{}=6\\&12\kertaa &\väri {sininen}{18}&{}+42\kertaa &\väri {sininen}{-5}&{}=6\\&\pistettä \end{aligneddata}}

Sovellus

Bezout-relaatiota käytetään usein lemmana muiden lauseiden (esim . aritmeettisen peruslauseen [13] ) todistamisessa sekä diofantiiniyhtälöiden ja modulovertailujen ratkaisemisessa.

Ensimmäisen asteen diofantiiniyhtälöiden ratkaisu

Tarkastellaan muodon diofantiiniyhtälöiden ratkaisua kokonaislukuina

ax+by=c.

Merkitse gcd Yhtälöllä on ilmeisesti kokonaislukuratkaisuja vain silloin , kun se on jaollinen luvulla . Katsomme tämän ehdon täyttyneen, ja yksi yllä olevista algoritmeista löytää Bezout-kertoimet : $d={}$ $(a, b).$ $c$ $d$ $x,y$

a+by=d.

Tällöin alkuperäisen yhtälön ratkaisu on pari [11] , jossa . $c_{1}x,c_{1}y$ $c_{1}=c/d$

Ensimmäisen asteen vertailujen ratkaiseminen

ax\equiv b{\pmod m}

se riittää muuttamaan muotoon [8]

ax+my=b.

Käytännössä tärkeä erikoistapaus on käänteiselementin löytäminen jäännösrenkaasta eli vertailun ratkaiseminen

ax\equiv 1{\pmod {m)).

Muunnelmia ja yleistyksiä

Bezoutin relaatio on helppo yleistää tapaukseen, jossa lukuja on enemmän kuin kaksi [1] :

Antaa , …, olla kokonaislukuja, jotka eivät kaikki ole nollaa. Sitten on sellaisia kokonaislukuja , …, , että relaatio täyttyy: $a_{1}$ $a_n$ $x_{1}$ $x_{n}$

GCD , …, =

(a_1

a_n)

x_1\cdot a_1 + \cdots x_n\cdot a_n

Bezoutin relaatio voi päteä kokonaislukujen lisäksi myös muissa kommutatiivisissa renkaissa (esimerkiksi Gaussin kokonaisluvuille ). Tällaisia renkaita kutsutaan Bezout - renkaiksi .

Esimerkki: polynomirenkaan formulointi (yhdestä muuttujasta):

Olkoon jokin polynomiperhe, eivätkä ne kaikki ole yhtä suuria kuin nolla. Merkitään niiden suurin yhteinen jakaja. Sitten on olemassa polynomiperhe , jossa seuraava relaatio pätee: $\left(P_i\oikea)_{i\in I}$ $\Delta$ $\left(A_i\oikea)_{i\in I}$

\Delta = \sum_{i\in I} A_iP_i

Bezout-kertoimet kahdelle polynomille yhdessä muuttujassa voidaan laskea samalla tavalla kuin edellä kokonaisluvuille (käyttämällä laajennettua Euclid-algoritmia ) [14] . Kahden polynomin yhteiset juuret ovat myös niiden suurimman yhteisen jakajan juuret, joten Bezout-relaatiosta ja algebran peruslauseesta seuraa seuraava tulos :

Olkoon polynomit ja annettu kertoimilla jossain kentässä. Sitten polynomit ja sellaiset, jotka ovat olemassa silloin ja vain jos ja joilla ei ole yhteisiä juuria missään algebrallisesti suljetussa kentässä (yleensä kompleksilukujen kenttä otetaan jälkimmäiseksi ). $f(x)$ $g(x)$ $kirves)$ $b(x)$ $af+bg=1$ $f(x)$ $g(x)$

Tämän tuloksen yleistys mihin tahansa määrään polynomeja ja tuntemattomia on Hilbertin nollalause .

Katso myös

Muistiinpanot

↑ 1 2 Hasse G., 1953 , s. 29.
↑ 1600-luvun matematiikka // Matematiikan historia / Toimittanut A.P. Yushkevich , kolmessa osassa. - M . : Nauka, 1970. - T. II. - S. 75.
↑ Claude Gaspard Bachet, Siur de Méziriac. Problemes plaisants et delectables // Problemes plaisans, qui se font par nombres (ranska) . – 2. painos - Lyons, Ranska: Pierre Rigaud & Associates, 1624. - S. 18-33. Arkistoitu 13. maaliskuuta 2012 Wayback Machinessa
↑ Jones, GA; Jones, JM §1.2. Bezoutin identiteetti // Alkulukuteoria. - Berliini: Springer-Verlag, 1998. - P. 7-11.
↑ Davenport G. Korkeampi aritmetiikka. Johdatus lukuteoriaan. - M .: Nauka, 1965. - S. 28. - 176 s.
↑ Hasse G., 1953 , s. 33.
↑ Faddeev D.K. Luennot algebrasta. Oppikirja yliopistoille. - Nauka, 1984. - S. 9. - 416 s.
↑ 1 2 Bezoutin henkilöllisyys . Käyttöpäivä: 25. joulukuuta 2014. Arkistoitu alkuperäisestä 25. joulukuuta 2014. (määrätön)
↑ Gelfond A. O. Yhtälöiden ratkaisu kokonaislukuina. - Nauka, 1983. - S. 9-10. - 63 s. - (Suosittuja matematiikan luentoja, numero 8).
↑ Egorov D. F. Lukuteorian elementit. - Moskova-Petrograd: Gosizdat, 1923. - S. 14. - 202 s.
↑ 1 2 3 Sushkevich A. K. Numeroteoria . Peruskurssi. - Kharkov: Kharkov Universityn kustantamo, 1954. - S. 49-51.
↑ Khinchin A. Ya. Jatketut murtoluvut. - Toim. 3. - M .: GIFML, 1961. - S. 11-12.
↑ Katso esimerkiksi: Zhikov V.V. Aritmeettisen peruslause // Soros Educational Journal . - 2000. - T. 6 , nro 3 . - S. 112-117 . Arkistoitu alkuperäisestä 23. marraskuuta 2018.
↑ Koblitz N. Numeroteorian ja kryptografian kurssi. - M . : Tieteellinen kustantaja TVP, 2001. - S. 19. - 259 s. — ISBN 5-94057-103-4 .

Kirjallisuus

Vinogradov I.M. Numeroteorian perusteet. - M. - L .: GITTL, 1952. - 180 s.
Kaluzhnin L. A. Aritmetiikan päälause. - M . : Nauka, 1969. - ( Suosittuja matematiikan luentoja ).
Hasse G. Luentoja lukuteoriasta. - M .: Toim. ulkomainen kirjallisuus, 1953. - 529 s.

Linkit

Bezout-suhdelaskin verkossa .
Bezoutin identiteetti .
Bezoutin identiteetti, euklidinen algoritmi .