share: true aliases: - "# Rozšířený Eukleidův algoritmus (EEA)" - EEA - REA
Nechť splňují . Rozšířený Eukleidův algoritmus má na vstupu , jeho výstupem bude a dvojice Bézoutových koeficientů .
Definujeme stejně jako v EA a dále posloulnosti koeficientů
Pak pro každé platí a speciálně pro máme
#dukaz Důkaz korektnosti EEA: Provedeme silnou indukcí podle .
ZK: Pro vztah zřejmě platí:
IK:
Vytvořeno: 7. 8. 2024, 13:25 Poslední aktualizace: 7. 8. 2024, 13:25