Bezout arány

A Bezout-hányados az egész számok legnagyobb közös osztóját ábrázolja lineáris kombinációjuk egész együtthatókkal [1] .

Nevét Étienne Bézout francia matematikusról kapta .

Történelem

Ezt a tényt először 1624-ben Claude Gaspard Bacher de Meziriac francia matematikus tette közzé a másodpímszámok esetében [2] . Basche megfogalmazása a következő: " Adott két [kölcsönösen] prímszám, keresse meg mindegyik legkisebb többszörösét, amelyik a másik többszöröse " [3] . A probléma megoldására Basche az Euklidész algoritmust használta .

Étienne Bezout négykötetes Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine 3. kötetében, 1766, általánosította a tételt úgy, hogy kiterjesztette tetszőleges számpárokra, valamint polinomokra .

Megfogalmazás

Legyen , egész számok , amelyek közül legalább az egyik nem nulla. Aztán vannak olyan egész számok, amelyek a relációt $a$ $b$ $x,y$

GCD

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

Ezt az állítást nevezik Bezout relációjának (számok és ), valamint Bezout lemmája vagy Bezout azonossága [4] . Ebben az esetben az egész számokat Bezout-együtthatónak nevezzük . $a$ $b$ $x,y$

A Bezout-relációnak is van egy módosítása, amely természetes számokra korlátozódik [5] :

Legyenek természetes számok. Aztán vannak olyan természetes számok , hogy a reláció $a$ $b$ $x,y$

GCD

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

Példák

GCD A Bezout reláció alakja: $(12, 30) = 6.$ $6=3 \cdot 12 + (-1) \cdot 30$
- Vannak más lehetőségek is a GCD lebontására, például: $6=(-2) \cdot 12 + 1 \cdot 30.$

Következmények

Ha a számok másodprímek , akkor az egyenlet $a,b$

ax+by=1

egész számú megoldása van [6] . Ez a fontos tény megkönnyíti az elsőrendű diofantin egyenletek megoldását .

A GCD a legkisebb természetes szám, amely számok lineáris kombinációjaként és egész együtthatókkal ábrázolható [7] . $(a,b)$ $a$ $b$

Az egész lineáris kombinációk halmaza egybeesik a GCD többszöröseinek halmazával [8 ] . $\{ax+by\}$ $(a,b)$

Bezout együtthatók

Mivel az az eset, amikor a számok közül legalább az egyik egyenlő nullával, triviális, a szakasz többi része azt feltételezi, hogy mindkét szám nem egyenlő nullával. $a,b$

Kétértelműség

A Bézout-együtthatók megtalálása egyenértékű egy két ismeretlennel rendelkező elsőrendű diofantin egyenlet megoldásával :

ax+by=d,

ahol a gcd

d=

(a, b).

Vagy ami ugyanaz:

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

Ebből következik, hogy a Bezout-együtthatókat félreérthetően definiálják - ha néhány értékük ismert, akkor az együtthatók teljes halmazát a [9] képlet adja meg. $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\pontok \jobbra\}.

Az alábbiakban látható , hogy vannak olyan Bezout-együtthatók, amelyek kielégítik az és az egyenlőtlenségeket . $|x|<\left|{\frac {b}{d}}\right|$ $|y|<\left|{\frac {a}{d}}\right|$

Együtthatók számítása Euklidész algoritmussal

A Bezout-együtthatók meghatározásához használhatja a kiterjesztett euklideszi algoritmust a GCD megtalálására, és a maradékokat a és b lineáris kombinációiként ábrázolja [10] . Az algoritmus lépései a következő formában vannak felírva:

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

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.

Példa

Nézzük meg, hogy az Euklidész algoritmus képleteinek Bezout-relációjának alakja van $a=991,b=981.$

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

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

10=1\cdot 10.

Így a GCD . Ezekből a képletekből a következőket kapjuk: $(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}}.

Ennek eredményeképpen a Bezout-relációnak megvan a formája

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

Együtthatók számítása folyamatos törtek felhasználásával

