Using C, implement the "Extended Euclidean Algorithm", see page below. This algorithm is useful for RSA cryptography. Demonstrate that it works on some examples.

Algorithm 8.4.1 Extended Euclidean Algorithm [Given integers A and B with A> B > 0, this algorithm com- putes gcd(A, B) and finds integers s and t such that sA +tB- gcd(A, B)] Input: A, B [integers with A > B 0] Algorithm Body: Ipre-condtion: a - SA +tB and b-uA vB] while (b t 0) loop invariant: a-SA +tB and b-uA +vB, gcd(a, b-gcd(A. B)] a mod b, q:a div b end while gcd:a Ipost-condition: gcd(A. B)-a sA +tB Output: gcd/a positive integer], s, t [integers]