Finding Linear Combinations

Write a class named LinearCombinationFinder whose main method prompts the user for two positive integers (separated by spaces) and then applies the Extended Euclidean Algorithm to these values to find their greatest common divisor and a linear combination of these values equal to it.

Sample run:

This program finds a linear combination of two positive 
numbers that equals the gcd of those numbers
-------------------------------------------------------
Enter the two numbers you wish to consider (separated by a space): 1239 168

Work:
x = 1, y = -7, a = 168, b = 63, q = 7, lastX = 0, lastY = 1
x = -2, y = 15, a = 63, b = 42, q = 2, lastX = 1, lastY = -7
x = 3, y = -22, a = 42, b = 21, q = 1, lastX = -2, lastY = 15
x = -8, y = 59, a = 21, b = 0, q = 2, lastX = 3, lastY = -22

The following is a linear combination of 1239 and 168 equal to their gcd:

   3*1239 + -22*168 = 21