Euclid's Algorithm Example Compute ged(408,595) n Un -2 408 1 0 -1 595 0 1 0 0 408 1 0 595/408 =1 remainder 187 1 1 187 -1 1 408/187=2 remainder 34 2 2 34 3 -2 187/34 5 remainder 17 3 5 17 -16 11 34/17 =2 remainder 0 4 2 0 35 -24 Hence gcd(408,595)=r3=17=-16×408+11×595 44 Euclid’s Algorithm Example  Compute gcd(408, 595) 595/408 = 1 remainder 187 408/187 = 2 remainder 34 187/34 = 5 remainder 17 34/17 = 2 remainder 0 Hence gcd(408, 595)= r3=17=-16×408+11×595 n qn rn un vn -2 408 1 0 -1 595 0 1 0 0 408 1 0 4 2 0 35 -24 3 5 17 -16 11 2 2 34 3 -2 1 1 187 -1 1