Java Program to Implement Extended Euclid Algorithm

2021 VietMX JAVA 0

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 ** 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);       
    }
}

Output:

1
2
3
4
5
6
Extended Euclid Algorithm Test
  
Enter a b of ax + by = gcd(a, b)
  
120 23
Roots  x : -9 y :47

Related posts:

Introduction to Spring MVC HandlerInterceptor
Introduction to Spring Data JPA
Java Program to Create a Balanced Binary Tree of the Incoming Data
ThreadPoolTaskExecutor corePoolSize vs. maxPoolSize
Java Program to Perform the Unique Factorization of a Given Number
New Features in Java 12
Guide to CountDownLatch in Java
ClassNotFoundException vs NoClassDefFoundError
Java Program to Implement RenderingHints API
New in Spring Security OAuth2 – Verify Claims
Guide to DelayQueue
Hướng dẫn Java Design Pattern – Chain of Responsibility
Simple Single Sign-On with Spring Security OAuth2
Tạo số và chuỗi ngẫu nhiên trong Java
Converting Between Byte Arrays and Hexadecimal Strings in Java
Checking for Empty or Blank Strings in Java
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
So sánh ArrayList và Vector trong Java
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
New Features in Java 9
Spring Boot - OAuth2 with JWT
Remove HTML tags from a file to extract only the TEXT
Why String is Immutable in Java?
Java Program to Perform Uniform Binary Search
Java Program to Implement Hopcroft Algorithm
Wrapper Classes in Java
Set Interface trong Java
Versioning a REST API
Java Program to Implement Queue
Java Program to Implement PriorityQueue API
Receive email using IMAP
Introduction to Spring Cloud Stream