Extended Euclidean Algorithm This algorithm first determines the greatest common divisor of the parameters a,b. Then the algorithm finds the values of x and y that solve the equation LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYrLUkjbWlHRiQ2JVEjYXhGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSSNtb0dGJDYtUSIrRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0Y9LyUpc3RyZXRjaHlHRj0vJSpzeW1tZXRyaWNHRj0vJShsYXJnZW9wR0Y9LyUubW92YWJsZWxpbWl0c0dGPS8lJ2FjY2VudEdGPS8lJ2xzcGFjZUdRLDAuMjIyMjIyMmVtRicvJSdyc3BhY2VHRkwtRiw2JVEiYkYnRi9GMi1GNjYtUSJ+RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSYwLjBlbUYnL0ZORlYtRiw2JVEieUYnRi9GMi1GNjYtUSI9RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSwwLjI3Nzc3NzhlbUYnL0ZORmluLUYsNiVRJGdjZEYnRi9GMi1JKG1mZW5jZWRHRiQ2JC1GIzYmLUYsNiVRImFGJ0YvRjItRjY2LVEiLEYnRjlGOy9GP0YxRkBGQkZERkZGSEZVL0ZOUSwwLjMzMzMzMzNlbUYnRk9GOUY5Rjk=. with(ArrayTools):
<Text-field style="Heading 1" layout="Heading 1">Euclidgcd(a,b)</Text-field> euclidgcd:=proc(a,b) description"This process will derive the gcd(a,b) of given parameters a and b."; #option trace; local i,r: global R, Q; with(StringTools); #Check for greatest parameter and initialize R(remainder table)and Q(Quotient table); if a>b then R[0]:=b: Q[1]:=trunc(a/b): R[1]:=b*frac(a/b): cat(a ,"=", Q[1] ,"*", b ,"+", R[1]); print(%); else R[0]:=a: Q[1]:=trunc(b/a): R[1]:=a*frac(b/a): cat(b ,"=", Q[1] ,"*", a ,"+", R[1]); print(%); end if; #Now loop to find quotients and remainders for i from 2 while r<>1 do Q[i]:=trunc(R[i-2]/R[i-1]): R[i]:=R[i-1]*frac(R[i-2]/R[i-1]): cat(R[i-2] ,"=", Q[i] ,"*", R[i-1] ,"+", R[i]); print(%); r:=R[i]: end do; print(); type(Q); #Convert the quotients to an Array to be used by other programs. Q:=convert(Q,array); #Output section print(Quotients = Q()); cat("gcd(",a,",",b,")=",R[i-2]); end proc:
<Text-field style="Heading 1" layout="Heading 1">Euclidext(a,b)</Text-field> euclidext:=proc(a,b) #option trace; #global values are "a-return" and "b-return" global aret,bret; local i,x,y,n; euclidgcd(a,b): with(ArrayTools): n:=Size(Q,2); x[0]:=0: x[1]:=1: y[0]:=1: y[1]:=0: for i from 2 to n+1 do x[i]:=-Q[i-1]*x[i-1]+x[i-2]: y[i]:=-Q[i-1]*y[i-1]+y[i-2]: end do; cat("x[n]=", x[n+1]); print(%); cat("y[n]=", y[n+1]); print(%); if a<b then print(a*x[n+1]+b*y[n+1]); aret:=x[n+1]; bret:=y[n+1]; else print(b*x[n+1]+a*y[n+1]); aret:=y[n+1]; bret:=x[n+1]; end if; end proc:
<Text-field style="Heading 1" layout="Heading 1">Example.</Text-field> Find the greatest common divisor of 3511 and 65537. The find a solution of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkjbW5HRiQ2JFElMzUxMUYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1JI21vR0YkNi1RIn5GJ0YvLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0Y4LyUpc3RyZXRjaHlHRjgvJSpzeW1tZXRyaWNHRjgvJShsYXJnZW9wR0Y4LyUubW92YWJsZWxpbWl0c0dGOC8lJ2FjY2VudEdGOC8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRkctSSNtaUdGJDYlUSJ4RicvJSdpdGFsaWNHUSV0cnVlRicvRjBRJ2l0YWxpY0YnLUYzNi1RIitGJ0YvRjZGOUY7Rj1GP0ZBRkMvRkZRLDAuMjIyMjIyMmVtRicvRklGVy1GLDYkUSY2NTUzN0YnRi9GMi1GSzYlUSJ5RidGTkZRLUYzNi1RIj1GJ0YvRjZGOUY7Rj1GP0ZBRkMvRkZRLDAuMjc3Nzc3OGVtRicvRklGXW8tRks2JVEkZ2NkRidGTkZRLUkobWZlbmNlZEdGJDYkLUYjNiZGKy1GMzYtUSIsRidGL0Y2L0Y6RlBGO0Y9Rj9GQUZDRkUvRklRLDAuMzMzMzMzM2VtRidGWUYvRi9GLw==. euclidext(3511,65537); LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JVEzNjU1Mzc9MTgqMzUxMSsyMzM5RicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JVExMzUxMT0xKjIzMzkrMTE3MkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JVExMjMzOT0xKjExNzIrMTE2N0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JVEuMTE3Mj0xKjExNjcrNUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JVEtMTE2Nz0yMzMqNSsyRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JVEoNT0yKjIrMUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== LUkjbWlHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHRic2JVEoMj0yKjErMEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== JSFH L0kqUXVvdGllbnRzRzYiPUYkNiM7IiIiIiIoRVxbbChGKCIjPSIiI0YoIiIkRigiIiYiJEwjIiIlRihGKUYsIiInRiw= USt4W25dPTI2MjI2NiI= USt5W25dPS0xNDA1NiI= IiIi