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)
    {
        GcdValue task = new GcdValue();
        // Formula
        // ax + by = gcd(a,b) 
        // Test Cases
        // a = 15 b = 20 = (5)
        // Here Bezout coefficients : x=-1,y=1
        task.extended_gcd(15, 20);
        // a = 24 b = 75 = (3)
        // Here Bezout coefficients : x=-3,y=1
        task.extended_gcd(24, 75);
        // a = 45 b = 30 = (15)
        // Here Bezout coefficients : x=1,y=-1
        task.extended_gcd(45, 30);
        // a = 21 b = 49 = (7)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(21, 49);
        // a = 16 b = 40 = (8)
        // Here Bezout coefficients : x=-2,y=1
        task.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 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){
    GcdValue task ;
    // Formula
    // ax + by = gcd(a,b)
    // Test Cases
    // a = 15 b = 20 = (5)
    // Here Bezout coefficients : x=-1,y=1
    task.extended_gcd(15, 20);
    // a = 24 b = 75 = (3)
    // Here Bezout coefficients : x=-3,y=1
    task.extended_gcd(24, 75);
    // a = 45 b = 30 = (15)
    // Here Bezout coefficients : x=1,y=-1
    task.extended_gcd(45, 30);
    // a = 21 b = 49 = (7)
    // Here Bezout coefficients : x=-2,y=1
    task.extended_gcd(21, 49);
    // a = 16 b = 40 = (8)
    // Here Bezout coefficients : x=-2,y=1
    task.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 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)
    {
        var task = new GcdValue();
        // Formula
        // ax + by = gcd(a,b)
        // Test Cases
        // a = 15 b = 20 = (5)
        // Here Bezout coefficients : x=-1,y=1
        task.extended_gcd(15, 20);
        // a = 24 b = 75 = (3)
        // Here Bezout coefficients : x=-3,y=1
        task.extended_gcd(24, 75);
        // a = 45 b = 30 = (15)
        // Here Bezout coefficients : x=1,y=-1
        task.extended_gcd(45, 30);
        // a = 21 b = 49 = (7)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(21, 49);
        // a = 16 b = 40 = (8)
        // Here Bezout coefficients : x=-2,y=1
        task.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 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()
    {
        $task = new GcdValue();
        // Formula
        // ax + by = gcd(a,b)
        // Test Cases
        // a = 15 b = 20 = (5)
        // Here Bezout coefficients : x=-1,y=1
        $task->extended_gcd(15, 20);
        // a = 24 b = 75 = (3)
        // Here Bezout coefficients : x=-3,y=1
        $task->extended_gcd(24, 75);
        // a = 45 b = 30 = (15)
        // Here Bezout coefficients : x=1,y=-1
        $task->extended_gcd(45, 30);
        // a = 21 b = 49 = (7)
        // Here Bezout coefficients : x=-2,y=1
        $task->extended_gcd(21, 49);
        // a = 16 b = 40 = (8)
        // Here Bezout coefficients : x=-2,y=1
        $task->extended_gcd(16, 40);
    }
}
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()
{
    var task = new GcdValue();
    // Formula
    // ax + by = gcd(a,b)
    // Test Cases
    // a = 15 b = 20 = (5)
    // Here Bezout coefficients : x=-1,y=1
    task.extended_gcd(15, 20);
    // a = 24 b = 75 = (3)
    // Here Bezout coefficients : x=-3,y=1
    task.extended_gcd(24, 75);
    // a = 45 b = 30 = (15)
    // Here Bezout coefficients : x=1,y=-1
    task.extended_gcd(45, 30);
    // a = 21 b = 49 = (7)
    // Here Bezout coefficients : x=-2,y=1
    task.extended_gcd(21, 49);
    // a = 16 b = 40 = (8)
    // Here Bezout coefficients : x=-2,y=1
    task.extended_gcd(16, 40);
}
// 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()
    {
        var task = new GcdValue();
        // Formula
        // ax + by = gcd(a,b)
        // Test Cases
        // a = 15 b = 20 = (5)
        // Here Bezout coefficients : x=-1,y=1
        task.extended_gcd(15, 20);
        // a = 24 b = 75 = (3)
        // Here Bezout coefficients : x=-3,y=1
        task.extended_gcd(24, 75);
        // a = 45 b = 30 = (15)
        // Here Bezout coefficients : x=1,y=-1
        task.extended_gcd(45, 30);
        // a = 21 b = 49 = (7)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(21, 49);
        // a = 16 b = 40 = (8)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(16, 40);
    }
}
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__":
    task = GcdValue()
    # Formula
    # ax + by = gcd(a,b)
    # Test Cases
    # a = 15 b = 20 = (5)
    # Here Bezout coefficients : x=-1,y=1
    task.extended_gcd(15, 20)
    # a = 24 b = 75 = (3)
    # Here Bezout coefficients : x=-3,y=1
    task.extended_gcd(24, 75)
    # a = 45 b = 30 = (15)
    # Here Bezout coefficients : x=1,y=-1
    task.extended_gcd(45, 30)
    # a = 21 b = 49 = (7)
    # Here Bezout coefficients : x=-2,y=1
    task.extended_gcd(21, 49)
    # a = 16 b = 40 = (8)
    # Here Bezout coefficients : x=-2,y=1
    task.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 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()
        task = GcdValue.new()
        # Formula
        # ax + by = gcd(a,b)
        # Test Cases
        # a = 15 b = 20 = (5)
        # Here Bezout coefficients : x=-1,y=1
        task.extended_gcd(15, 20)
        # a = 24 b = 75 = (3)
        # Here Bezout coefficients : x=-3,y=1
        task.extended_gcd(24, 75)
        # a = 45 b = 30 = (15)
        # Here Bezout coefficients : x=1,y=-1
        task.extended_gcd(45, 30)
        # a = 21 b = 49 = (7)
        # Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(21, 49)
        # a = 16 b = 40 = (8)
        # Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(16, 40)
    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=
    {
        var task = new GcdValue()
        // Formula
        // ax + by = gcd(a,b)
        // Test Cases
        // a = 15 b = 20 = (5)
        // Here Bezout coefficients : x=-1,y=1
        task.extended_gcd(15, 20)
        // a = 24 b = 75 = (3)
        // Here Bezout coefficients : x=-3,y=1
        task.extended_gcd(24, 75)
        // a = 45 b = 30 = (15)
        // Here Bezout coefficients : x=1,y=-1
        task.extended_gcd(45, 30)
        // a = 21 b = 49 = (7)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(21, 49)
        // a = 16 b = 40 = (8)
        // Here Bezout coefficients : x=-2,y=1
        task.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 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
        task.extended_gcd(15,20);
        // a = 24 b = 75 = (3)
        // Here Bezout coefficients : x=-3,y=1
        task.extended_gcd(24,75);
        // a = 45 b = 30 = (15)
        // Here Bezout coefficients : x=1,y=-1
        task.extended_gcd(45,30);
        // a = 21 b = 49 = (7)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(21,49);
        // a = 16 b = 40 = (8)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(16,40);
    }
}
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
        task.extended_gcd(15, 20);
        // a = 24 b = 75 = (3)
        // Here Bezout coefficients : x=-3,y=1
        task.extended_gcd(24, 75);
        // a = 45 b = 30 = (15)
        // Here Bezout coefficients : x=1,y=-1
        task.extended_gcd(45, 30);
        // a = 21 b = 49 = (7)
        // Here Bezout coefficients : x=-2,y=1
        task.extended_gcd(21, 49);
        // a = 16 b = 40 = (8)
        // Here Bezout coefficients : x=-2,y=1
        task.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 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

Standard post




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.

New Comment







© 2022, kalkicode.com, All rights reserved