Code


Here you will find C++ and Python example codes for the Euclidean Algorithm, Extended Euclidean Algorithm and Multiplicative Inverse. To see the entire script with everything in it, go to the bottom of this page.

WARNING: prevent fraud when copying these codes


If you are using and/or copying any of the codes below, make sure you keep the reference to this website inside the code. Even if you edit the code or translate it to another programming language, do not get rid of the link to this webpage inside the code. If you don't and pretend you came up with this code, you are comitting fraud. Nobody likes fraudsters, that includes the person who is grading your homework. (If you think you changed the code so much that it is actually different than the original code you used from this page, then you can change the word "Source: " to something like "Inspired by: " or "Based on: ".)

Table of contents

Things to note before reading the codes



Euclidean Algorithm (non-recursive)


We start with the non-recursive version of the algorithm.

def gcd_nonrecursive(a, b):
	""" Calculating the greatest common divisor 
	using the Euclidean Algorithm (non-recursive) 
	(Source: extendedeuclideanalgorithm.com/code) 
	"""
  
	#Set default values for the quotient and the remainder
	q = 0
	r = 1
	
	'''
	In each iteration of the loop below, we
	calculate the new quotient, remainder, a and b.
	r decreases, so we stop when r = 0 
	'''
	while(r > 0):
		#The calculations
		q = math.floor(a/b)
		r = a - q * b
		
		#The values for the next iteration
		a = b
		b = r if (r > 0) else b
	
	return abs(b)
/* Calculating the greatest common divisor 
using the Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int gcd_nonrecursive(int a, int b){
	//Set default values for the quotient and the remainder
	int q = 0;
	int r = 1;
	
	/*In each iteration of the loop below, we
	calculate the new quotient, remainder, a and b.
	r decreases, so we stop when r = 0*/
	while(r > 0){
		//The calculations
		q = floor(a/b);
		r = a - q * b;
		
		//The values for the next iteration
		a = b;
		b = (r > 0)? r : b;
	}
	return abs(b);
}

You see that q is the quotient and r is the remainder. And abs(b) is absolute value of b.
Each iteration of the while loop represents one line in the table that you construct when using the Euclidean Algorithm.
The last line inside the while loop may confuse you: we're saying a = b, so why don't we just say b = r?
Remember that we are done when r=0. But after r becomes 0, we're still assigning new values to a and b. But we want to return the b that we found at the moment that r=0, so we should not assign a new value to b after that point.
Therefore we only say that b=r if r > 0. So if r=0, then b=b, such that we can return that value after the loop.

Euclidean Algorithm (recursive)

Now that you understand what is going on, we'll show that we can actually do this a lot shorter:

def gcd(a, b):
	""" Calculating the greatest common divisor 
	using the Euclidean Algorithm (recursive) 
	(Source: extendedeuclideanalgorithm.com/code)
	"""
	q = math.floor(a/b)
	r = a - q * b
	return abs(b) if (r == 0) else gcd(b, r)
/* Calculating the greatest common divisor 
using the Euclidean Algorithm (recursive) 
(Source: extendedeuclideanalgorithm.com/code) */
int gcd(int a, int b){
	int q = floor(a/b);
	int r = a - q * b;
	return (r == 0)? abs(b) : gcd(b, r);
}

This piece of code does as exactly the same as the previous code.
As we know from this page, one important property of the Euclidean Algorithm is that gcd(a, b) = gcd(b, r). So if we want to calculate gcd(a, b), we can do that by calculating gcd(b, r). Therefore this algorithm is calling itself with the arguments b and r. So those will be the next a and b when this function executes itself. Note that calling itself with arguments b and r is the same as saying a = b and b = r and then starting a new iteration of the while loop as we did before. But we're done when r=0. Then the absolute value of b is our new gcd. So if that's the case, it should not call itself but return abs(b) instead.


Extended Euclidean Algorithm (non-recursive)


It's easier to understand the code below if you've already looked at the non-recursive code for the Euclidean Algorithm. This is basically the same, with some extra lines added:

def xgcd_nonrecursive(a, b):
	""" Calculates the gcd and Bezout coefficients, 
	using the Extended Euclidean Algorithm (non-recursive).
	(Source: extendedeuclideanalgorithm.com/code) 
	"""
	#Set default values for the quotient, remainder, 
	#s-variables and t-variables
	q = 0
	r = 1
	s1 = 1 
	s2 = 0
	s3 = 1 
	t1 = 0 
	t2 = 1
	t3 = 0
	
	'''
	In each iteration of the loop below, we
	calculate the new quotient, remainder, a, b,
	and the new s-variables and t-variables.
	r decreases, so we stop when r = 0
	'''
	while(r > 0):
		#The calculations
		q = math.floor(a/b)
		r = a - q * b
		s3 = s1 - q * s2
		t3 = t1 - q * t2
		
		'''
		The values for the next iteration, 
		(but only if there is a next iteration)
		'''
		if(r > 0):
			a = b
			b = r
			s1 = s2
			s2 = s3
			t1 = t2
			t2 = t3

	return abs(b), s2, t2

