Algorytm Euklidesa, który poznałeś w poprzednim module ma wiele praktycznych zastosowań. Oto niektóre z nich:

• Wyznaczanie największego wspólnego dzielnika (NWD) – podstawowe zadanie algorytmu.

• Skracanie ułamków – dzięki NWD można sprowadzić ułamek do postaci nieskracalnej.

• Algorytmy kryptograficzne – np. RSA, gdzie NWD i algorytm rozszerzony Euklidesa są wykorzystywane do znajdowania odwrotności modulo.

• Informatyka i teoria liczb – przydatny w zadaniach związanych z podzielnością, modularnością i w problemach optymalizacyjnych.

Ćwiczenie na rozgrzewkę