Algorytm Euklidesa

nww(a,b) = 2^max{a1,b1}*3^max{a2,b2}*5^max{a3,b3}

a = 2^a1*3^a2*5^a3 b = 2^b1*3^b2*5^b3

nwd(a,b) = 2^min{a1,b1}*3^min{a2,b2}*5^min{a3,b3}

wniosek: nwd(a,b) * nww(a,b) = a * b

Metoda szkolna

nwd(150, 105) = 15

150 = 1*105 + 45

105 = 2*45 + 15

45 = 3*15 + 0

Ponieważ a(mod b) ≤ a/2

złożoność ≈ log(Max{a,b}) operacji mod

---