Euclidian Algorithm Example Find g.c.d、(1547,560 1547=2*560+427 560=1*427+133 427=3*133+28 133=4*28+21 21=1*21+7 21=3*7+0 Thus g.c. d(1547,560)=7Euclidian Algorithm • Example: – Find g.c.d.(1547, 560) – 1547 = 2*560+427 – 560= 1*427 + 133 – 427 = 3*133 + 28 – 133 = 4*28 + 21 – 21 = 1*21 + 7 – 21 = 3*7 + 0 – Thus g.c.d(1547,560) = 7