V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!

Bézoutova rovnost

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
m (Nahrazení textu „</math>“ textem „\)</big>“)
 
(Nejsou zobrazeny 3 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://ww2000w.multimediaexpo.cz/mmecz/index.php/B%C3%A9zoutova_rovnost“