Bézoutova rovnost
Kategorie: Nezařazeno (celkem: 23181 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 12. srpna 2008
- Zobrazeno: 4657×
- Licence: GNU Free Documentation License
- Seznam autorů a změn
- Vyloučení odpovědnosti
Příbuzná témata
Bézoutova rovnost
Bézoutova rovnost je lineární Diofantická rovnice v teorii čísel. Říká, že největší společný dělitel (gcd - z angl. greatest common divisor) 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:
Obsah |
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ů:
Příklad
Největší společný dělitel čísel 12 a 42 je 6. Bézoutova rovnost tedy je:
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 
se společným dělitelem d existují koeficienty 
tak, že:
Největší společný dělitel čísel je vlastně nejmenší kladné číslo, které lze zapsat jako lineární kombinaci , jejíž koeficienty jsou celá čísla.
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 znemená, že existuje i číslo ? tak, že ?p + ?q = 1. Po vynásobení d dostaneme Bézoutovu rovnost ?a + ?b = d.
Viz také
- Rozšířený Eukleidův algoritmus