Bézoutova rovnost

Z Multimediaexpo.cz

Bézoutova rovnost je lineární diofantická rovnice v teorii čísel. Říká, že největší společný dělitel dvou přirozených čísel a a b lze zapsat jako lineární kombinaci těchto dvou čísel, jejíž koeficienty jsou celá čísla – nazývají se Bézoutovy koeficienty nebo Bézoutova čísla:

$\mathrm{NSD}(a,b)=\alpha a+\beta b;a,b\in \mathbb{N};\alpha ,\beta \in \mathbb{Z}$

Obsah [skrýt] 1 Algoritmus 2 Příklad 3 Zobecnění 4 Důkaz 5 Externí odkazy

Algoritmus

Bézoutovy koeficienty lze určit rozšířeným Eukleidovým algoritmem. Tato čísla nejsou určena jednoznačně. Pokud jsou řešením koeficienty (α, β), pak existuje nekonečně mnoho dalších koeficientů:

$\{(\alpha +\frac{kb}{\mathrm{NSD}(a,b)},\beta -\frac{ka}{\mathrm{NSD}(a,b)})\mid k\in \mathbb{Z}\}$

Příklad

Největší společný dělitel čísel 12 a 42 je 6. Bézoutova rovnost tedy je:

$\alpha \cdot 12+\beta \cdot 42=6$

Jedno z možných řešení je (α, β) = (−3, 1), tedy (−3)·12 + 1·42 = 6. Jiné možné řešení je (4, −1).

Zobecnění

Bézoutova rovnost může být rozšířena jako lineární kombinace více než dvou čísel. Pro libovolná čísla $a_1,\dots ,a_n$ se společným dělitelem d existují koeficienty ${\alpha }_1,\dots ,{\alpha }_n$ tak, že:

${\alpha }_1{a}_1+\cdots +{\alpha }_n{a}_n=d$

Největší společný dělitel čísel $a_1,\dots ,a_n$ je vlastně nejmenší kladné číslo, které lze zapsat jako lineární kombinaci $a_1,\dots ,a_n$, jejíž koeficienty jsou celá čísla.

Bézoutova rovnost také existuje v jiných algebraických strukturách než v celých číslech. Nalézt ji pro libovolné dva prvky rozšířeným Eukleidovým algoritmem lze ve všech Eukleidovských oborech a ty obory, v nichž je zaručena její existence pro libovolné dva prvky, se nazývají Bézoutovy obory.

Důkaz

Ať d je největší společný dělitel čísel a a b, p = a / d a q = b / d, pak p a q jsou nesoudělná čísla. Uvažujme nyní čísla p, 2p, …, (q−1)p. Žádné z těchto čísel není kongruentní nule modulo q a jsou také jednoznačná modulo q. To znamená, že (p, 2p, …, (q−1)p) je permutace (1, 2, …, q − 1) modulo q. Proto musí existovat číslo α, 1 ≤ α ≤ q − 1 tak, že αp ≡ 1 (mod q). To znamená, že existuje i číslo β tak, že αp + βq = 1. Po vynásobení d dostaneme Bézoutovu rovnost αa + βb = d.

Externí odkazy

• Online kalkulačka Bézoutovy rovnosti (anglicky)

[zobrazit] Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii