YOU CAN USE ANY LANGUAGE, (JAVA, JAVASCRIPT, C/C++ PREFERRED)

MTH 182 GCD Extra Credit Project V1 Spring 2019 Here is an important result about the Greatest Common Divisor of two positive integers Theorem: If a.b eZ and let S keZ:k amtbn where m, n eZ. Then ged(ab min (S) Thus, 3s,t eZ such that gcd(a,b) as+br For example, if a 28,b-15, then gcd (28,15)--28(7)+15(-13); hence,s 7 and 13 are integers that the theorem guarantees to exist. The problem is how to find them in a systematic way. Here is a method that is based on the Euclidean Algorithm R, [ 1 0 28 R, 0 15 Step Form the matrix Step 2 Since 28 div 15, subtract the second row from the first row: R-K, [ 1-0 0-1 28-51-1-1 13 0 1 15 Step 3 Since 15 div 13-1, subtract the first row from the second row 1 -1 13 R,-R 0-1- 15-13 Step 4: Since 13div 2-6, subtract 6 times the second row from the first row R,-6R1-6-1) -1-6(2) 13-6(2) 7-13 1 -1 2 2 R, Step 5: Since 2 div1 2, subtract 2 times the first row from the second row: 7 -13 1 R-2R27) 2-23) 2-2)15 28 0 At this point we are done because the second row in this case has a zero in the third column. The desired values are in the first row s 7,1-13,and d. In fact, by using the corresponding values in the second row, all values of s and tsuch that 28s +15t-1 gcd(a,b) are s 7-15k and -13+28k where ke2 In general, you need to repeat steps similar to steps 2-5 until a zero appears in the third column as in step 5 If the zero is in the first row, then the second row contains the values s, t and d; otherwise, the these values are n the first row. The allowed operations are of ony two types: (1) Replace the first row with the row obtained by subtracting k times the second row where k0 is an integer (denoted by R R-kR, ). (2) Replace the second row with the row obtained by subtracting k times the first row where k0 is an integer (denoted by R, R,-RR) Bonus Project (20 pt: Added to Quiz-Worksheet Scores) Using the ideas of this method, write a program that requests the user to enter to positive integers a and b and computes and prints the geda,b) along with values for s and t such that gcd(a,b) as+bt