Bezoutový poměr

Bezoutův poměr je reprezentace největšího společného dělitele celých čísel jako jejich lineární kombinace s celočíselnými koeficienty [1] .

Pojmenováno po francouzském matematikovi Étienne Bézoutovi .

Historie

Poprvé tuto skutečnost publikoval v roce 1624 francouzský matematik Claude Gaspard Bacher de Meziriac pro případ prvočísel [2] . Bascheho formulace zní takto: „Zadaná dvě [vzájemně] prvočísla, najděte nejmenší násobek každého, který je jedním násobkem toho druhého “ [3] . K vyřešení problému Basche použil Euclidův algoritmus .

Étienne Bezout ve svém čtyřsvazkovém Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine , svazek 3, 1766, zobecnil větu tím, že ji rozšířil na libovolné dvojice čísel a také na polynomy .

Formulace

Dovolit , být celá čísla , z nichž alespoň jedno není nula. Pak existují celá čísla taková , že vztah $A$ $b$ $x, y$

GCD

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

Toto tvrzení se nazývá Bezoutův vztah (pro čísla a ), stejně jako Bezoutovo lemma nebo Bezoutova identita [4] . V tomto případě se celá čísla nazývají Bezoutovy koeficienty . $A$ $b$ $x, y$

Existuje také modifikace Bezoutova vztahu, omezená na přirozená čísla [5] :

Nechť , jsou přirozená čísla. Pak jsou přirozená čísla taková, že vztah $A$ $b$ $x, y$

GCD

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

Příklady

GCD Bezoutův vztah má tvar: $(12, 30) = 6.$ $6=3 \cdot 12 + (-1) \cdot 30$
- Existují další možnosti pro rozklad GCD, například: $6=(-2) \cdot 12 + 1 \cdot 30.$

Důsledky

Pokud jsou čísla coprime , pak rovnice $a,b$

ax+by=1

má celočíselná řešení [6] . Tato důležitá skutečnost usnadňuje řešení diofantických rovnic prvního řádu .

GCD je nejmenší přirozené číslo, které lze reprezentovat jako lineární kombinaci čísel a s celočíselnými koeficienty [7] . $(a,b)$ $A$ $b$

Množina celočíselných lineárních kombinací se shoduje s množinou násobků pro GCD ) [8] . $\{ax+by\}$ $(a,b)$

Bezoutové koeficienty

Protože případ, kdy se alespoň jedno z čísel rovná nule, je triviální, zbytek této části předpokládá, že obě tato čísla nejsou rovna nule. $a,b$

Nejednoznačnost

Nalezení Bézoutových koeficientů je ekvivalentní řešení diofantické rovnice prvního řádu se dvěma neznámými:

ax+by=d,

kde gcd

d=

(a,b).

Nebo, což je totéž:

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

Z toho vyplývá, že Bezoutovy koeficienty jsou definovány nejednoznačně — pokud jsou známy některé jejich hodnoty , pak je celá množina koeficientů dána vzorcem [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\tečky \vpravo\}.

Níže bude ukázáno , že existují Bezoutovy koeficienty splňující nerovnosti a . $|x|<\left|{\frac {b}{d}}\right|$ $|y|<\left|{\frac {a}{d}}\right|$

Výpočet koeficientů pomocí Euklidova algoritmu

K nalezení Bezoutových koeficientů můžete použít rozšířený euklidovský algoritmus pro nalezení GCD a reprezentovat rezidua jako lineární kombinace a a b [10] . Kroky algoritmu jsou zapsány v následujícím tvaru:

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

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říklad

Pojďme najít Bezoutův vztah pro formule Euklidova algoritmu ve tvaru $a=991,b=981.$

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

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

10=1\cdot 10.

Tedy GCD . Z těchto vzorců dostaneme: $(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}}.

Výsledkem je, že Bezoutova relace má tvar

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

Výpočet koeficientů pomocí pokračovacích zlomků

Alternativní (v podstatě ekvivalentní) způsob řešení rovnice používá spojité zlomky . Rozdělme obě části rovnice na GCD: . Dále expandujte na pokračující zlomek a vypočítejte konvergenty . Poslední ( s) z nich se budou rovnat a budou se vztahovat k předchozímu v obvyklém poměru: $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}.

Dosazením do tohoto vzorce a vynásobením obou stran číslem , dostaneme ${\displaystyle p_{n}=a_{1};q_{n}=b_{1))$ $d$

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

Až na znamení, to je Bezoutův poměr. proto předposlední konvergent dává moduly řešení: je zde jmenovatel tohoto zlomku a je čitatel. Zbývá na základě původní rovnice najít znaménka ; k tomu stačí najít poslední číslice v produktech [11] . ${\frac {p_{n-1}}{q_{n-1}}}$ $|x|$ $|y|$ $x, y$ $|ax|,|by|$

Minimální dvojice koeficientů

Algoritmus uvedený v předchozí části z hlediska spojitých zlomků, stejně jako ekvivalentní Euklidův algoritmus, vede k páru splňujícímu nerovnosti. $(x,y)$

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

Tato skutečnost vyplývá ze skutečnosti, že zlomky a , jak je naznačeno výše, tvoří po sobě jdoucí konvergenty a čitatel a jmenovatel dalšího konvergenta je vždy větší než ten předchozí [11] [12] . Pro stručnost můžeme takový pár nazvat minimální , takové páry jsou vždy dva. ${\frac {|y|}{|x|}}$ ${\frac {|a_{1}|}{|b_{1}|}}$

Příklad. Nechte _ gcd(12, 42) = 6. Níže jsou uvedeny některé prvky seznamu párů Bezoutových koeficientů, přičemž minimální páry jsou zvýrazněny červeně: $a=12,b=42$

{\begin{alignedat}{3}&\tečky \\&12\times &\color {blue}{-10}&{}+42\times &\color {blue}{3}&{}= 6\\&12\times &\color {červená}{-3}&{}+42\times &\color {červená}{1}&{}=6\\&12\times &\color {červená}{4 }&{}+42\times &\color {red}{-1}&{}=6\\&12\times &\color {modrá}{11}&{}+42\times &\color {modrá} {-3}&{}=6\\&12\times &\color {modrá}{18}&{}+42\times &\color {blue}{-5}&{}=6\\&\tečky \end{aligneddata}}

Aplikace

Bezoutův vztah se často používá jako lemma při dokazování jiných teorémů (např. základní věty aritmetiky [13] ), stejně jako při řešení diofantických rovnic a modulových porovnávání.

Řešení diofantických rovnic prvního stupně

Uvažujme řešení v celých číslech diofantických rovnic tvaru

ax+by=c.

Označme gcd Je zřejmé, že rovnice má celočíselná řešení pouze tehdy, je -li dělitelná . Tuto podmínku budeme považovat za splněnou a jeden z výše uvedených algoritmů najde Bezoutovy koeficienty : $d={}$ $(a,b).$ $C$ $d$ $x, y$

a+by=d.

Pak řešením původní rovnice bude dvojice [11] , kde . $c_{1}x,c_{1}y$ $c_{1}=c/d$

Řešení srovnání prvního stupně

K řešení přirovnání I. stupně

ax\equiv b{\pmod m}

stačí převést do tvaru [8]

ax+my=b.

Prakticky důležitým speciálním případem je nalezení reciprokého prvku v kruhu zbytků , tedy řešení srovnání

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

Variace a zobecnění

Bezoutův vztah lze snadno zobecnit na případ, kdy existuje více než dvě čísla [1] :

Nechť , …, jsou celá čísla, která se všechna nerovnají nule. Pak existují taková celá čísla , …, , že vztah je splněn: $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ův vztah může platit nejen pro celá čísla, ale i v jiných komutativních kruzích (například pro Gaussova celá čísla ). Takové prsteny se nazývají Bezoutovy prsteny .

