Bezout-förhållande

Bezout-förhållandet är en representation av den största gemensamma delaren av heltal som deras linjära kombination med heltalskoefficienter [1] .

Uppkallad efter den franske matematikern Étienne Bézout .

Historik

För första gången publicerades detta faktum 1624 av den franske matematikern Claude Gaspard Bacher de Meziriac för fallet med coprimtal [2] . Basches formulering är följande: " Givet två [ömsesidigt] primtal, hitta den minsta multipeln av varje som är en multipel av den andra " [3] . För att lösa problemet använde Basche Euclid-algoritmen .

Étienne Bezout generaliserade i sina fyra volymer Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine , volym 3, 1766, satsen genom att utvidga den till godtyckliga talpar, såväl som till polynom .

Formulering

Låt , vara heltal , varav minst ett inte är noll. Sedan finns det heltal så att relationen $a$ $b$ $x,y$

GCD

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

Detta påstående kallas Bezouts relation (för siffror och ), såväl som Bezouts lemma eller Bezouts identitet [4] . I det här fallet kallas heltal Bezout-koefficienter . $a$ $b$ $x,y$

Det finns också en modifiering av Bezout-relationen, begränsad till naturliga tal [5] :

Låt , vara naturliga tal. Sedan finns det naturliga tal så att relationen $a$ $b$ $x,y$

GCD

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

Exempel

GCD Bezout-relationen har formen: $(12, 30) = 6.$ $6=3 \cdot 12 + (-1) \cdot 30$
- Det finns andra alternativ för nedbrytning av GCD, till exempel: $6=(-2) \cdot 12 + 1 \cdot 30.$

Konsekvenser

Om talen är coprime , då ekvationen $a,b$

axe+by=1

har heltalslösningar [6] . Detta viktiga faktum underlättar lösningen av första ordningens diofantiska ekvationer .

GCD är det minsta naturliga talet som kan representeras som en linjär kombination av tal och med heltalskoefficienter [7] . $(a,b)$ $a$ $b$

Uppsättningen av linjära heltalskombinationer sammanfaller med uppsättningen av multipler för GCD ) [8] . $\{ax+by\}$ $(a,b)$

Bezout-koefficienter

Eftersom fallet när minst ett av talen är lika med noll är trivialt, antar resten av detta avsnitt att båda dessa tal inte är lika med noll. $a,b$

Tvetydighet

Att hitta Bézout-koefficienterna motsvarar att lösa en första ordningens diofantisk ekvation med två okända:

axe+by=d,

där gcd

d=

(a,b).

Eller, vilket är detsamma:

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

Det följer att Bezout-koefficienterna definieras tvetydigt - om några av deras värden är kända, så ges hela uppsättningen av koefficienter av formeln [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\}.

Nedan kommer det att visas att det finns Bezout-koefficienter som uppfyller ojämlikheterna och . $|x|<\left|{\frac {b}{d}}\right|$ $|y|<\left|{\frac {a}{d}}\right|$

Beräkning av koefficienter med hjälp av euklidalgoritmen

För att hitta Bezout-koefficienterna kan du använda den utökade euklidiska algoritmen för att hitta GCD och representera residualerna som linjära kombinationer av a och b [10] . Stegen i algoritmen skrivs i följande form:

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

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.

Exempel

Låt oss hitta Bezout-relationen för Euklidalgoritmens formler har formen $a=991,b=981.$

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

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

10=1\cdot 10.

Således, GCD . Från dessa formler får vi: $(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}}.

Som ett resultat har Bezout-relationen formen

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

Beräkning av koefficienter med hjälp av fortsatta bråk

Ett alternativt (i huvudsak likvärdigt) sätt att lösa ekvationen använder sig av fortsatta bråk . Låt oss dela upp båda delarna av ekvationen i GCD: . Expandera sedan till en fortsatt bråkdel och beräkna konvergenterna . De sista av dem kommer att vara lika med och relaterade till den föregående med det vanliga förhållandet: $axe+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}.

