Eukleidův algoritmus: Porovnání verzí

'''Eukleidův algoritmus''' (též '''Euklidův''') je [[algoritmus]], kterým lze určit [[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í.

* 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]].