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)