//Global variables used by the Extended Euclidean Algorithm
int s = 0;
int t = 0;

/* Calculates the gcd and Bézout coefficients, 
using the Extended Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd_nonrecursive(int a, int b){
	//Set default values for the quotient, remainder, 
	//s-variables and t-variables
	int q = 0;
	int r = 1;
	int s1 = 1; 
	int s2 = 0;
	int s3 = 1; 
	int t1 = 0; 
	int t2 = 1;
	int t3 = 0;
	
	/*In each iteration of the loop below, we
	calculate the new quotient, remainder, a, b,
	and the new s-variables and t-variables.
	r decreases, so we stop when r = 0*/
	while(r > 0){
		//The calculations
		q = floor(a/b);
		r = a - q * b;
		s3 = s1 - q * s2;
		t3 = t1 - q * t2;
		
		/* The values for the next iteration, 
		(but only if there is a next iteration)*/
		if(r > 0){
			a = b;
			b = r;
			s1 = s2;
			s2 = s3;
			t1 = t2;
			t2 = t3;
		}
	}
	s = s2;
	t = t2;
	return abs(b);
}

We have added the lines for the s-variables and the t-variables before the while loop. Inside the while loop, we have added the calculations for s3 and t3 to the calculations. And below that, we're also assigning new values to the s-variables and t-variables. Remember that the Extended Euclidean Algorithm does not only compute the gcd of a and b, but also s and t such that a*s+t*b=gcd(a,b).
For the Python code, we return s, t and the absolute value of b.
In C++, you can't return multiple variables, so we make global variables of s and t. So after executing this function, you can call the global variables s and t inside your main function to retrieve those values.

Small modifications that you could apply to this piece of code
For the part where we set the values for the next iteration of the while loop, you might wonder why we don't use any ternary expressions anymore. Instead of using the if-statement, you could use ternary expressions for b, s2 and s3 to only assign them a new value if r > 0 (like we did before with b). But since there are three statements now that require a check to see whether r > 0, we decided to use an if-statement here. You could also take the lines a = b;, s1 = s2; and t1 = t2 out of the if-statement and place them above the if-statement. A third way is placing all statements that are currently inside the if-statement below the if-statement and then only put break; inside the if-statement. If you're doing that, you might as well change the while-condition r > 0 into true, since the if statement with the break; now decides when to stop the while loop.)


Extended Euclidean Algorithm (recursive)


This is the same as the recursive code for the Euclidean Algorithm, but with some extra lines. Again, you'll notice that this piece of code is a lot shorter than the non-recusive version.

def xgcd(a, b, s1 = 1, s2 = 0, t1 = 0, t2 = 1):
	""" Calculates the gcd and Bezout coefficients, 
	using the Extended Euclidean Algorithm (recursive).
	(Source: extendedeuclideanalgorithm.com/code) 
	"""
	q = math.floor(a/b)
	r = a - q * b
	s3 = s1 - q * s2
	t3 = t1 - q * t2
	
	#if r==0, then b will be the gcd and s2, t2 the Bezout coefficients
	return (b, s2, t2) if (r == 0) else xgcd(b, r, s2, s3, t2, t3)
