Implement the Euclidean Algorithm. $(15$ points$)$

Given two integer inputs a and $b,$ return the greatest common divisor $($gcd$).$ You MUST show the following tests $($You can change the function name$).$

a$)gcd(0,15)$

b$)gcd(39,13)$

c$)gcd(31356,55576)$

Implement the Extended Euclidean Algorithm. $(15$ points$)$

Given two integer inputs $x$ and $n,$ return the inverse of $x$ modulo $n.$

You MUST show the following tests $($You can change the function name$).$

a$)$ inv$(24,8)$

b$)$ inv $(11,29)$

c$)$ inv $(0,983)$