Az egyenlet megoldásának egy alternatív (lényegében ekvivalens) módja a folyamatos törteket használja . Osszuk fel az egyenlet mindkét részét GCD-re: . Ezután bontsa ki egy folyamatos törtre, és számítsa ki a konvergenseket . Közülük az utolsó ( k) megegyeznek az előzővel, és a szokásos arány szerint viszonyulnak hozzá: $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}.

Ebbe a képletbe behelyettesítve és mindkét oldalt megszorozva -val , akkor azt kapjuk ${\displaystyle p_{n}=a_{1};q_{n}=b_{1))$ $d$

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

Egy jelig ez Bezout aránya. ezért az utolsó előtti konvergens megadja a megoldás moduljait: van ennek a törtnek a nevezője, és a számlálója. Marad az eredeti egyenlet alapján a jelek megtalálása ; ehhez elég az utolsó számjegyeket megtalálni a szorzatokban [11] . ${\frac {p_{n-1}}{q_{n-1}}}$ $|x|$ $|y|$ $x,y$ $|ax|,|by|$

Minimális együttható párok

Az előző szakaszban a folytonos törtek alapján megadott algoritmus, valamint az ekvivalens Euklidész algoritmus egy olyan párt eredményez, amely kielégíti az egyenlőtlenségeket . $(x,y)$

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

Ez a tény abból adódik, hogy a és a törtek , mint fentebb jeleztük, egymást követő konvergenseket alkotnak, és a következő konvergens számlálója és nevezője mindig nagyobb, mint az előzőé [11] [12] . A rövidség kedvéért egy ilyen párt nevezhetjük minimálisnak , mindig van két ilyen pár. ${\frac {|y|}{|x|}}$ ${\frac {|a_{1}|}{|b_{1}|}}$

Példa. Hadd . gcd(12, 42) = 6. Az alábbiakban a Bezout-együttható párok listájának néhány eleme látható, a minimális párok pirossal kiemelve: $a=12,b=42$

{\begin{alignedat}{3}&\dots \\&12\times &\color {blue}{-10}&{}+42\times &\color {blue}{3}&{}= 6\\&12\szer &\szín {piros}{-3}&{}+42\szer &\szín {piros}{1}&{}=6\\&12\szer &\szín {piros}{4 }&{}+42\szer &\szín {piros}{-1}&{}=6\\&12\szer &\szín {kék}{11}&{}+42\szer &\szín {kék} {-3}&{}=6\\&12\szer &\szín {kék}{18}&{}+42\szer &\szín {kék}{-5}&{}=6\\&\pont \end{aligneddata}}

Alkalmazás

A Bezout-relációt gyakran használják lemmaként más tételek bizonyítása során (például az aritmetika alaptétele [13] ), valamint diofantusi egyenletek és modulo-összehasonlítások megoldása során.

Diofantinuszi egyenletek elsőfokú megoldása

Tekintsük a forma diofantinuszi egyenletek megoldását egész számokban

ax+by=c.

Jelölje gcd Nyilvánvaló, hogy az egyenletnek csak akkor van egész megoldása, ha osztható -vel . Ezt a feltételt teljesítettnek tekintjük, és a fenti algoritmusok egyike megkeresi a Bezout-együtthatókat : $d={}$ $(a, b).$ $c$ $d$ $x,y$

a+by=d.

Ekkor az eredeti egyenlet megoldása a [11] pár lesz , ahol . $c_{1}x,c_{1}y$ $c_{1}=c/d$

Elsőfokú összehasonlítások megoldása

Az elsőfokú összehasonlítások megoldására

ax\equiv b{\pmod m}

elég átalakítani a formára [8]

ax+my=b.

Gyakorlatilag fontos speciális eset a reciprok elem megtalálása a maradékok gyűrűjében , vagyis az összehasonlítás megoldása

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

Változatok és általánosítások

Bezout relációja könnyen általánosítható arra az esetre, ha kettőnél több szám van [1] :

Legyen , … egész számok, amelyek nem egyenlők nullával. Ekkor vannak olyan egész számok , …, , amelyekre a reláció teljesül: $a_{1}$ $a_n$ $x_{1}$ $x_{n}$

GCD , …, =

(a_1

a_n)

x_1\cdot a_1 + \cdots x_n\cdot a_n

