# Extended Euclidean Algorithm in Java

«
»
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.

1. `/**`
2. ` ** Java Program to implement Extended Euclid  Algorithm`
3. ` **/`
4. ` `
5. `import java.util.Scanner;`
6. ` `
7. `/** Class ExtendedEuclid **/`
8. `public class ExtendedEuclid`
9. `{`
10. `    /** Function to solve **/`
11. `    public void solve(long a, long b)`
12. `    {`
13. `        long x = 0, y = 1, lastx = 1, lasty = 0, temp;`
14. `        while (b != 0)`
15. `        {`
16. `            long q = a / b;`
17. `            long r = a % b;`
18. ` `
19. `            a = b;`
20. `            b = r;`
21. ` `
22. `            temp = x;`
23. `            x = lastx - q * x;`
24. `            lastx = temp;`
25. ` `
26. `            temp = y;`
27. `            y = lasty - q * y;`
28. `            lasty = temp;            `
29. `        }`
30. `        System.out.println("Roots  x : "+ lastx +" y :"+ lasty);`
31. `    }`
32. `    /** Main function **/`
33. `    public static void main (String[] args) `
34. `    {`
35. `        Scanner scan = new Scanner(System.in);`
36. `        System.out.println("Extended Euclid Algorithm Test\n");`
37. `        /** Make an object of ExtendedEuclid class **/`
38. `        ExtendedEuclid ee = new ExtendedEuclid();`
39. ` `
40. `        /** Accept two integers **/`
41. `        System.out.println("Enter a b of ax + by = gcd(a, b)\n");`
42. `        long a = scan.nextLong();`
43. `        long b = scan.nextLong();`
44. `        /** Call function solve of class ExtendedEuclid **/`
45. `        ee.solve(a, b);        `
46. `    }`
47. `}`

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