(Note that Bézout is actually written with an é (not an e), but some compilers can't handle that character)
//Global variables used by the Extended Euclidean Algorithm
int s = 0;
int t = 0;

/* Calculates the gcd and Bézout coefficients, 
using the Extended Euclidean Algorithm (recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1){
	int q = floor(a/b);
	int r = a - q * b;
	int s3 = s1 - q * s2;
	int t3 = t1 - q * t2;
	
	s = s2;
	t = t2;
	
	return (r == 0)? abs(b) : xgcd(b, r, s2, s3, t2, t3);
}

Just like in the non-recursive version, notice that the Python code returns multiple variables, whereas the C++ code uses global variables that you can call from your main function.


Calculating the Multiplicative Inverse


We have seen before that when using the Extended Euclidean Algorithm to calculate the multiplicative inverse, we don't need the s-columns. So we could create another xgcd function and then just remove the lines for the s-columns. However, we already have the xgcd function that uses the Extended Euclidean Algorithm, so let's use that. (That's the code above, from the previous paragraph.)

def multinv(b, n):
   """
   Calculates the multiplicative inverse of a number b mod n,
   using the Extended Euclidean Algorithm. If b does not have a
   multiplicative inverse mod n, then throw an exception.
   (Source: extendedeuclideanalgorithm.com/code)
   """
   
   #Get the gcd and the second Bezout coefficient (t)
   #from the Extended Euclidean Algorithm. (We don't need s)
   my_gcd, _, t = xgcd(n, b)
   
   #It only has a multiplicative inverse if the gcd is 1
   if(my_gcd == 1):
      return t % n
   else:
      raise ValueError('{} has no multiplicative inverse modulo {}'.format(b, n))
(Note that Bézout is actually written with an é (not an e), but some compilers can't handle that character)
/* Calculates the multiplicative inverse of a number b mod n,
using the Extended Euclidean Algorithm. If b does not have a
multiplicative inverse mod n, then throw an exception.
(Source: extendedeuclideanalgorithm.com/code) */
int multinv(int b, int n){
	if(xgcd(n, b) == 1){
		//t is a global variable that is assigned a value by xgcd
		return (t + n) % n;
	}
	else{
		throw -1;
	}
}
((t + n) % n; actually just means t mod n. But not all compilers do this correctly with negative numbers if you use t %n. Hence we use (t + n) % n;)

So this function calculates the multiplicative inverse of b mod n, where n is the modulus and b just a number.
You call this function inside your main function with multinv(b, n), but note that this function will call xgcd with n as the first argument and b as the second argument (so they are swapped).
Remember that we can only calculate the multiplicative inverse of b mod n, if the gcd of n and b is exactly 1. If that's the case, then t mod n is our multiplicative inverse, with t being the global variable that was assigned a value by the xgcd function.
For the C++ code:
Then why do we return (t + n) mod n instead of just t mod n ? This is a dirty fix for the cases where t is a negative number. The mod operator of C++ doesn't handle that well.

If the gcd of n and b does not equal 1, it means b does not have a multiplicative inverse modulo n. But if we ask this multinv function to calculate a multiplicative inverse, we expect it to return a multiplicative inverse. So if that's not possible, something went different than we expect. You might say that something went wrong. That's why we raise(Python)/throw(C++) an exception when there is no multiplicative inverse.
You can catch this exception, to prevent your program from crashing.
Here is an example where we call multinv to try to calculate the multiplicative inverse of 15 mod 10.
Spoiler alert: it doesn't have a multiplicative inverse.

b = 10
n = 15

'''
Multiplicative Inverse:
Try to compute the multiplicative inverse of b mod n.
If that succeeds, verify that it's correct.
If it doesn't succeed, show the error raised by the function.
'''

print('Multiplicative inverse:')
try:
  inverse = multinv(b, n);
  print("We discovered that the multiplicative inverse of",
  b, "mod", n, "equals", inverse)
  verification = (inverse * b % n == 1)
  if(verification):
        print("And indeed,", b, "*", inverse, "mod", n, "= 1")
  else:
        print("This is not correct.")    
except ValueError as error:
  print(error)
int main(int argc, char** argv) {
	int b = 15;
	int n = 10;
	
	try {
      	  	cout << multinv(b, n) << endl;
  	}
  	catch (int n) {
      	  	cout << "Error: there is no multiplicative inverse for the given numbers" << endl;
  	}

	return 0;
}

So what happens if we execute this code?
We try to calculate the multiplicative inverse. An exception will occur, since 15 mod 10 does not have a multiplicative inverse.
The exception will occur during the calculation of multinv(15, 10), so before anything is printed.
When the exception occurs, the except-block (Python)/catch-block (C++) is activated. That means that the error message will be printed.
If you would use a b and n such that there is a multiplicative inverse, then no exception will be thrown in the try block, resulting in the multiplicative inverse being printed. The except/catch block will then be ignored, since there was no exception. So the error message will not be printed in that case.


Everything put together into one program


View the example script


Click on Python or C++ to view the entire example script.

import math 

def gcd_iterative(a, b):
   """ Calculating the greatest common divisor 
   using the Euclidean Algorithm (non-recursive) 
   (Source: extendedeuclideanalgorithm.com/code) 
   """
  
   #Set default values for the quotient and the remainder
   q = 0
   r = 1
   
   '''
   In each iteration of the loop below, we
   calculate the new quotient, remainder, a and b.
   r decreases, so we stop when r = 0 
   '''
   while(r > 0):
      #The calculations
      q = math.floor(a/b)
      r = a - q * b
      
      #The values for the next iteration
      a = b
      b = r if (r > 0) else b
   
   return abs(b)


def gcd(a, b):
   """ Calculating the greatest common divisor 
   using the Euclidean Algorithm (recursive) 
   (Source: extendedeuclideanalgorithm.com/code)
   """
   q = math.floor(a/b)
   r = a - q * b
   return abs(b) if (r == 0) else gcd(b, r)
   
   

def xgcd_iterative(a, b):
   """ Calculates the gcd and Bezout coefficients, 
   using the Extended Euclidean Algorithm (non-recursive).
   (Source: extendedeuclideanalgorithm.com/code) 
   """
   #Set default values for the quotient, remainder, 
   #s-variables and t-variables
   q = 0
   r = 1
   s1 = 1 
   s2 = 0
   s3 = 1 
   t1 = 0 
   t2 = 1
   t3 = 0
   
   '''
   In each iteration of the loop below, we
   calculate the new quotient, remainder, a, b,
   and the new s-variables and t-variables.
   r decreases, so we stop when r = 0
   '''
   while(r > 0):
      #The calculations
      q = math.floor(a/b)
      r = a - q * b
      s3 = s1 - q * s2
      t3 = t1 - q * t2
      
      '''
      The values for the next iteration, 
      (but only if there is a next iteration)
      '''
      if(r > 0):
         a = b
         b = r
         s1 = s2
         s2 = s3
         t1 = t2
         t2 = t3

   return abs(b), s2, t2


def xgcd(a, b, s1 = 1, s2 = 0, t1 = 0, t2 = 1):
   """ Calculates the gcd and Bezout coefficients, 
   using the Extended Euclidean Algorithm (recursive).
   (Source: extendedeuclideanalgorithm.com/code) 
   """
   q = math.floor(a/b)
   r = a - q * b
   s3 = s1 - q * s2
   t3 = t1 - q * t2
   
   #if r==0, then b will be the gcd and s2, t2 the Bezout coefficients
   return (abs(b), s2, t2) if (r == 0) else xgcd(b, r, s2, s3, t2, t3)



def multinv(b, n):
   """
   Calculates the multiplicative inverse of a number b mod n,
   using the Extended Euclidean Algorithm. If b does not have a
   multiplicative inverse mod n, then throw an exception.
   (Source: extendedeuclideanalgorithm.com/code)
   """
   
   #Get the gcd and the second Bezout coefficient (t)
   #from the Extended Euclidean Algorithm. (We don't need s)
   my_gcd, _, t = xgcd(n, b)
   
   #It only has a multiplicative inverse if the gcd is 1
   if(my_gcd == 1):
      return t % n
   else:
      raise ValueError('{} has no multiplicative inverse modulo {}'.format(b, n))


def main():
   #Use your own values for a and b
   a = 34
   b = 24
   
   '''
   Euclidean algorithm: 
   see the output of gcd(a, b)
   '''
   print('Euclidean Algorithm:')
   print('The gcd of', a, 'and', b, 'is', gcd(a, b))
   
   #-------------------------------------------------------------
   
   '''
   Extended Euclidean Algorithm:
   see the output of xgcd(a,b) and Bezout coefficients
   And verify that they are correct
   '''
   my_gcd, s, t = xgcd(a, b)
   verification = abs(s*a+t*b)
   print('Extended Euclidean Algorithm:')
   print('The gcd of', a, 'and', b, 'is', my_gcd)
   print('And the Bezout coefficients: s=', s, ' and t=', t, '.', sep='')
   print('And', s, '*', a, '+', t, '*', b, '=', verification)
   if(my_gcd == verification):
         print('So as we expect, s*a+t*b is equal to the gcd we found.') 
   else:
         print('Something went wrong')
   
  #------------------------------------------------------------      
   b = 10
   n = 15
  
   '''
   Multiplicative Inverse:
   Try to compute the multiplicative inverse of b mod n.
   If that succeeds, verify that it's correct.
   If it doesn't succeed, show the error raised by the function.
   '''
 
   print('Multiplicative inverse:')
   try:
      inverse = multinv(b, n);
      print('We discovered that the multiplicative inverse of',
      b, 'mod', n, 'equals', inverse)
      verification = (inverse * b % n == 1)
      if(verification):
            print('And indeed,', b, '*', inverse, 'mod', n, '= 1')
      else:
            print('This is not correct.')    
   except ValueError as error:
      print(error)


#Use main() as main function when you run this script
if __name__== "__main__":
  main()
#include <iostream>
#include <cmath>

using namespace std;


/* Calculating the greatest common divisor 
using the Euclidean Algorithm (non-recursive) 
(Source: extendedeuclideanalgorithm.com/code) */
int gcd_iterative(int a, int b){
	//Set default values for the quotient and the remainder
	int q = 0;
	int r = 1;
	
	/*In each iteration of the loop below, we
	calculate the new quotient, remainder, a and b.
	r decreases, so we stop when r = 0*/
	while(r > 0){
		//The calculations
		q = floor(a/b);
		r = a - q * b;
		
		//The values for the next iteration
		a = b;
		b = (r > 0)? r : b;
	}
	return abs(b);
}



/* Calculating the greatest common divisor 
using the Euclidean Algorithm (recursive) 
(Source: extendedeuclideanalgorithm.com/code) */
int gcd(int a, int b){
	int q = floor(a/b);
	int r = a - q * b;
	return (r == 0)? b : gcd(b, r);
}

//Global variables used by the Extended Euclidean Algorithm
int s = 0;
int t = 0;

/* Calculates the gcd and Bézout coefficients, 
using the Extended Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd_iterative(int a, int b){
	//Set default values for the quotient, remainder, 
	//s-values and t-values
	int q = 0;
	int r = 1;
	int s1 = 1; 
	int s2 = 0;
	int s3 = 1; 
	int t1 = 0; 
	int t2 = 1;
	int t3 = 0;
	
	/*In each iteration of the loop below, we
	calculate the new quotient, remainder, a, b,
	and the new s-values and t-values.
	r decreases, so we stop when r = 0*/
	while(r > 0){
		//The calculations
		q = floor(a/b);
		r = a - q * b;
		s3 = s1 - q * s2;
		t3 = t1 - q * t2;
		
		/* The values for the next iteration, 
		(but only if there is a next iteration)*/
		if(r > 0){
			a = b;
			s1 = s2;
			t1 = t2;
			b = r;
			s2 = s3;
			t2 = t3;
		}
	}
	s = s2;
	t = t2;
	return abs(b);
}