Bezout relációja nem csak egész számokra érvényes, hanem más kommutatív gyűrűkre is (például Gauss egész számokra ). Az ilyen gyűrűket Bezout gyűrűknek nevezik .

Példa: polinomiális gyűrű megfogalmazása (egy változóból):

Legyen néhány polinomcsalád, és nem mindegyik egyenlő nullával. Jelöljük a legnagyobb közös osztójukat. Ekkor van egy olyan polinomcsalád , amelyre a következő összefüggés teljesül: $\left(P_i\right)_{i\in I}$ $\Delta$ $\left(A_i\right)_{i\in I}$

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

Egy változóban lévő két polinomra vonatkozó Bezout együtthatók a fentiekhez hasonlóan egész számokra számíthatók (a kiterjesztett Euklidész algoritmus segítségével ) [14] . Két polinom közös gyöke a legnagyobb közös osztó gyöke is, így a Bezout-relációból és az algebra alaptételéből a következő eredmény következik :

Legyen a és polinomok adott együtthatókkal valamilyen mezőben. Ekkor olyan polinomok és hasonlók, amelyek akkor és csak akkor léteznek, és nincs közös gyökük egyetlen algebrailag zárt mezőben sem (általában a komplex számok mezőjét vesszük ez utóbbinak ). $f(x)$ $g(x)$ $fejsze)$ $b(x)$ $af+bg=1$ $f(x)$ $g(x)$

Ennek az eredménynek tetszőleges számú polinomra és ismeretlenre általánosítása a Hilbert-féle nullatétel .

Lásd még

Jegyzetek

↑ 1 2 Hasse G., 1953 , p. 29.
↑ A 17. század matematikája // A matematika története / Szerk.: A. P. Juskevics , három kötetben. - 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 (francia) . — 2. kiadás. - Lyons, Franciaország: Pierre Rigaud & Associates, 1624. - S. 18-33. Archivált : 2012. március 13. a Wayback Machine -nél
↑ Jones, GA; Jones, JM, §1.2. Bezout identitása // Elemi számelmélet. - Berlin: Springer-Verlag, 1998. - P. 7-11.
↑ Davenport G. Magasabb aritmetika. Bevezetés a számelméletbe. - M. : Nauka, 1965. - S. 28. - 176 p.
↑ Hasse G., 1953 , p. 33.
↑ Faddeev D.K. Előadások az algebráról. Tankönyv egyetemek számára. - Nauka, 1984. - S. 9. - 416 p.
↑ 1 2 Bezout személyazonossága . Hozzáférés dátuma: 2014. december 25. Az eredetiből archiválva : 2014. december 25. (határozatlan)
↑ Gelfond A. O. Egyenletek megoldása egész számokban. - Nauka, 1983. - S. 9-10. — 63 p. - (Népszerű matematikai előadások, 8. szám).
↑ Egorov D. F. A számelmélet elemei. - Moszkva-Petrograd: Gosizdat, 1923. - S. 14. - 202 p.
↑ 1 2 3 Sushkevich A. K. Számelmélet. Alapfokú tanfolyam. - Harkov: Harkovi Egyetem Kiadója, 1954. - S. 49-51.
↑ Khinchin A. Ya. Folytatja a törteket. - Szerk. 3. - M. : GIFML, 1961. - S. 11-12.
↑ Lásd például: Zhikov V.V. Az aritmetika alapvető tétele // Soros Educational Journal . - 2000. - T. 6 , 3. sz . - S. 112-117 . Az eredetiből archiválva : 2018. november 23.
↑ Koblitz N. Számelmélet és kriptográfia tanfolyam. - M . : TVP Tudományos Kiadó, 2001. - S. 19. - 259 p. — ISBN 5-94057-103-4 .

Irodalom

Vinogradov I.M. A számelmélet alapjai. - M. - L. : GITTL, 1952. - 180 p.
Kaluzsnin L. A. Az aritmetika fő tétele. - M . : Nauka, 1969. - ( Népszerű matematikai előadások ).
Hasse G. Előadások a számelméletről. - M . : Szerk. külföldi irodalom, 1953. - 529 p.

Linkek

Bezout arány kalkulátor online .
Bezout identitása .
Bezout identitása, euklideszi algoritmus .