# Extended euclidean algorithm implementation

The extended Euclidean algorithm is an extension of the Euclidean method in arithmetic and computer programming that computes, in addition to the greatest common divisor (gcd) of integers a and b, the coefficients of Bézout's identity, which are integers x and y such that.

``ax + by = gcd(a,b)``

We are given input a and b and our goal is to find gcd and Bezout coefficients (x,y).

## Extended euclidean algorithm implementation in java

``````/*
Java program for
Extended euclidean algorithm implementation
*/
public class GcdValue
{
// Find GCD of given two given number
public void extended_gcd(int a, int b)
{
// Declare some auxiliary variable
int s = 0;
int r = b;
int old_s = 1;
int old_r = a;
int temp = 0;
int bezout_t = 0;
// When r not equal to zero
while (r != 0)
{
int quotient = old_r / r;
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = (old_r - old_s * a) / b;
}
// Display given number
System.out.println("\nGiven (a,b) : " + a + "," + b);
// Displaying the value calculate result
System.out.println("Bezout coefficients : " + old_s + "," + bezout_t);
System.out.println("greatest common divisor : " + old_r);
}
public static void main(String[] args)
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}
}``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in c++

``````// Include header file
#include <iostream>
//  Stdc++11 program for
//  Extended euclidean algorithm implementation
class GcdValue
{
// Find GCD of given two given number
public:
void extended_gcd(int a, int b)
{
// Declare some auxiliary variable
int s = 0;
int r = b;
int old_s = 1;
int old_r = a;
int temp = 0;
int bezout_t = 0;
// When r not equal to zero
while (r != 0)
{
int quotient = old_r / r;
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = (old_r - old_s * a) / b;
}
// Display given number
std::cout << "\nGiven (a,b) : " << a
<<"," << b << std::endl;
// Displaying the value calculate result
std::cout << "Bezout coefficients : "
<< old_s << ","
<< bezout_t
<< std::endl;
std::cout << "greatest common divisor : "
<< old_r << std::endl;
}
};
int main(int argc, char **argv){
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
return 0;
};``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in c

``````// Include header file
#include <stdio.h>
//  C program for
//  Extended euclidean algorithm implementation

// Find GCD of given two given number
void  extended_gcd (int a, int b)
{
// Declare some auxiliary variable
int s = 0;
int r = b;
int old_s = 1;
int old_r = a;
int temp = 0;
int bezout_t = 0;
// When r not equal to zero
while(r != 0)
{
int quotient = old_r / r;
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = (old_r - old_s * a) / b;
}
// Display given number
printf("Given (a,b) : %d,%d\n" , a , b);
// Displaying the value calculate result
printf("Bezout coefficients : %d,%d\n\n" ,
old_s, bezout_t);
printf("greatest common divisor : %d\n\n" , old_r);
}

int main()
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
extended_gcd(15, 20);
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
extended_gcd(24, 75);
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
extended_gcd(45, 30);
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
extended_gcd(21, 49);
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
extended_gcd(16, 40);
return 0;
}``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8
``````

## Extended euclidean algorithm implementation in golang

``````package main
import "fmt"

//  Go lang program for
//  Extended euclidean algorithm implementation

// Find GCD of given two given number
func extended_gcd( a  int,  b  int) {
// Declare some auxiliary variable
var  s  int = 0;
var  r  int = b;
var  old_s  int = 1;
var  old_r  int = a;
var  temp  int = 0;
var  bezout_t  int = 0;
// When r not equal to zero
for(r != 0) {
var  quotient  int = old_r / r;
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0) {
bezout_t = (old_r - old_s * a) / b;
}
// Display given number
fmt.Println("\nGiven (a,b) : " ,a,",",b);
// Displaying the value calculate result
fmt.Println("Bezout coefficients : " ,old_s,"," ,bezout_t);
fmt.Println("greatest common divisor : " ,old_r);
}
func main() {
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
extended_gcd(15, 20);
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
extended_gcd(24, 75);
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
extended_gcd(45, 30);
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
extended_gcd(21, 49);
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
extended_gcd(16, 40);
}
``````
Output
``````Given (a,b) :  15 , 20
Bezout coefficients :  -1 , 1
greatest common divisor :  5

Given (a,b) :  24 , 75
Bezout coefficients :  -3 , 1
greatest common divisor :  3

