# 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: ".)

### Things to note before reading the codes

• We use ternary expressions.
For example:
Python:
```a = a if b < 1 else b
```
C++:
```a = (b < 1)? a : b;
```

If you don't know what that means, then

• For the Euclidean Algorithm and the Extended Euclidean Algorithm, we'll show two versions:
• A non-recursive version, which is easier to understand
• A recursive version, because it's a lot shorter (but harder to understand if you don't know what's going on).
My advice is to first look at the non-recursive version, such that you understand how to algorithm works. After that it's easier to understand the recursive version, which you can then use for your homework or project.
• For the Python codes, we're using
``````import math
``````
• For C++ codes, we're using
``````#include <iostream>
#include <cmath>

using namespace std;
``````
Note that using namespace std; is usually considered bad practice. (Click here to read why.) So it would be better to remove this line and add the std:: prefix to all things like cout and endl, etc. But since we are giving you example code, we choose to use namespace std; here for simplicity and readability.
• If you're only here to copy the codes, then that's fine (as long as you don't remove the url to this website from the code(s)!). But if you want to get a better understanding of what is actually happening in these codes, it is very useful to read the other pages on this website before reading this page.
• We have put the codes into seperate functions. At first, we only show you the code for each function. If you're interested in how to call these functions we give you (e.g. from your main function), have a look at the bottom of this page where we give you the whole code with everything in it, including a main function that you can use to call the other functions.

### Euclidean Algorithm (non-recursive)

``````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;
}``````