/* Calculates the gcd and Bézout coefficients, 
using the Extended Euclidean Algorithm (recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1){
	int q = floor(a/b);
	int r = a - q * b;
	int s3 = s1 - q * s2;
	int t3 = t1 - q * t2;
	
	s = s2;
	t = t2;
	
	return (r == 0)? b : xgcd(b, r, s2, s3, t2, t3);
}

/* Calculates the multiplicative inverse of a number b mod n,
using the Extended Euclidean Algorithm. If b does not have a
multiplicative inverse mod n, then throw an exception.
(Source: extendedeuclideanalgorithm.com/code) */
int multinv(int b, int n){
	if(xgcd(n, b) == 1){
		//t is a global variable that is assigned a value by xgcd
		return (t + n) % n;
	}
	else{
		throw -1;
	}
}

int main(int argc, char** argv) {
	//Use your own values for a and b
	int a = 34;
	int b = 24;
	
	//Euclidean Algorithm:
	//see the output of gcd(a, b)
	
	cout << "Euclidean Algorithm:" << endl;
    cout << "The gcd of " << a << " and " << b << " is " << gcd(a, b) << endl;
	
	//-------------------------------------------------------------
   
    /*Extended Euclidean Algorithm:
    see the output of xgcd(a,b) and Bezout coefficients
    And verify that they are correct.*/
	
	int my_gcd = xgcd(a, b);	//xgcd will set global variables s and t
	int verification = abs(s*a+t*b);
	cout << "Extended Euclidean Algorithm:" << endl;
	cout << "The gcd of " << a <<  " and " << b << " is " << my_gcd << endl;
	cout << "And the Bezout coefficients: s=" << s << " and t=" << t << "." << endl;
	cout << "And " << s << " * " << a << " + " << t << " * " << b << " = " << verification << endl;
	if(my_gcd == verification){
         cout << "So as we expect, s*a+t*b is equal to the gcd we found." << endl;
    }
    else{
	     cout << "Something went wrong" << endl;
    }
	
	//#------------------------------------------------------------ 
	b = 15;
	int n = 10;

    /*Multiplicative Inverse:
    Try to compute the multiplicative inverse of b mod n.
    If that succeeds, verify that it's correct.
    If it doesn't succeed, show the error raised by the function.*/

	try {
      	cout << multinv(b, n) << endl;
  	}
  	catch (int n) {
      	cout << "Error: there is no multiplicative inverse for the given numbers" << endl;
  	}
  	
	
	return 0;
}


Download the example scripts


Download Python script
Download C++ script