Euclidean and Extended Euclidean for GCD

Euclidean algorithm for finding Greatest Common Divisor (GCD) of two numbers

Example: GCD for 81 and 16

Steps:

• next a = b % a

• next b = a

• if a get 0 then stop iteration and pick b as GCD

example solution table:

here a = 81 and b = 16

a = b % a	b = a
16 % 81 = 16	81
81 % 16 = 1	16
16 % 1 = 0	1

GCD = 1