Bézoutova rovnost

Z Wikipedie, otevřené encyklopedie

Bézoutova rovnost je lineární diophantická 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:

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

[editovat] 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{gcd}(a,b)},\ \beta-\frac{ka}{\mathrm{gcd}(a,b)}\right) \mid k \in \mathbb{Z} \right\}$

[editovat] 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).

[editovat] 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.

[editovat] 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.