Eukleidův algoritmus: Porovnání verzí

'''Eukleidův algoritmus''' (též '''Euklidův''') je [[algoritmus]], kterým lze určit [[Největšínejvětší společný dělitel|největšího společného dělitele]] dvou [[Přirozené číslo|přirozených čísel]], tedy největší číslo takové, že beze zbytku dělí obě čísla. Jedná se o jeden z nejstarších známých netriviálních algoritmů a postupně vznikla řada jeho modifikací například pro příbuzné úlohy. Z nich nejdůležitější je [[rozšířený Eukleidův algoritmus]], kterým lze nalézt [[Bézoutova rovnost|Bézoutovu rovnost]], neboli vyjádření největšího společného dělitele dvou čísel jejich lineární kombinací.

Opakovaně prováděné operace nemění hodnotu největšího společného dělitele

(neboť NSD(''u'', ''v'') = NSD(''v'', ''u'' - ''qv'') pro libovolné celé číslo ''q''), ale v každém kroku se hodnota proměnné ''v'' sníží, takže je zřejmé, že v konečném počtu kroků se algoritmus ukončí s tím, že ''v'' je nulové. Tehdy obsahuje proměnná ''u'' největší společný dělitel, neboť NSD(''u'', 0) = ''u'', což musí být současně největší společný dělitel původních čísel, neboť, jak už bylo uvedeno, hlavní smyčka programu hodnotu největšího společného dělitele nemění.

Mějme čísla ''u'' = 40902, ''w'' = 24140. Výpočet probíhá následujícím způsobem:

| 40902 = 24140×1 + 16762

| 24140 = 16762×1 + 7378

| 16762 = 7378×2 + 2006

| 7378 = 2006×3 + 1360

| 2006 = 1360×1 + 646

| 1360 = 646×2 + 68

| 646 = 68×9 + 34

| 68 = 34×2 + 0

* Na základě tohoto algoritmu lze rychle spočítat [[inverzní prvek]] k násobení v [[modulární aritmetika|modulární aritmetice]]. Největší společný dělitel dvou čísel se dá vyjádřit [[Bézoutova rovnost|Bézoutovou rovností]] jako součet násobků těchto čísel. Pokud je tímto největším společným dělitelem 1, pak dostaneme součin prvku a jeho inverzního. Tedy pokud máme spočítat inverzní prvek ''x'' modulo ''n'' a vyjde nám vyjádření největšího společného dělitele Bézoutovou rovností ''ax'' + ''bn'' = 1, kde známe všechny proměnné. Máme tak vlastně přímo rovnost ''ax''=1 [[modulo]] ''n'' a nalezené ''a'' je hledaný inverzní prvek. Tento výpočet inverzního prvku je častý v aplikacích [[teorie čísel]], zejména v [[kryptografie|kryptografii]].

* Tento algoritmus lze použít nejen pro čísla, ale také pro [[polynom]]y. Polynom je s jeho využitím možno rozdělit na součin polynomů oddělených dle násobnosti kořenů. Derivace snižuje násobnost každého kořene o 1 a zavádí nové kořeny. Největší společný dělitel s původním polynomem odstraňuje nové kořeny. Například lze tak zjistit kořeny polynomu (x - a)(x - a)(x - a)(x - b)(x - b), přestože neexistuje algoritmus na výpočet kořenů polynomu stupně většího než 4.