01204211/activity7 number theory 2

This is part of 01204211-58.

In-class activities

A.1 Implement the Extended-GCD algorithm and use it to find, for each following pair of $a$ and $b$, the g.c.d. of $a$ and $b$ and a pair of integers $(x,y)$ such that $ax+by=gcd(a,b)$.

(a) $a=5,b=7$

(b) $a=500,b=7123$

(c) $a=55515,b=71234$

(d) $a=5551532,b=7123456$

(e) $a=$your student id, $b=$ the student id of another student sitting next to you.