Genom att ersätta den här formeln och multiplicera båda sidor med , får vi ${\displaystyle p_{n}=a_{1};q_{n}=b_{1))$ $d$

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

Upp till ett tecken, detta är Bezouts förhållande. därför ger den näst sista konvergenten lösningens moduler: det finns nämnaren för detta bråk, och är täljaren. Det återstår, baserat på den ursprungliga ekvationen, att hitta tecknen ; för detta räcker det med att hitta de sista siffrorna i produkterna [11] . ${\frac {p_{n-1}}{q_{n-1}}}$ $|x|$ $|y|$ $x,y$ $|ax|,|av|$

Minsta koefficientpar

Algoritmen som gavs i föregående avsnitt i termer av fortsatta bråk, såväl som motsvarande Euklids algoritm, resulterar i ett par som uppfyller olikheterna $(x,y)$

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

Detta faktum följer av det faktum att bråken och , som anges ovan, bildar successiva konvergenter , och täljaren och nämnaren för nästa konvergent alltid är större än den för den föregående [11] [12] . För korthetens skull kan vi kalla ett sådant par minimalt , det finns alltid två sådana par. ${\frac {|y|}{|x|}}$ ${\frac {|a_{1}|}{|b_{1}|}}$

Exempel. Låt . gcd(12, 42) = 6. Nedan är några delar av listan över par av Bezout-koefficienter, med minimiparen markerade i rött: $a=12,b=42$

{\begin{alignedat}{3}&\dots \\&12\times &\color {blue}{-10}&{}+42\times &\color {blue}{3}&{}= 6\\&12\ gånger &\färg {röd}{-3}&{}+42\ gånger &\färg {röd}{1}&{}=6\\&12\ gånger &\färg {röd}{4 }&{}+42\ gånger &\färg {röd}{-1}&{}=6\\&12\ gånger &\färg {blå}{11}&{}+42\ gånger &\färg {blå} {-3}&{}=6\\&12\ gånger &\färg {blå}{18}&{}+42\ gånger &\färg {blå}{-5}&{}=6\\&\prickar \end{aligneddata}}

Applikation

Bezout-relationen används ofta som ett lemma för att bevisa andra satser (till exempel aritmetikens grundsats [13] ), såväl som för att lösa diofantiska ekvationer och modulo-jämförelser.

Lösning av diofantiska ekvationer av första graden

Låt oss betrakta lösningen i heltal av diofantiska ekvationer av formen

axe+by=c.

Beteckna gcd Uppenbarligen har ekvationen heltalslösningar endast när den är delbar med . Vi kommer att betrakta detta villkor som uppfyllt, och en av ovanstående algoritmer kommer att hitta Bezout-koefficienterna : $d={}$ $(a,b).$ $c$ $d$ $x,y$

a+by=d.

Då blir lösningen av den ursprungliga ekvationen paret [11] , där . $c_{1}x,c_{1}y$ $c_{1}=c/d$

Lösa jämförelser av första graden

För att lösa jämförelser av första graden

ax\equiv b{\pmod m}

det räcker att omvandla det till formen [8]

ax+my=b.

Ett praktiskt viktigt specialfall är att hitta det reciproka elementet i ringen av rester , det vill säga att lösa jämförelsen

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

Variationer och generaliseringar

Bezouts relation är lätt att generalisera till fallet när det finns fler än två tal [1] :

Låt , …, vara heltal som inte alla är lika med noll. Sedan finns det sådana heltal , ..., , att relationen är uppfylld: $a_{1}$ $en$ $x_{1}$ $x_{n}$

GCD , …, =

(a_1

en)

x_1\cdot a_1 + \cdots x_n\cdot a_n

Bezouts relation kan gälla inte bara för heltal, utan även i andra kommutativa ringar (till exempel för Gaussiska heltal ). Sådana ringar kallas Bezout-ringar .

Exempel: formulering för en polynomring (från en variabel):

Låta vara någon familj av polynom, och inte alla av dem är lika med noll. Låt oss beteckna deras största gemensamma delare. Sedan finns det en familj av polynom så att följande relation gäller: $\left(P_i\right)_{i\in I}$ $\Delta$ $\left(A_i\right)_{i\in I}$

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

