If you're seeing this message, it means we're having trouble loading external resources on our website.

Pokud používáš webový filtr, ujisti se, že domény: *.kastatic.org and *.kasandbox.org jsou vyloučeny z filtrování.

Hlavní obsah

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.
Umíš anglicky? Kliknutím zobrazíš diskuzi anglické verze Khan Academy.