# Java Program to Implement Extended Euclid Algorithm

This is a Java Program to Implement Extended Euclid Algorithm. The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y (one of which is typically negative) that satisfy Bézout’s identity
ax + by = gcd(a, b).

Here is the source code of the Java Program to Implement Extended Euclid Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
** Java Program to implement Extended Euclid  Algorithm
**/

import java.util.Scanner;

/** Class ExtendedEuclid **/
public class ExtendedEuclid
{
/** Function to solve **/
public void solve(long a, long b)
{
long x = 0, y = 1, lastx = 1, lasty = 0, temp;
while (b != 0)
{
long q = a / b;
long r = a % b;

a = b;
b = r;

temp = x;
x = lastx - q * x;
lastx = temp;

temp = y;
y = lasty - q * y;
lasty = temp;
}
System.out.println("Roots  x : "+ lastx +" y :"+ lasty);
}
/** Main function **/
public static void main (String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Extended Euclid Algorithm Test\n");
/** Make an object of ExtendedEuclid class **/
ExtendedEuclid ee = new ExtendedEuclid();

/** Accept two integers **/
System.out.println("Enter a b of ax + by = gcd(a, b)\n");
long a = scan.nextLong();
long b = scan.nextLong();
/** Call function solve of class ExtendedEuclid **/
ee.solve(a, b);
}
}


Output:

Extended Euclid Algorithm Test

Enter a b of ax + by = gcd(a, b)

120 23
Roots  x : -9 y :47