### Java Program to Implement Extended Euclidean Algorithm based on Number Theory

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

This Program is based on Pune University BE IT SyllabusDevelop and program in C++ or Java based on number theory such as Chinese remainder or Extended Euclidean algorithm. ( Or any other to illustrate number theory for security)

Here is the source code of the Java Program to Implement Extended Euclidean Algorithm. The Java program is successfully compiled and run on a Eclipse IDE. The program output is also shown below.
Points to be remember
1. Create the Java Class with the name of ExtendedEuclied
```import java.util.Scanner;

/*
* @author Professional Cipher [www.professionalcipher.com]
*/
public class ExtendedEuclied
{

public void solve(long a, long b)
{
long x=0,y=1,last_x=1,last_y=0,temp;
while(b!=0)
{
long q=a/b;
long r=a%b;
a=b;
b=r;
temp=x;
x=last_x-q*x;
last_x=temp;
temp=y;
y=last_y-q*y;
last_y=temp;
}

System.out.println("Roots x:"+ last_x +"y:"+last_y+"\nGCD : "+a);
}

/** main function **/

public static void main (String[] args)
{
Scanner scan=new Scanner(System.in);
/** more an object of Extended Eucliead class **/
ExtendedEuclied ee=new ExtendedEuclied();
/** Accept two integers **/

System.out.println("Enter ab of an + by=gcd(a,b) \n");
long a=scan.nextLong();
long b=scan.nextLong();
/** call function solve of class extended euclied **/
ee.solve(a,b);
}
}

/*
*
*
*OUTPUT:
*Enter ab of an + by=gcd(a,b)
*105
*80
*Roots x:-3y:4
*GCD : 5
*
*/

```

1. 