implementing euclid's extended algorithm
import java.util.Scanner; class Lab3{ //euclids algorithm int euclid(int a, int b){ if(b==0) return a; else return euclid(b, a%b); } //euclids extended algorithm int exeuclid(int a, int m) { int A3 = m; int A2 = 0, A1 = 1; if (m == 1) return 0; while (a > 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process // same as Euclid's algo m = a % m; a = t; t = A2; // Update A1 and A2 A2 = A1 - q * A2; A1 = t; } // Make A1 positive if (A1 < 0) A1 += A3; return A1; } public static void main(String[] args) { Lab3 ob = new Lab3(); int x, y, choice; Scanner input = new Scanner(System.in); System.out.println("Enter Choice \n Enter 1 for gcd and 2 for extended ed"); choice=input.nextInt(); switch(choice) { case 1: int output; System.out.println("Enter the first number"); x = input.nextInt(); System.out.println("Enter the second number"); y = input.nextInt(); output = ob.euclid(x, y); System.out.println("GCD is:"+output); break; case 2: System.out.println("To Find Inverse"); int m, b; System.out.println("Enter m"); m=input.nextInt(); System.out.println("Enter b"); b = input.nextInt(); System.out.println("Inverse is equal to: "+ob.exeuclid(m, b)); break; default: System.out.println("Wrong Choice"); } } }Code language: JavaScript (javascript)
