Question

(a) Show that the following algorithm computes the greatest common divisor g of the positive integers a and b, together with a solution (u, v) in integers to the equation au + bv = gcd(a, b). 1. Set u = 1, g = a, x = 0, and y = b 2. If y = 0, set v = (g − au)/b and return the values (g, u, v) 3. Divide g by y with remainder, g = qy + t, with 0 ≤ t < y 4. Set s = u − qx 5. Set u = x and g = y 6. Set x = s and y = t 7. Go To Step (2) (b) Implement the above algorithm on a computer using the computer language of your choice. (c) Use your program to compute g = gcd(a, b) and integer solutions to the equation au + bv = g for the following pairs (a, b). (i) (527, 1258) (ii) (228, 1056) (iii) (163961, 167181) (iv) (3892394, 239847) (d) What happens to your program if b = 0? Fix the program so that it deals with this case correctly. (e) It is often useful to have a solution with u > 0. Modify your program so that it returns a solution with u > 0 and u as small as possible. [Hint. If (u, v) is a solution, then so is (u + b/g, v − a/g).] Redo (c) using your modified program.

Answer 1

public class GCD {
   
    public static void main(String args[]){
             //Enter two number whose GCD needs to be calculated.      
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please enter first number to find GCD");
        int number1 = scanner.nextInt();
        System.out.println("Please enter second number to find GCD");
        int number2 = scanner.nextInt();
      
        System.out.println("GCD of two numbers " + number1 +" and " 
                           + number2 +" is :" + findGCD(number1,number2));
      
      
    }

    private static int findGCD(int number1, int number2) {
        //base case
        if(number2 == 0){
            return number1;
        }
        return findGCD(number2, number1%number2);
    }
  
}