$1.$ Complete the Python script EuclideanAlgoShell.py that will implement the Euclidean Al$-$gorithm. Use this program in order to compute gcd$($a$,$ b$)$ where a $=1326$ and b $=374.$

def euclidgcd$($a$,$b$)$:

while b$!=0$:

#fill in Python code here

return a

a $=2322$

b $=654$

g$=$euclidgcd$($a$,$b$)$

print$($g$)$

$2.$ Complete the Python script ExtEuclideanAlgoShell.py that will implement the Extended Euclidean Algorithm.

def exteuclidgcd$($a$,$b$)$:

#Initialize variables

x$1=0$

x$2=1$

y$1=1$

y$2=0$

#loop to iteratively converge on the solution

while $($b$>0)$:

#fill in code here to complete this script

#reassign values

a$=$b

b$=$r

x$2=$x$1$

x$1=$x

y$2=$y$1$

y$1=$y

#print values at each iteration

print$($q$,$r$,$x$,$y$,$a$,$b$,$x$2,$x$1,$y$2,$y$1)$

#set final answer and pass back to main by reference

gcd$=$a

x$=$x$2$

y$=$y$2$

return x$,$y$,$gcd

a$=4864$

b$=3458$

x$,$y$,$gcd$=$exteuclidgcd$($a$,$b$)$

print$($x$,$y$,$gcd$)$

Verify your code by

a$.$ Running the Extended Euclidean Algorithm example provided in the lecture slides.

b$.$ Determining x$,$ y and gcd$($a$,$ b$)$ such that gcd$($a$,$ b$)=$ ax$+$by where a $=6090$ and b $=2431.$