Assignment: Extended Euclidean Algorithm
Using any programming language of your choice implement the Extended Euclidean algorithm
Specifications: The program should take two inputs
1) An integer a, which is the modulus
2) A non-negative integer b that is less than a.
The program should output three values
1) gcd(a,b)
2) Integer x and
3) Integer y, such that ax + by = gcd(a,b).
Test 1
1) Run your program with a = 1759 b = 550
2) What are your outputs?
3) What is the modular multiplicative inverse of 550 mod 1759?
Test 2
1) Run your program with a = 43 b = 17
2) What are your outputs?
3) What is the modular multiplicative inverse of 17 mod 43?
Note that the modular multiplicative inverse has to be non-negative and less than 43.
Test 3
1) Run your program with a = 400 b = 10
2) What are your outputs?
3) What is the modular multiplicative inverse of 10 mod 400?
The response should include a reference list. Double-space, using Times New Roman 12 pnt font, one-inch margins, and APA style of writing and citations.