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

---

Extended Euclidean algorithm is a reverse process of Euclidean algorithm. It says: ax + by = GCD(p,q)

Extended Euclidean find out a and b for withdraw p and q with the help of x and y.

Here p = 81 and q = 16. Take a1 = 1, a2 = 0 b1 = 0, b2 = 1. Find out others

Steps:

• next p = q % p

• next q = p

• t = b / a

• a = a1 - t*a2

• b = b1 - t*b2

• next a1 = a2 and next a2 = a

• next b1 = b2 and next b2 = b

• break iteration when p get zero

How the table build up:

p	q	t = q / p	a1	a2	a = a1-t*a2	b1	b2	b = b1-t*b2
16	81	5	1	0	1	0	1	-5
1	16	16	0	1	-16	1	-5	81
0	1

Here a = -16 and b = 81 . If x = -5 and y = 1 then this will be fulfill the condition of ax+by=GCD(p,q)