Еуклидов алгоритам

Еуклидов алгоритам је поступак за налажење највећег заједничког делиоца (НЗД) два природна броја. Носи име по старогрчком математичару Еуклиду.

[уреди] Алгоритам

За налажење највећег заједничког делиоца два броја А и Б НЗД(А,Б) примењује се следећи поступак.

• 1. Ако је А=Б онда је НЗД(А,Б)=А
• 2. Ако је А>Б онда је НЗД(А,Б)=НЗД(А-Б,Б)
• 3. Ако је Б>А онда је НЗД(А,Б)=НЗД(А,Б-A)

Укратко за налажење НЗД два броја понављамо поступак за мањи и разлику два броја све док не добијемо два иста броја, што представља коначно решење.

То се може описати следећим псеудокодом

 function nzd(a, b)
     while a ≠ b
         if a > b
             a := a - b
         else
             b := b - a
     return a

Пример: НЗД(39,6)=НЗД(33,6)=НЗД(27,6)=НЗД(21,6)=НЗД(15,6)=НЗД(9,6)=НЗД(3,6)=НЗД(3,3)=3

[уреди] Модификација алгоритма

Значајно ефикаснији алгоритам се добија ако се уместо одузимања користи остатак при дељењу. У горњем примеру се лепо види да уствари од броја 39 одузимамо 6 све док не добијемо мањи број од 6. Значајно ефикаснији алгоритам је:

НЗД(А,Б)=

• 1. Ако је Б=0 онда НЗД(А,Б)=А
• 2. Иначе, НЗД(А,Б)=НЗД(Б, А mod Б)

где је mod остатак при дељењу броја А бројем Б.

псеудокод

 function nzd(a, b)
     if b = 0 return a
     else return nzd(b, a mod b)

1. Пример: НЗД(39,6)=НЗД(6,3)=НЗД(3,0)=3
2. Пример: НЗД(1071,1029)=НЗД(1029,42)=НЗД(42,21)=НЗД(21,0)=21

[уреди] Шира примена

Еуклидов алгоритам може се применити и на неке друге ентитете. На пример може се применити и за одређивање НЗД за два полинома.

[уреди] Пример

НЗД два полинома P(x)=x⁵+x⁴-x³-3x²-3x-1 и Q(x)=x⁴-2x³-x²-2x+1 налазимо на следећи начин користећи Еуклидов алгоритам (уз скраћивање и проширење):

1.

1a.

2.

2a.

3.

NZD(P(x),Q(x)) = R(2s) = x² + x + 1