Given (a,b) :  45 , 30
Bezout coefficients :  1 , -1
greatest common divisor :  15

Given (a,b) :  21 , 49
Bezout coefficients :  -2 , 1
greatest common divisor :  7

Given (a,b) :  16 , 40
Bezout coefficients :  -2 , 1
greatest common divisor :  8``````

## Extended euclidean algorithm implementation in c#

``````// Include namespace system
using System;
//  C# program for
//  Extended euclidean algorithm implementation
public class GcdValue
{
// Find GCD of given two given number
public void extended_gcd(int a, int b)
{
// Declare some auxiliary variable
var s = 0;
var r = b;
var old_s = 1;
var old_r = a;
var temp = 0;
var bezout_t = 0;
// When r not equal to zero
while (r != 0)
{
var quotient = (int)(old_r / r);
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = (int)((old_r - old_s * a) / b);
}
// Display given number
Console.WriteLine("\nGiven (a,b) : " + a + "," + b);
// Displaying the value calculate result
Console.WriteLine("Bezout coefficients : " + old_s + "," + bezout_t);
Console.WriteLine("greatest common divisor : " + old_r);
}
public static void Main(String[] args)
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}
}``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in php

``````<?php
//  Php program for
//  Extended euclidean algorithm implementation
class GcdValue
{
// Find GCD of given two given number
function extended_gcd(\$a, \$b)
{
// Declare some auxiliary variable
\$s = 0;
\$r = \$b;
\$old_s = 1;
\$old_r = \$a;
\$temp = 0;
\$bezout_t = 0;
// When r not equal to zero
while (\$r != 0)
{
\$quotient = (int)(\$old_r / \$r);
\$temp = \$r;
\$r = \$old_r - \$quotient * \$r;
\$old_r = \$temp;
\$temp = \$s;
\$s = \$old_s - \$quotient * \$s;
\$old_s = \$temp;
}
if (\$b != 0)
{
\$bezout_t = (int)((\$old_r - \$old_s * \$a) / \$b);
}
// Display given number
echo "\nGiven (a,b) : \$a,\$b\n";
// Displaying the value calculate result
echo "Bezout coefficients : \$old_s,\$bezout_t\n";
echo "greatest common divisor : \$old_r\n";
}
function main()
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}
}
GcdValue::main();``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8
``````

## Extended euclidean algorithm implementation in node js

``````//  Node Js program for
//  Extended euclidean algorithm implementation
class GcdValue
{
// Find GCD of given two given number
extended_gcd(a, b)
{
// Declare some auxiliary variable
var s = 0;
var r = b;
var old_s = 1;
var old_r = a;
var temp = 0;
var bezout_t = 0;
// When r not equal to zero
while (r != 0)
{
var quotient = parseInt(old_r / r);
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = parseInt((old_r - old_s * a) / b);
}
// Display given number
console.log("\nGiven (a,b) : " + a + "," + b);
// Displaying the value calculate result
console.log("Bezout coefficients : " + old_s + "," + bezout_t);
console.log("greatest common divisor : " + old_r);
}
}
function main()
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}
// Start program execution
main();``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in typescript

``````//  Typescript program for
//  Extended euclidean algorithm implementation
class GcdValue
{
// Find GCD of given two given number
public  extended_gcd(a:number, b:number)
{
// Declare some auxiliary variable
var s = 0;
var r = b;
var old_s = 1;
var old_r = a;
var temp = 0;
var bezout_t = 0;
// When r not equal to zero
while (r != 0)
{
var quotient = parseInt(old_r / r);
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = parseInt((old_r - old_s * a) / b);
}
// Display given number
console.log("\nGiven (a,b) : " + a + "," + b);
// Displaying the value calculate result
console.log("Bezout coefficients : " + old_s + "," + bezout_t);
console.log("greatest common divisor : " + old_r);
}
public static  main()
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}
}
GcdValue.main();
/*
file : code.ts
tsc --target es6 code.ts
node code.js
*/``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in python

