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.
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.
Related Posts:
- Apply for Computer Science Internship
- Check Programming Books
- Practice Information Technology MCQs
- Check Java Books
- Practice Programming MCQs