Tutorialspoint.dev

Euclidean algorithms (Basic and Extended)

GCD of two numbers is the largest number that divides both of them. A simple way to find GCD is to factorize both numbers and multiply common factors.

GCD

Basic Euclidean Algorithm for GCD
The algorithm is based on below facts.

  • If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
  • Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

Below is a recursive function to evaluate gcd using Euclid’s algorithm.

CPP

// C++ program to demonstrate
// Basic Euclidean Algorithm
#include <bits/stdc++.h>
using namespace std;
  
// Function to return 
// gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
  
// Driver Code
int main()
{
    int a = 10, b = 15;
    cout << "GCD(" << a << ", " 
         << b << ") = " << gcd(a, b) 
                        << endl;
    a = 35, b = 10;
    cout << "GCD(" << a << ", " 
         << b << ") = " << gcd(a, b) 
                        << endl;
    a = 31, b = 2;
    cout << "GCD(" << a << ", " 
         << b << ") = " << gcd(a, b) 
                        << endl;
    return 0;
}
  
// This code is contributed 
// by Nimit Garg

C

// C program to demonstrate Basic Euclidean Algorithm
#include <stdio.h>
  
// Function to return gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
  
// Driver program to test above function
int main()
{
    int a = 10, b = 15;
    printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
    a = 35, b = 10;
    printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
    a = 31, b = 2;
    printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
    return 0;
}

Java

// Java program to demonstrate working of extended
// Euclidean Algorithm
  
import java.util.*;
import java.lang.*;
  
class GFG
{
    // extended Euclidean Algorithm
    public static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
          
        return gcd(b%a, a);
    }
  
// Driver Program
    public static void main(String[] args)
    {
        int a = 10, b = 15, g;
        g = gcd(a, b);
        System.out.println("GCD(" + a +  " , " + b+ ") = " + g);
          
        a = 35; b = 10;
        g = gcd(a, b);
        System.out.println("GCD(" + a +  " , " + b+ ") = " + g);
          
        a = 31; b = 2;
        g = gcd(a, b);
        System.out.println("GCD(" + a +  " , " + b+ ") = " + g);
  
    }
}
// Code Contributed by Mohit Gupta_OMG <(0_o)>

Python3

# Python program to demonstrate Basic Euclidean Algorithm
  
  
# Function to return gcd of a and b
def gcd(a, b): 
    if a == 0 :
        return
      
    return gcd(b%a, a)
  
a = 10
b = 15
print("gcd(", a , "," , b, ") = ", gcd(a, b))
  
a = 35
b = 10
print("gcd(", a , "," , b, ") = ", gcd(a, b))
  
a = 31
b = 2
print("gcd(", a , "," , b, ") = ", gcd(a, b))
  
# Code Contributed By Mohit Gupta_OMG <(0_o)>

C#

using System;
  
class GFG
{
    public static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
          
        return gcd(b % a, a);
    }
      
    // Driver Code
    static public void Main ()
    {
        int a = 10, b = 15, g;
        g = gcd(a, b);
        Console.WriteLine("GCD(" + a + 
              " , " + b + ") = " + g);
          
        a = 35; b = 10;
        g = gcd(a, b);
        Console.WriteLine("GCD(" + a + 
              " , " + b + ") = " + g);
          
        a = 31; b = 2;
        g = gcd(a, b);
        Console.WriteLine("GCD(" + a + 
              " , " + b + ") = " + g);
    }
}
  
// This code is contributed by ajit

PHP

<?php
// PHP program to demonstrate
// Basic Euclidean Algorithm
  
// Function to return
// gcd of a and b
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
    return gcd($b % $a, $a);
}
  
// Driver Code
$a = 10; $b = 15;
echo "GCD(",$a,"," , $b,") = "
                   gcd($a, $b);
echo " ";
$a = 35; $b = 10;
echo "GCD(",$a ,",",$b,") = "
                  gcd($a, $b);
echo " ";
$a = 31; $b = 2;
echo "GCD(",$a ,",", $b,") = "
                   gcd($a, $b);
  
// This code is contributed by m_kit
?>


Output :



GCD(10, 15) = 5
GCD(35, 10) = 5
GCD(31, 2) = 1

Time Complexity: O(Log min(a, b))

 
Extended Euclidean Algorithm:
Extended Euclidean algorithm also finds integer coefficients x and y such that:

  ax + by = gcd(a, b) 

Examples:

Input: a = 30, b = 20
Output: gcd = 10
        x = 1, y = -1
(Note that 30*1 + 20*(-1) = 10)

Input: a = 35, b = 15
Output: gcd = 5
        x = 1, y = -2
(Note that 10*0 + 5*1 = 5)

The extended Euclidean algorithm updates results of gcd(a, b) using the results calculated by recursive call gcd(b%a, a). Let values of x and y calculated by the recursive call be x1 and y1. x and y are updated using below expressions.

x = y1 - ⌊b/a⌋ * x1
y = x1


Below is implementation based on above formulas.

C

// C program to demonstrate working of extended
// Euclidean Algorithm
#include <stdio.h>
  
// C function for extended Euclidean Algorithm
int gcdExtended(int a, int b, int *x, int *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0;
        *y = 1;
        return b;
    }
  
    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b%a, a, &x1, &y1);
  
    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;
  
    return gcd;
}
  
