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 Find an Element in a List with Java
Exception Handling in Java
Spring Security OAuth Login with WebFlux
Java Program to Perform integer Partition for a Specific Case
A Guide to Spring Cloud Netflix – Hystrix
Guide to Spring Cloud Kubernetes
Hướng dẫn sử dụng Java Annotation
Spring Boot - Sending Email
Comparing Dates in Java
Spring Security – Reset Your Password
Hướng dẫn Java Design Pattern – Singleton
Serialize Only Fields that meet a Custom Criteria with Jackson
Java Program to Implement the String Search Algorithm for Short Text Sizes
Jackson Unmarshalling JSON with Unknown Properties
Giới thiệu HATEOAS
Finding Max/Min of a List or Collection
Introduction to Spring Data MongoDB
Spring Boot - Thymeleaf
How to Read a Large File Efficiently with Java
How to Count Duplicate Elements in Arraylist
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Java Program to Implement Hash Tables
Java Program to Generate Random Numbers Using Multiply with Carry Method
Java Program to Implement Ternary Tree
Registration – Activate a New Account by Email
Java Program to Implement Stack API
Spring Data MongoDB – Indexes, Annotations and Converters
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Spring Data JPA @Modifying Annotation
Hướng dẫn Java Design Pattern – Abstract Factory
Spring Cloud – Tracing Services with Zipkin
Difference Between Wait and Sleep in Java