Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 1
Lekce 5: Modulární aritmetika- Co je to modulární aritmetika?
- Operátor modulo
- Výzva Modulo
- Kongruence modulo
- Kongruence modulo
- Relace ekvivalence
- Věta o dělení se zbytkem
- Modulární sčítání a odčítání
- Modulární sčítání
- Výzva modulo (sčítání a odčítání)
- Modulární násobení
- Modulární násobení
- Modulární mocnění
- Rychlé modulární umocňování
- Rychlé modulární umocňování
- Modulární inverze
- Euklidův algoritmus
Euklidův algoritmus
Vzpomeň si, že největší společný dělitel (NSD) dvou celých čísel A a B je největší celé číslo, které dělí A i B.
Eucleidův algoritmus je metoda pro rychlé hledání NSD dvou celých čísel.
Algoritmus
Eucleidův algoritmus pro hledání NSD(A, B) zní takto:
- Je-li A = 0, pak NSD(A, B) = B, jelikož NSD(0, B) = B, a máme hotovo.
- Je-li B = 0, pak NSD(A, B) = A, jelikož NSD(A, 0) = A, a máme hotovo.
- Napiš A ve zbytkovém tvaru (A = B⋅Q + R)
- Najdi NSD(B, R) pomocí Eucleidova Algoritmu, jelikož NSD(A, B) = NSD(B, R).
Příklad:
Najdi největší společný dělitel čísel 270 a 192.
- A=270, B=192
- A ≠0
- B ≠0
- Využij dělení pod sebou k nalezení výsledku 270/192 = 1 se zbytkem 78. To lze zapsat jako: 270 = 192 * 1 +78
- Najdi NSD(192, 78), jelikož NSD(270, 192) = NSD(192, 78).
A = 192, B = 78
- A ≠0
- B ≠0
- Využij dělení pod sebou k nalezení výsledku 192/78 = 2 se zbytkem 36. To lze zapsat jako:
- 192 = 78 * 2 + 36
- Najdi NSD(78, 36), jelikož NSD(192, 78) = NSD(78, 36).
A = 78, B = 36
- A ≠0
- B ≠0
- Využij dělení pod sebou k nalezení výsledku 78/36 = 2 se zbytkem 6. To lze zapsat jako:
- 78 = 36 * 2 + 6
- Najdi NSD(36,6), jelikož NSD(78, 36) = NSD(36, 6).
A = 36, B = 6
- A ≠0
- B ≠0
- Využij dělení pod sebou k nalezení 36/6 = 6 se zbytkem 0. To lze zapsat jako:
- 36 = 6 * 6 + 0
- Najdi NSD(6, 0), jelikož NSD(36, 6) = NSD(6, 0).
A=6, B=0
- A ≠0
- B =0, NSD(6, 0) = 6.
Ukázali jsme tedy:
NSD(270, 192) = NSD(192, 78) = NSD(78, 36) = NSD(36, 6) = NSD(6, 0) = 6.
NSD(270, 192) = 6
Pochopení Eucleidova algoritmu
Prozkoumáme-li Eucleidův algoritmus, můžeme si všimnout, že využívá těchto vlastností:
- NSD(A, 0) = A
- NSD(0, B) = B
- Je-li A = B⋅Q + R a B≠0, pak NSD(A, B) = NSD(B, R), kde Q je celé číslo a R je celé číslo mezi 0 a B-1.
První dvě vlastnosti umožňují spočítat NSD, je-li alespoň jedno z čísel rovno 0. Třetí vlastnost nám umožňuje vzít větší, složitější problém a redukuje ho na menší a snadnější.
Eucleidův algoritmus využívá těchto vlastností rychlým zjednodušením příkladu pomocí třetí vlastnosti, dokud není snadno řešitelný jednou z prvních dvou vlastností.
Proč ty vlastnosti fungují pochopíme důkazem.
Platnost NSD(A, 0) = A dokážeme takto:
- Největší celé číslo, které dělí A je A.
- Všechna celá čísla dělí 0, jelikož pro každé celé číslo C platí C ⋅ 0 = 0. Z toho musíme vyvodit, že A dělí 0.
- Největší číslo, které dělí jak A, tak 0, je A.
Důkaz pro NSD(0, B) = B je nyní zřejmý. (Stejný postup, jen nahradíme A za B).
Pro důkaz NSD(A, B) = NSD(B, R) musíme nejdřív dokázat NSD(A, B) = NSD(B, A-B).
Mějme tři celá čísla A, B a C taková, že A - B = C.
Důkaz, že NSD(A, B) dělí C.
NSD(A, B), z definice, dělí A. Z toho plyne, že A musí být násobkem NSD(A, B). Tedy X⋅NSD(A, B) = A, kde X je celé číslo.
NSD(A, B), z definice, dělí B. Z toho plyne, že B musí být násobkem NSD(A, B). Tedy Y⋅NSD(A,B) = B, kde Y je celé číslo.
A - B = C dává tedy:
- X⋅NSD(A, B) - Y⋅NSD(A, B) = C
- (X - Y)⋅NSD(A, B) = C.
Vidíme tedy, že NSD(A, B) dělí C.
Ilustrace tohoto důkazu je ukázána v levé části obrázku níže:
Důkaz, že NSD(B, C) dělí A.
NSD(B,C), z definice, dělí B. Z toho plyne, že B musí být násobkem NSD(B,C). Tedy M⋅NSD(B,C)=B, kde M je celé číslo.
NSD(B, C), z definice, dělí C. Z toho plyne, že C musí být násobkem NSD(B, C). Tedy N⋅NSD(B, C) = C, kde N je celé číslo.
A - B = C dává tedy:
- B + C = A
- M⋅NSD(B,C) + N⋅NSD(B,C) = A
- (M + N)⋅NSD(B,C) = A
Vidíme tedy, že NSD(B, C) dělí A.
Ilustrace tohoto důkazu je ukázána na obrázku níže.
Důkaz, že NSD(A, B) = NSD(A, A-B).
- NSD(A,B), z definice, dělí B.
- Ukázali jsme, že NSD(A,B) dělí C.
- Jelikož NSD(A,B) dělí B i C, je to společný dělitel B a C.
NSD(A,B) musí být menší nebo roven NSD(B,C), jelikož NSD(B,C) je „největší“ společný dělitel B a C.
- NSD(B,C), z definice, dělí B.
- Ukázali jsme, že NSD(B,C) dělí A.
- Jelikož NSD(B,C) dělí A a i B, je to společný dělitel A a B.
NSD(B,C) musí být menší nebo roven NSD(A,B), jelikož NSD(A,B) je „největší” společný dělitel A a B.
Platí-li tedy NSD(A, B) ≤ NSD(B, C) a NSD(B, C) ≤ NSD(A, B), můžeme tvrdit:
NSD(A, B) = NSD(B, C)
Což je ekvivalentní:
NSD(A, B) = NSD(B, A-B)
Ilustrace tohoto důkazu je znázorněna v právé části obrázku níže.
Důkaz, že NSD(A, B) = NSD(B, R).
Ukázali jsme, že NSD(A, B) = NSD(B, A-B).
Na pořadí nezáleží, takže platí NSD(A,B)=NSD(A-B,B).
Opakovaně použijeme NSD(A, B) = NSD(A-B, B) a získáme:
NSD(A, B) = NSD(A-B, B) = NSD(A-2B, B) = NSD(A-3B, B) = ... = NSD(A-Q⋅B, B)
Platí však A = B⋅Q + R, takže A-Q⋅B = R.
Proto platí NSD(A, B) = NSD(R, B).
Na pořadí nezáleží, takže:
NSD(A, B) = NSD(B, R).
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.