// Driver Program
int main()
{
    int x, y;
    int a = 35, b = 15;
    int g = gcdExtended(a, b, &x, &y);
    printf("gcd(%d, %d) = %d", a, b, g);
    return 0;
}

Java

// Java program to demonstrate working of extended
// Euclidean Algorithm
  
import java.util.*;
import java.lang.*;
  
class GFG
{
    // extended Euclidean Algorithm
    public static int gcdExtended(int a, int b, int x, int y)
    {
        // Base Case
        if (a == 0)
        {
            x = 0;
            y = 1;
            return b;
        }
  
        int x1=1, y1=1; // To store results of recursive call
        int gcd = gcdExtended(b%a, a, x1, y1);
  
        // Update x and y using results of recursive
        // call
        x = y1 - (b/a) * x1;
        y = x1;
  
        return gcd;
    }
  
// Driver Program
    public static void main(String[] args)
    {
        int x=1, y=1;
        int a = 35, b = 15;
        int g = gcdExtended(a, b, x, y);
        System.out.print("gcd(" + a +  " , " + b+ ") = " + g);
  
    }
}
// Code Contributed by Mohit Gupta_OMG <(0-o)>

Python3

# Python program to demonstrate working of extended
# Euclidean Algorithm
  
# function for extended Euclidean Algorithm
def gcdExtended(a, b, x, y):
    # Base Case
    if a == 0
        x = 0
        y = 1
        return b
          
    x1 = 1
    y1 = 1 # To store results of recursive call
    gcd = gcdExtended(b%a, a, x1, y1)
  
    # Update x and y using results of recursive
    # call
    x = y1 - (b/a) * x1
    y = x1
  
    return gcd
  
  
x = 1
y = 1
a = 35
b = 15
g = gcdExtended(a, b, x, y)
print("gcd(", a , "," , b, ") = ", g)
  
# Code Contributed by Mohit Gupta_OMG <(0_o)>

C#

// C# program to demonstrate working 
// of extended Euclidean Algorithm
using System;
  
class GFG
{
      
    // extended Euclidean Algorithm
    public static int gcdExtended(int a, int b, 
                                  int x, int y)
    {
        // Base Case
        if (a == 0)
        {
            x = 0;
            y = 1;
            return b;
        }
  
        // To store results of
        // recursive call
        int x1 = 1, y1 = 1; 
        int gcd = gcdExtended(b % a, a, x1, y1);
  
        // Update x and y using 
        // results of recursive call
        x = y1 - (b / a) * x1;
        y = x1;
  
        return gcd;
    }
      
    // Driver Code
    static public void Main ()
    {
        int x = 1, y = 1;
        int a = 35, b = 15;
        int g = gcdExtended(a, b, x, y);
        Console.WriteLine("gcd(" + a + " , "
                              b + ") = " + g);
    }
}
  
// This code is contributed by m_kit

PHP

<?php
// PHP program to demonstrate 
// working of extended 
// Euclidean Algorithm
  
// PHP function for 
// extended Euclidean 
// Algorithm
function gcdExtended($a, $b,    
                     $x, $y)
{
    // Base Case
    if ($a == 0)
    {
        $x = 0;
        $y = 1;
        return $b;
    }
  
    // To store results 
    // of recursive call
    $gcd = gcdExtended($b % $a
                       $a, $x, $y);
  
    // Update x and y using
    // results of recursive
    // call
    $x = $y - ($b / $a) * $x;
    $y = $x;
  
    return $gcd;
}
  
// Driver Code
$x = 0;
$y = 0;
$a = 35; $b = 15;
$g = gcdExtended($a, $b, $x, $y);
echo "gcd(",$a;
echo ", " , $b, ")";
echo " = " , $g;
  
// This code is contributed by ajit
?>


Output :

gcd(35, 15) = 5

 
How does Extended Algorithm Work?

As seen above, x and y are results for inputs a and b,
   a.x + b.y = gcd                      ----(1)  

And x1 and y1 are results for inputs b%a and a
   (b%a).x1 + a.y1 = gcd   
                    
When we put b%a = (b - (⌊b/a⌋).a) in above, 
we get following. Note that ⌊b/a⌋ is floor(a/b)

   (b - (⌊b/a⌋).a).x1 + a.y1  = gcd

Above equation can also be written as below
   b.x1 + a.(y1 - (⌊b/a⌋).x1) = gcd      ---(2)

After comparing coefficients of 'a' and 'b' in (1) and 
(2), we get following
   x = y1 - ⌊b/a⌋ * x1
   y = x1

 
How is Extended Algorithm Useful?
The extended Euclidean algorithm is particularly useful when a and b are coprime (or gcd is 1). Since x is the modular multiplicative inverse of “a modulo b”, and y is the modular multiplicative inverse of “b modulo a”. In particular, the computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method.

References:
http://e-maxx.ru/algo/extended_euclid_algorithm
http://en.wikipedia.org/wiki/Euclidean_algorithm
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm



This article is attributed to GeeksforGeeks.org

leave a comment

code

1 Comments

load comments

Subscribe to Our Newsletter