Alogrytm Euklidesa

Euklides z Aleksandrii  – matematyk grecki przez większość życia działający w Aleksandrii. Najważniejsze z dzieł Euklidesa to „Elementy geometrii”, traktat stanowiący wykładnię geometrii, teorii liczb i podstawowych pojęć matematycznych. 

                                                                     Algorytm Euklidesa.

Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) liczb całkowitych.

Przykład:

NWD(243,111)=?

243÷111=2, reszty 21

111÷21=5,reszty 6

21÷6=3, reszty 3 

6÷3=2,reszty 0 

OStatnia niezerowa reszta wynosi 3.

NWD(243,111)=3