``````#  Python 3 program for
#  Extended euclidean algorithm implementation
class GcdValue :
# Find GCD of given two given number
def extended_gcd(self, a,  b) :
# Declare some auxiliary variable
s = 0
r = b
old_s = 1
old_r = a
temp = 0
bezout_t = 0
# When r not equal to zero
while (r != 0) :
quotient = int(old_r / r)
temp = r
r = old_r - quotient * r
old_r = temp
temp = s
s = old_s - quotient * s
old_s = temp
if (b != 0) :
bezout_t = int((old_r - old_s * a) / b)
# Display given number
print("\nGiven (a,b) :",a,",",b)
# Displaying the value calculate result
print("Bezout coefficients :",old_s,",",bezout_t)
print("greatest common divisor :",old_r)

if __name__=="__main__":
# Formula
# ax + by = gcd(a,b)
# Test Cases
# a = 15 b = 20 = (5)
# Here Bezout coefficients : x=-1,y=1
# a = 24 b = 75 = (3)
# Here Bezout coefficients : x=-3,y=1
# a = 45 b = 30 = (15)
# Here Bezout coefficients : x=1,y=-1
# a = 21 b = 49 = (7)
# Here Bezout coefficients : x=-2,y=1
# a = 16 b = 40 = (8)
# Here Bezout coefficients : x=-2,y=1
Output
``````Given (a,b) : 15 , 20
Bezout coefficients : -1 , 1
greatest common divisor : 5

Given (a,b) : 24 , 75
Bezout coefficients : -3 , 1
greatest common divisor : 3

Given (a,b) : 45 , 30
Bezout coefficients : 1 , -1
greatest common divisor : 15

Given (a,b) : 21 , 49
Bezout coefficients : -2 , 1
greatest common divisor : 7

Given (a,b) : 16 , 40
Bezout coefficients : -2 , 1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in ruby

``````#  Ruby program for
#  Extended euclidean algorithm implementation
class GcdValue
# Find GCD of given two given number
def extended_gcd( a,  b)
# Declare some auxiliary variable
s = 0
r = b
old_s = 1
old_r = a
temp = 0
bezout_t = 0
# When r not equal to zero
while (r != 0)
quotient = old_r / r
temp = r
r = old_r - quotient * r
old_r = temp
temp = s
s = old_s - quotient * s
old_s = temp
end
if (b != 0)
bezout_t = (old_r - old_s * a) / b
end
# Display given number
print("\nGiven (a,b) : ",a,",", b,"\n")
# Displaying the value calculate result
print("Bezout coefficients : ",old_s, "," , bezout_t,"\n")
print("greatest common divisor : ",old_r,"\n")
end
def self.main()
# Formula
# ax + by = gcd(a,b)
# Test Cases
# a = 15 b = 20 = (5)
# Here Bezout coefficients : x=-1,y=1
# a = 24 b = 75 = (3)
# Here Bezout coefficients : x=-3,y=1
# a = 45 b = 30 = (15)
# Here Bezout coefficients : x=1,y=-1
# a = 21 b = 49 = (7)
# Here Bezout coefficients : x=-2,y=1
# a = 16 b = 40 = (8)
# Here Bezout coefficients : x=-2,y=1
end
end
GcdValue.main()``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8
``````

## Extended euclidean algorithm implementation in scala

``````//  Scala program for
//  Extended euclidean algorithm implementation
class GcdValue ()
{
// Find GCD of given two given number
def extended_gcd(a : Int, b : Int) : Unit=
{
// Declare some auxiliary variable
var s = 0
var r = b
var old_s = 1
var old_r = a
var temp = 0
var bezout_t = 0
// When r not equal to zero
while (r != 0)
{
var quotient = old_r / r
temp = r
r = old_r - quotient * r
old_r = temp
temp = s
s = old_s - quotient * s
old_s = temp
}
if (b != 0)
{
bezout_t = (old_r - old_s * a) / b
}
// Display given number
println("\nGiven (a,b) : " + a + "," + b)
// Displaying the value calculate result
println("Bezout coefficients : " + old_s + "," + bezout_t)
println("greatest common divisor : " + old_r)
}
}

object Main
{
def main(args : Array[String]) : Unit=
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}
}``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in swift

