The English encyclopedia Allmultimedia.org will be launched in two phases.
The final launch of the Allmultimedia.org will take place on February 27, 2026
(shortly after the 2026 Winter Olympics).

Bézoutova rovnost

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
m (Nahrazení textu „</math>“ textem „\)</big>“)
 
(Nejsou zobrazeny 2 mezilehlé verze.)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Bézoutova rovnost|700}}
+
'''Bézoutova rovnost''' je [[Lineární rovnice|lineární]] [[diofantická rovnice|diofantická]] [[rovnice]] v&nbsp;[[Teorie čísel|teorii čísel]]. Říká, že [[největší společný dělitel]] dvou [[Přirozené číslo|přirozených čísel]] ''a'' a ''b'' lze zapsat jako [[Lineární kombinace|lineární kombinaci]] těchto dvou čísel, jejíž koeficienty jsou celá čísla – nazývají se ''Bézoutovy koeficienty'' nebo ''Bézoutova čísla'':
 +
: <big>\(\mathrm{NSD}(a, b) = \alpha a + \beta b;  a,b\in\mathbb{N}; \alpha,\beta\in\mathbb{Z}\)</big>
 +
 +
== Algoritmus ==
 +
 +
Bézoutovy koeficienty lze určit [[Rozšířený Eukleidův algoritmus|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ů:
 +
 +
: <big>\( \left\{ \left(\alpha+\frac{kb}{\mathrm{NSD}(a,b)},\ \beta-\frac{ka}{\mathrm{NSD}(a,b)}\right) \mid k \in \mathbb{Z} \right\} \)</big>
 +
 +
== Příklad ==
 +
 +
Největší společný dělitel čísel 12 a 42 je 6. Bézoutova rovnost tedy je:
 +
 +
: <big>\(\alpha\cdot12 + \beta\cdot42 = 6\)</big>
 +
 +
Jedno z&nbsp;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 <big>\(a_1, \ldots, a_n\)</big> se společným dělitelem ''d'' existují koeficienty <big>\(\alpha_1, \ldots, \alpha_n\)</big> tak, že:
 +
 +
: <big>\(\alpha_1 a_1 + \cdots + \alpha_n a_n = d\)</big>
 +
 +
Největší společný dělitel čísel <big>\(a_1, \ldots, a_n\)</big> je vlastně nejmenší kladné číslo, které lze zapsat jako lineární kombinaci <big>\(a_1, \ldots, a_n\)</big>, jejíž koeficienty jsou celá čísla.
 +
 +
Bézoutova rovnost také existuje v jiných [[algebraická struktura|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ý obor|Eukleidovských oborech]] a ty obory, v nichž je zaručena její existence pro libovolné dva prvky, se nazývají [[Bézoutův obor|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'', 2''p'', …, (''q''−1)''p''. Žádné z těchto čísel není [[Kongruence|kongruentní]] nule [[Zbytek po dělení|modulo]] ''q'' a jsou také jednoznačná modulo ''q''. To znamená, že (''p'', 2''p'', …, (''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 ==
 +
* [http://wims.unice.fr/wims/wims.cgi?module=tool/arithmetic/bezout.en Online kalkulačka Bézoutovy rovnosti (anglicky)]
 +
 +
 +
{{Článek z Wikipedie}}
[[Kategorie:Rovnice]]
[[Kategorie:Rovnice]]

Aktuální verze z 14. 8. 2022, 14:51

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

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ů:

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

Příklad

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

\(\alpha\cdot12 + \beta\cdot42 = 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, \ldots, a_n\) se společným dělitelem d existují koeficienty \(\alpha_1, \ldots, \alpha_n\) tak, že:

\(\alpha_1 a_1 + \cdots + \alpha_n a_n = d\)

Největší společný dělitel čísel \(a_1, \ldots, a_n\) je vlastně nejmenší kladné číslo, které lze zapsat jako lineární kombinaci \(a_1, \ldots, 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


Citováno z „http://www.multimediaexpo.cz/mmecz/index.php/B%C3%A9zoutova_rovnost“