ČVOZ - Čínská věta o zbytcích

Chinese Remainder Theorem (CRT)

#veta Čínská věta o zbytcích

Uvažujme soustavu lineárních kongruencí

kde jsou navzájem nesoudělná, tedy pro každá .

Řešení této soustavy vždy existuje a všechna řešení jsou kongruentní modulo (tedy v je řešení určení jednoznačně), kde

Dále definujeme

(tedy jako součin všech modulů kromě -tého)

#dukaz Rozjezd důkazu:

  • Pokud

    • (tedy je obsaženo v )
    • Řešení neexistuje
    • Ale triviálně platí tvrzení

  • Pokud

    • (tedy není obsaženo v )
    • Řešení má

  • Skutečně platí:

    • Pro každé je jedničce kongruentní jen 1 z členů, ostatní jsou kongruentní nule
    • Tedy tento výraz řeší všechny lineární kongruence ze vstupní soustavy

Příklad

../Attachments/Pasted image 20240111200941.png

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25