``````import Foundation
//  Swift program for
//  Extended euclidean algorithm implementation
class GcdValue
{
// Find GCD of given two given number
func extended_gcd(_ a : Int, _ b : Int)
{
// Declare some auxiliary variable
var s : Int = 0;
var r : Int = b;
var old_s : Int = 1;
var old_r : Int = a;
var temp : Int = 0;
var bezout_t : Int = 0;
// When r not equal to zero
while (r != 0)
{
let quotient : Int = old_r / r;
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = (old_r - old_s * a) / b;
}
// Display given number
print("\nGiven (a,b) : ",a,",",b);
// Displaying the value calculate result
print("Bezout coefficients :",old_s,"," ,bezout_t);
print("greatest common divisor :",old_r);
}
static func main()
{
let task : GcdValue = GcdValue();
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}
}
GcdValue.main();``````
Output
``````Given (a,b) :  15 , 20
Bezout coefficients : -1 , 1
greatest common divisor : 5

Given (a,b) :  24 , 75
Bezout coefficients : -3 , 1
greatest common divisor : 3

Given (a,b) :  45 , 30
Bezout coefficients : 1 , -1
greatest common divisor : 15

Given (a,b) :  21 , 49
Bezout coefficients : -2 , 1
greatest common divisor : 7

Given (a,b) :  16 , 40
Bezout coefficients : -2 , 1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in kotlin

``````//  Kotlin program for
//  Extended euclidean algorithm implementation
class GcdValue {
// Find GCD of given two given number
fun extended_gcd(a : Int, b : Int) : Unit
{
// Declare some auxiliary variable
var s : Int = 0;
var r : Int = b;
var old_s : Int = 1;
var old_r : Int = a;
var temp : Int ;
var bezout_t : Int = 0;
// When r not equal to zero
while (r != 0)
{
val quotient : Int = old_r / r;
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if (b != 0)
{
bezout_t = (old_r - old_s * a) / b;
}
// Display given number
java.lang.System.out.println("\nGiven (a,b) : " + a.toString() + "," + b.toString());
// Displaying the value calculate result
java.lang.System.out.println("Bezout coefficients : " + old_s.toString() + "," + bezout_t.toString());
java.lang.System.out.println("greatest common divisor : " + old_r.toString());
}
}
fun main(args : Array<String>) : Unit
{
val task : GcdValue = GcdValue();
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
}``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Extended euclidean algorithm implementation in rust

``````/*
Rust program for
Extended euclidean algorithm implementation
*/
fn main()
{
// Formula
// ax + by = gcd(a,b)
// Test Cases
// a = 15 b = 20 = (5)
// Here Bezout coefficients : x=-1,y=1
extended_gcd(15, 20);
// a = 24 b = 75 = (3)
// Here Bezout coefficients : x=-3,y=1
extended_gcd(24, 75);
// a = 45 b = 30 = (15)
// Here Bezout coefficients : x=1,y=-1
extended_gcd(45, 30);
// a = 21 b = 49 = (7)
// Here Bezout coefficients : x=-2,y=1
extended_gcd(21, 49);
// a = 16 b = 40 = (8)
// Here Bezout coefficients : x=-2,y=1
extended_gcd(16, 40);
}

// Find GCD of given two given number
fn extended_gcd(a: i32, b: i32)
{
// Declare some auxiliary variable
let mut s: i32 = 0;
let mut r: i32 = b;
let mut old_s: i32 = 1;
let mut old_r: i32 = a;
let mut temp: i32 ;
let mut bezout_t: i32 = 0;
// When r not equal to zero
while r != 0
{
let quotient: i32 = old_r / r;
temp = r;
r = old_r - quotient * r;
old_r = temp;
temp = s;
s = old_s - quotient * s;
old_s = temp;
}
if b != 0
{
bezout_t = (old_r - old_s * a) / b;
}
// Display given number
println!("\nGiven (a,b) : {},{}",  a , b);
// Displaying the value calculate result
println!("Bezout coefficients : {},{}",old_s , bezout_t);
println!("greatest common divisor : {}", old_r);
}``````
Output
``````Given (a,b) : 15,20
Bezout coefficients : -1,1
greatest common divisor : 5

Given (a,b) : 24,75
Bezout coefficients : -3,1
greatest common divisor : 3

Given (a,b) : 45,30
Bezout coefficients : 1,-1
greatest common divisor : 15

Given (a,b) : 21,49
Bezout coefficients : -2,1
greatest common divisor : 7

Given (a,b) : 16,40
Bezout coefficients : -2,1
greatest common divisor : 8``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.