This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
/*
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).
*/
/**
** Java Program to implement Extended Euclid Algorithm
**/
importjava.util.Scanner;
/** Class ExtendedEuclid **/
publicclassExtendedEuclid
{
/** Function to solve **/
publicvoidsolve(longa,longb)
{
longx=0,y=1,lastx=1,lasty=0,temp;
while(b!=0)
{
longq=a/b;
longr=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);