Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Největší společný dělitel

Definice (Eukleidovský obor integrity)

Obor integrity je eukleidovský, jestliže existuje zobrazení (eukleidovská funkce), které pro každé splňuje:

1. Jestliže a , pak
2. Pokud , existují taková, že a

Poznámka

Je-li nějaké komutativní těleso, pak je eukleidovským oborem integrity s eukleidovskou funkcí danou stupněm polynomů. Příkladem eukleidovského oboru integrity jsou např. i celá čísla (se sčítáním, násobením, unárním minus, jedničkou a nulou), kde eukleidovská funkce je funkce absolutní hodnoty prvku.

Algoritmus (Eukleidův algoritmus)

Na eukleidovském okruhu s eukleidovskou funkcí pro dva prvky najdeme největší společný dělitel následujícím postupem:

- Je-li a , vezmeme takové, že pro nějaké a . zvýšíme o a pokračujeme další iterací.
- Je-li a , potom a výpočet končí.

Dá se dokázat, že se výpočet zastaví a kroky jsou dobře definované (lze nalézt a ), tedy libovolné dva polynomy mají největšího společného dělitele.

Poznámka

Největší společný dělitel je v polynomech určen až na asociovanost () jednoznačně. Pro asociované polynomy vždy platí, že a pro nějaké .