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).

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);

`}`

`}`

Extended Euclid Algorithm Test Enter a b of ax + by = gcd(a, b) 120 23 Roots x : -9 y :47

**Sanfoundry Global Education & Learning Series – 1000 Java Programs.**

If you wish to look at all Java Programming examples, go to Java Programs.