Bezout forhold

Bezout-forholdet er en repræsentation af den største fælles divisor af heltal som deres lineære kombination med heltalskoefficienter [1] .

Opkaldt efter den franske matematiker Étienne Bézout .

Historie

For første gang blev denne kendsgerning offentliggjort i 1624 af den franske matematiker Claude Gaspard Bacher de Meziriac for tilfældet med coprime tal [2] . Basches formulering er som følger: " Givet to [gensidigt] primtal, find det mindste multiplum af hver, der er det ene multiplum af det andet " [3] . For at løse problemet brugte Basche Euclid-algoritmen .

Étienne Bezout generaliserede i sine fire bind Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine , bind 3, 1766, sætningen ved at udvide den til vilkårlige talpar såvel som til polynomier .

Ordlyd

Lad , være heltal , hvoraf mindst én ikke er nul. Så er der heltal sådan , at relationen $-en$ $b$ $x,y$

GCD

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

Dette udsagn kaldes Bezouts relation (for tal og ), samt Bezouts lemma eller Bezouts identitet [4] . I dette tilfælde kaldes heltal Bezout-koefficienter . $-en$ $b$ $x,y$

Der er også en modifikation af Bezout-relationen, begrænset til naturlige tal [5] :

Lad , være naturlige tal. Så er der naturlige tal sådan, at forholdet $-en$ $b$ $x,y$

GCD

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

Eksempler

GCD Bezout-relationen har formen: $(12, 30) = 6.$ $6=3 \cdot 12 + (-1) \cdot 30$
- Der er andre muligheder for nedbrydning af GCD, for eksempel: $6=(-2) \cdot 12 + 1 \cdot 30.$

Konsekvenser

Hvis tallene er coprime , så ligningen $a,b$

ax+by=1

har heltalsløsninger [6] . Denne vigtige kendsgerning letter løsningen af førsteordens diophantiske ligninger .

GCD er det mindste naturlige tal, der kan repræsenteres som en lineær kombination af tal og med heltalskoefficienter [7] . $(a,b)$ $-en$ $b$

Sættet af heltal lineære kombinationer falder sammen med sættet af multipler for GCD ) [8] . $\{ax+by\}$ $(a,b)$

Bezout-koefficienter

Da tilfældet, hvor mindst et af tallene er lig med nul, er trivielt, antager resten af dette afsnit, at begge disse tal ikke er lig med nul. $a,b$

Tvetydighed

At finde Bézout-koefficienterne svarer til at løse en førsteordens diophantinsk ligning med to ukendte:

økse+ved=d,

hvor gcd

d=

(a,b).

Eller, som er det samme:

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

Det følger heraf, at Bezout-koefficienterne er defineret tvetydigt - hvis nogle af deres værdier er kendte, er hele koefficientsættet givet af formlen [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\}.

Nedenfor vil det blive vist , at der er Bezout-koefficienter, der opfylder ulighederne og . $|x|<\left|{\frac {b}{d}}\right|$ $|y|<\left|{\frac {a}{d}}\right|$

Beregning af koefficienter ved hjælp af Euclid-algoritmen

For at finde Bezout-koefficienterne kan du bruge den udvidede euklidiske algoritme til at finde GCD og repræsentere residualerne som lineære kombinationer af a og b [10] . Algoritmens trin er skrevet i følgende 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_{ en},

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.

Eksempel

Lad os finde Bezout-relationen for Euklid-algoritmens 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 . Fra disse 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 et resultat har Bezout-relationen formen

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

Beregning af koefficienter ved hjælp af fortsatte brøker

En alternativ (i det væsentlige ækvivalent) måde at løse ligningen på bruger fortsatte brøker . Lad os opdele begge dele af ligningen i GCD: . Udvid derefter til en fortsat brøk og beregn konvergenterne . De sidste ( r) af dem vil være lig med og relateret til den foregående med det sædvanlige forhold: $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}.

Substituere i denne formel og gange begge sider med , får vi ${\displaystyle p_{n}=a_{1};q_{n}=b_{1))$ $d$

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

Op til et tegn er dette Bezouts forhold. derfor giver den næstsidste konvergent løsningens moduler: der er nævneren for denne brøk, og er tælleren. Det er tilbage, baseret på den oprindelige ligning, at finde tegnene ; for dette er det nok at finde de sidste cifre i produkterne [11] . ${\frac {p_{n-1}}{q_{n-1}}}$ $|x|$ $|y|$ $x,y$ $|ax|,|af|$

Minimum par af koefficienter

Algoritmen givet i det foregående afsnit i form af fortsatte brøker, såvel som den tilsvarende Euklids algoritme, resulterer i et par, der opfylder ulighederne $(x,y)$

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

Denne kendsgerning følger af det faktum, at brøkerne og , som angivet ovenfor, danner successive konvergenter , og tælleren og nævneren for den næste konvergent altid er større end den for den foregående [11] [12] . For kortheds skyld kan vi kalde et sådant par minimal , der er altid to sådanne par. ${\frac {|y|}{|x|}}$ ${\frac {|a_{1}|}{|b_{1}|}}$

Eksempel. Lad . gcd(12, 42) = 6. Nedenfor er nogle elementer i listen over par af Bezout-koefficienter, med minimumsparene fremhævet med rødt: $a=12,b=42$

