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

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.