Hledání Bezoutových koeficientů podle Euklidova algoritmu

Při provádění Euklidova algoritmu si pamatujeme vztahy typu

a = k \cdot b + r

, následně do nich zpětně dosadíme.

Počet kroků Euklidova algoritmu

Pro $a > b$ platí $b \cdot (a mod b) < \frac{a \cdot b}{2}$ . Tudíž součin čísel, jejichž $\gcd$ hledáme, se pokaždé sníží alespoň dvakrát. Tedy časová složitost je $𝒪 (\log (a \cdot b)) = 𝒪 (\log (a) + \log (b))$ .

Nejmenší $b$ , které potřebuje $n$ kroků, je $F_{n + 1}$ .

Diofantická rovnice

Věta. Řešení rovnice

a x + b y = c

ℤ

existuje právě tehdy, pokud

\gcd (a, b) | c

Důkaz.

( $\Rightarrow$ ) $\gcd (a, b) | a \land \gcd (a, b) | b ∴ \gcd (a, b) | c$

( $\Leftarrow$ ) Nechť $c^{'} = c \div \gcd (a, b)$ . Podle věty o Bezoutových koeficientech $a x_{0} + b y_{0} = \gcd (a, b)$ . Zvolme $x = c^{'} \cdot x_{0}, y = c^{'} \cdot y_{0}$ , poté přenásobením rovnice $c^{'}$ získáme $a x + b y = c$ .

Věta. Jestliže rovnice

a x + b y = c

má řešení

x_{0}, y_{0}

. Označme

a^{'} = a \div g c d (a, b), b^{'} = b \div g c d (a, b)

, pak všechna řešení jsou ve tvaru

x = x_{0} + k \cdot b^{'}, y = y_{0} - k \cdot a^{'}