Bezout-koefficienter för två polynom i en variabel kan beräknas på liknande sätt som ovan för heltal (med den utökade Euklidiska algoritmen ) [14] . De gemensamma rötterna för två polynom är också rötterna till deras största gemensamma divisor, så följande resultat följer av Bezout-relationen och algebras grundläggande sats :

Låt polynom och ges med koefficienter i något fält. Sedan polynom och sådant som finns om och bara om och inte har gemensamma rötter i något algebraiskt slutet fält (vanligtvis tas fältet av komplexa tal som det senare ). $f(x)$ $g(x)$ $yxa)$ $b(x)$ $af+bg=1$ $f(x)$ $g(x)$

En generalisering av detta resultat till valfritt antal polynom och okända är Hilberts nollsats .

Se även

Anteckningar

↑ 1 2 Hasse G., 1953 , sid. 29.
↑ 1600-talets matematik // Matematikens historia / Redigerad av A.P. Yushkevich , i tre volymer. - M . : Nauka, 1970. - T. II. - S. 75.
↑ Claude Gaspard Bachet, sieur de Méziriac. Problemes plaisants et delectables // Problemes plaisans, qui se font par nombres (franska) . — 2:a uppl. - Lyons, Frankrike: Pierre Rigaud & Associates, 1624. - S. 18-33. Arkiverad 13 mars 2012 på Wayback Machine
↑ Jones, GA; Jones, JM §1.2. Bezouts identitet // Elementär talteori. - Berlin: Springer-Verlag, 1998. - S. 7-11.
↑ Davenport G. Högre aritmetik. Introduktion till talteori. - M. : Nauka, 1965. - S. 28. - 176 sid.
↑ Hasse G., 1953 , sid. 33.
↑ Faddeev D.K. föreläsningar om algebra. Lärobok för universitet. - Nauka, 1984. - S. 9. - 416 sid.
↑ 1 2 Bezouts identitet . Datum för åtkomst: 25 december 2014. Arkiverad från originalet 25 december 2014. (obestämd)
↑ Gelfond A. O. Lösning av ekvationer i heltal. - Nauka, 1983. - S. 9-10. — 63 sid. - (Populära föreläsningar om matematik, nummer 8).
↑ Egorov D. F. Element i talteorin. - Moskva-Petrograd: Gosizdat, 1923. - S. 14. - 202 sid.
↑ 1 2 3 Sushkevich A. K. Talteori . Grundkurs. - Kharkov: Publishing House of Kharkov University, 1954. - S. 49-51.
↑ Khinchin A. Ya. Fortsatt bråk. - Ed. 3:a. - M. : GIFML, 1961. - S. 11-12.
↑ Se till exempel: Zhikov V.V. The fundamental theorem of aritmetic // Soros Educational Journal . - 2000. - T. 6 , nr 3 . - S. 112-117 . Arkiverad från originalet den 23 november 2018.
↑ Koblitz N. Kurs i talteori och kryptografi. - M . : Vetenskapligt förlag TVP, 2001. - S. 19. - 259 sid. — ISBN 5-94057-103-4 .

Litteratur

Vinogradov I.M. Fundamentals of Number Theory. - M. - L. : GITTL, 1952. - 180 sid.
Kaluzhnin L. A. Huvudsatsen för aritmetiken. - M . : Nauka, 1969. - ( Populära föreläsningar om matematik ).
Hasse G. Föreläsningar om talteori. - M. : Ed. utländsk litteratur, 1953. - 529 sid.

Bezout-förhållande

Historik

Formulering

Exempel

Konsekvenser

Bezout-koefficienter

Tvetydighet

Beräkning av koefficienter med hjälp av euklidalgoritmen

Beräkning av koefficienter med hjälp av fortsatta bråk

Minsta koefficientpar

Applikation

Lösning av diofantiska ekvationer av första graden

Lösa jämförelser av första graden

Variationer och generaliseringar

Se även

Anteckningar

Litteratur

Länkar