Příklad: formulace pro polynomický kruh (z jedné proměnné):

Nechť je nějaká rodina polynomů a ne všechny se rovnají nule. Označme jejich největšího společného dělitele. Pak existuje rodina polynomů taková, že platí následující vztah: $\left(P_i\right)_{i\in I}$ $\Delta$ $\left(A_i\right)_{i\in I}$

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

Bezoutovy koeficienty pro dva polynomy v jedné proměnné lze vypočítat podobně jako výše pro celá čísla (s použitím rozšířeného Euklidova algoritmu ) [14] . Společné kořeny dvou polynomů jsou zároveň kořeny jejich největšího společného dělitele, takže z Bezoutova vztahu a základní věty algebry vyplývá následující výsledek :

Nechť polynomy a jsou uvedeny s koeficienty v nějakém oboru. Pak polynomy a takové, které existují tehdy a jen tehdy a nemají společné kořeny v jakémkoli algebraicky uzavřeném poli (obvykle se pole komplexních čísel bere jako druhé ). $f(x)$ $g(x)$ $sekera)$ $b(x)$ $af+bg=1$ $f(x)$ $g(x)$

Zobecněním tohoto výsledku na libovolný počet polynomů a neznámých je Hilbertova věta o nule .

Viz také

Poznámky

↑ 1 2 Hasse G., 1953 , str. 29.
↑ Matematika 17. století // Historie matematiky / Editoval A.P. Juškevič , ve třech svazcích. - 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 (francouzsky) . — 2. vyd. - Lyons, Francie: Pierre Rigaud & Associates, 1624. - S. 18-33. Archivováno 13. března 2012 na Wayback Machine
↑ Jones, GA; Jones, JM §1.2. Bezoutova identita // Elementární teorie čísel. - Berlín: Springer-Verlag, 1998. - S. 7-11.
↑ Davenport G. Vyšší aritmetika. Úvod do teorie čísel. - M. : Nauka, 1965. - S. 28. - 176 s.
↑ Hasse G., 1953 , s. 33.
↑ Faddeev D.K. Přednášky o algebře. Učebnice pro vysoké školy. - Nauka, 1984. - S. 9. - 416 s.
↑ 1 2 Bezoutova identita . Datum přístupu: 25. prosince 2014. Archivováno z originálu 25. prosince 2014. (neurčitý)
↑ Gelfond A. O. Řešení rovnic v celých číslech. - Nauka, 1983. - S. 9-10. — 63 str. - (Populární přednášky z matematiky, číslo 8).
↑ Egorov D. F. Prvky teorie čísel. - Moskva-Petrograd: Gosizdat, 1923. - S. 14. - 202 s.
↑ 1 2 3 Sushkevich A. K. Teorie čísel. Základní kurz. - Charkov: Nakladatelství Charkovské univerzity, 1954. - S. 49-51.
↑ Khinchin A. Ya. Pokračovací zlomky. - Ed. 3. - M. : GIFML, 1961. - S. 11-12.
↑ Viz například: Zhikov V. V. Základní teorém aritmetiky // Soros Educational Journal . - 2000. - T. 6 , č. 3 . - S. 112-117 . Archivováno z originálu 23. listopadu 2018.
↑ Koblitz N. Kurz teorie čísel a kryptografie. - M . : Vědecké nakladatelství TVP, 2001. - S. 19. - 259 s. — ISBN 5-94057-103-4 .

Literatura

Vinogradov I.M. Základy teorie čísel. - M. - L. : GITTL, 1952. - 180 s.
Kalužnin L. A. Hlavní věta aritmetiky. - M . : Nauka, 1969. - ( Populární přednášky o matematice ).
Hasse G. Přednášky o teorii čísel. - M .: Ed. zahraniční literatura, 1953. - 529 s.

Odkazy

Bezout ratio kalkulačka online .
Bezoutova identita .
Bezoutova identita, euklidovský algoritmus .