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.
/** ** 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:
Extended Euclid Algorithm Test Enter a b of ax + by = gcd(a, b) 120 23 Roots x : -9 y :47
Related posts:
How to Store Duplicate Keys in a Map in Java?
Simultaneous Spring WebClient Calls
An Introduction to ThreadLocal in Java
Java Copy Constructor
Java Program to Implement Borwein Algorithm
Truyền giá trị và tham chiếu trong java
Java Program to Implement LinkedTransferQueue API
Circular Dependencies in Spring
A Guide to EnumMap
Lớp Collectors trong Java 8
Java Program to Implement Triply Linked List
Loại bỏ các phần tử trùng trong một ArrayList như thế nào?
A Quick JUnit vs TestNG Comparison
Jackson Ignore Properties on Marshalling
Spring Security – Reset Your Password
The Thread.join() Method in Java
Map Interface trong java
Java Program to Represent Graph Using Incidence List
Guide to java.util.concurrent.Locks
The Basics of Java Security
Hướng dẫn Java Design Pattern – Adapter
Notify User of Login From New Device or Location
Java Program to Implement Hash Trie
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
A Comparison Between Spring and Spring Boot
Simplify the DAO with Spring and Java Generics
Java Program to Implement Aho-Corasick Algorithm for String Matching
Java Program to Check whether Directed Graph is Connected using DFS
Java Program to Implement Queue using Two Stacks
Java Program to Implement Stein GCD Algorithm
Setting a Request Timeout for a Spring REST API
Serve Static Resources with Spring