{\begin{alignedat}{3}&\dots \\&12\ gange &\farve {blå}{-10}&{}+42\ gange &\farve {blå}{3}&{}= 6\\&12\ gange &\farve {rød}{-3}&{}+42\ gange &\farve {rød}{1}&{}=6\\&12\ gange &\farve {rød}{4 }&{}+42\ gange &\farve {rød}{-1}&{}=6\\&12\ gange &\farve {blå}{11}&{}+42\ gange &\farve {blå} {-3}&{}=6\\&12\gange &\farve {blå}{18}&{}+42\gange &\farve {blå}{-5}&{}=6\\&\prikker \end{aligneddata}}

Ansøgning

Bezout-relationen bruges ofte som et lemma i forbindelse med at bevise andre sætninger (f.eks. aritmetikkens grundsætning [13] ), samt til at løse diofantiske ligninger og modulo-sammenligninger.

Løsning af diofantiske ligninger af første grad

Lad os overveje løsningen i heltal af diofantiske ligninger af formen

ax+by=c.

Betegn gcd Det er klart, at ligningen kun har heltalsløsninger, når den er delelig med . Vi vil betragte denne betingelse for at være opfyldt, og en af ovenstående algoritmer vil finde Bezout-koefficienterne : $d={}$ $(a,b).$ $c$ $d$ $x,y$

a+by=d.

Så vil løsningen af den oprindelige ligning være parret [11] , hvor . $c_{1}x,c_{1}y$ $c_{1}=c/d$

Løsning af sammenligninger af første grad

At løse sammenligninger af første grad

ax\equiv b{\pmod m}

det er nok at transformere det til formen [8]

ax+my=b.

Et praktisk vigtigt specialtilfælde er at finde det gensidige element i ringen af rester , det vil sige at løse sammenligningen

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

Variationer og generaliseringer

Bezouts relation er let generaliseret til tilfældet, når der er mere end to tal [1] :

Lad , …, være heltal, ikke alle lig med nul. Så er der sådanne heltal , ..., , at forholdet er opfyldt: $a_{1}$ $a_n$ $x_{1}$ $x_{n}$

GCD , …, =

(a_1

a_n)

x_1\cdot a_1 + \cdots x_n\cdot a_n

Bezouts relation kan ikke kun gælde for heltal, men også i andre kommutative ringe (for eksempel for Gaussiske heltal ). Sådanne ringe kaldes Bezout-ringe .

Eksempel: formulering for en polynomialring (fra én variabel):

Lad være en familie af polynomier, og ikke alle af dem er lig med nul. Lad os betegne deres største fælles divisor. Så er der en familie af polynomier , sådan at følgende relation gælder: $\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 for to polynomier i én variabel kan beregnes på samme måde som ovenstående for heltal (ved hjælp af den udvidede Euklidiske algoritme ) [14] . De fælles rødder af to polynomier er også rødderne til deres største fælles divisor, så følgende resultat følger af Bezout-relationen og algebraens grundlæggende sætning :

Lad polynomier og gives med koefficienter i et eller andet felt. Derefter polynomier og sådan, der eksisterer, hvis og kun hvis og ikke har fælles rødder i noget algebraisk lukket felt (normalt tages feltet med komplekse tal som sidstnævnte ). $f(x)$ $g(x)$ $økse)$ $b(x)$ $af+bg=1$ $f(x)$ $g(x)$

En generalisering af dette resultat til et hvilket som helst antal polynomier og ukendte er Hilberts nulsætning .

Se også

Noter

↑ 1 2 Hasse G., 1953 , s. 29.
↑ Matematik i det 17. århundrede // Matematikkens historie / Redigeret af A.P. Yushkevich , i tre bind. - 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 (fransk) . — 2. udg. - Lyons, Frankrig: Pierre Rigaud & Associates, 1624. - S. 18-33. Arkiveret 13. marts 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øjere aritmetik. Introduktion til talteori. - M. : Nauka, 1965. - S. 28. - 176 s.
↑ Hasse G., 1953 , s. 33.
↑ Faddeev D.K. Forelæsninger om algebra. Lærebog for universiteter. - Nauka, 1984. - S. 9. - 416 s.
↑ 1 2 Bezouts identitet . Dato for adgang: 25. december 2014. Arkiveret fra originalen 25. december 2014. (ubestemt)
↑ Gelfond A. O. Løsning af ligninger i heltal. - Nauka, 1983. - S. 9-10. — 63 s. - (Populære forelæsninger om matematik, hæfte 8).
↑ Egorov D. F. Elementer i talteori. - Moskva-Petrograd: Gosizdat, 1923. - S. 14. - 202 s.
↑ 1 2 3 Sushkevich A. K. Talteori. Elementært kursus. - Kharkov: Publishing House of Kharkov University, 1954. - S. 49-51.
↑ Khinchin A. Ya. Fortsatte brøker. - Ed. 3. - M. : GIFML, 1961. - S. 11-12.
↑ Se for eksempel: Zhikov V.V. Aritmetikkens grundlæggende sætning // Soros Educational Journal . - 2000. - T. 6 , nr. 3 . - S. 112-117 . Arkiveret fra originalen den 23. november 2018.
↑ Koblitz N. Kursus i talteori og kryptografi. - M . : Videnskabeligt forlag TVP, 2001. - S. 19. - 259 s. — ISBN 5-94057-103-4 .

Litteratur

Vinogradov I.M. Fundamentals af talteori. - M. - L. : GITTL, 1952. - 180 s.
Kaluzhnin L. A. Hovedsætningen for aritmetik. - M . : Nauka, 1969. - ( Populære forelæsninger om matematik ).
Hasse G. Forelæsninger om talteori. - M. : Red. udenlandsk litteratur, 1953. - 529 s.