Here you will find Python and C++ example codes for the Euclidean Algorithm, Extended Euclidean Algorithm and Modular 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: ".)
What language do you prefer?
or ?
We will open the relevant tab for you by default in all of our tabmenus.
Hide or show code by default?
We've hidden all of the codes inside spoilers to make the page look better. If you think it's annoying you have click each of those spoilers to show the code, then click the button:
General remarks
For the Euclidean Algorithm and the Extended Euclidean Algorithm, we'll show two versions:
A non-recursive version, which is easier to understand, but contains ugly code.
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.
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.
Language specific remarks
On top of our code, we're using
import math
We use ternary expressions.
Here's an example:
a = a if b < 1 else b
The line of code above is equivalent to this:
if(b < 1):
a = a
else:
a = b
It's called a ternary expression. You can also do this with return statements. For example:
return 13 if a==0 else 37
This means:
if (a == 0):
return 13
else:
return 37
On top of our code, 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.
We use ternary expressions.
Here's an example:
a = (b < 1)? a : b;
The line of code above is equivalent to this:
if(b < 1){
a = a;
}
else{
a = b;
}
It's called a ternary expression. You can also do this with return statements. For example:
We start with the non-recursive version of the algorithm.
#Warning: can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can
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)
//Warning: can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can
/* 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.
What if b=0?
There's one problem with the code above: it can't handle the case where b=0.
Do you want to know why and what a non-recursive version of the Euclidean algorithm looks like that can handle b=0? Then keep reading.
But my advice: skip this part and continue to the recursive version of the Euclidean Algorithm. Here we've fixed that as well with a simple if statement.
If you would call this function with something like gcd_nonrecursive(-25, 0), you would expect the answer to be 25 (because of the property of the gcd that gcd(a, 0)=|a|).
Instead you get a divide by 0 error, because of the floor(a/b) and b=0. The reason that this happens is because we always skip the last row in our version of the Euclidean Algorithm because we're lazy. But when b=0, that last row that we skip is actually the only row. So to solve this, we can just include the row that we always skip in our algorithm. Do you want to know what a table looks like that doesn't skip the last row? See the spoiler here.
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(b > 0):
#The calculations
q = math.floor(a/b)
r = a - q * b
#The values for the next iteration
a = b
b = r
return abs(a)
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(b > 0){
//The calculations
q = floor(a/b);
r = a - q * b;
//The values for the next iteration
a = b;
b = r;
}
return abs(a);
}
Things that are changed here:
while(r > 0) is changed to while(b > 0)
we just use b=r as last line in the while loop now
we return abs(a) instead of abs(b)
Now when b=0, it just returns abs(a). In all other cases, it goes into the while loop first. Usually we can find the final answer in the column of b on the last row, but now there's an extra row, so that same answer moved into the column of a in that extra row. That's why we now return abs(a) instead of abs(b).
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)
"""
if(b == 0):
return abs(a)
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){
if(b == 0){
return abs(a);
}
int q = floor(a/b);
int r = a - q * b;
return (r == 0)? abs(b) : gcd(b, r);
}
There's an if statement at the beginning, taking care of the case where b=0.
The rest of the code does exactly the same as the non-recursive function.
Some more explanation
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:
#Warning: this version can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can.
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;
//Warning: this version can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can.
/* 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.
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.)
Beware of a bug in this code: it can't handle b=0.
Just like the non-recursive function we showed for the Euclidean algorithm, this code fails when you ask it the gcd(a,b) with b=0. We have solved this in the recursive version, so my advice is to skip this part and head over to the recursive function. But if you are really interested in a non-recursive function of the Extended Euclidean Algorithm that can handle the case of b=0, keep reading. Here's the code:
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(b > 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,
a = b
b = r
s1 = s2
s2 = s3
t1 = t2
t2 = t3
return abs(a), s1, t1
//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(b > 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:
a = b;
s1 = s2;
t1 = t2;
b = r;
s2 = s3;
t2 = t3;
}
s = s1;
t = t1;
return abs(a);
}
This code is very similar to the non-recursive code that can handle b=0 of the Euclidean Algorithm. The things that different from the non-recursive version of the Extended Euclidean Algorithm above are:
while(r > 0) is changed to while(b > 0)
We removed the if statement that said if(r > 0) inside the while loop
we return abs(a) instead of abs(b) and s1 and t1 instead of s2 and t2
The reason why we return different values here, is because we now use a table with an extra row. The answers we are looking for can be found on the row where r=0, but if you then add another row, the answers shift a bit to the left. If you want to read more about this, check the information inside the spoiler here.
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)
"""
if(b == 0):
return abs(a), 1, 0
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)
(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){
if(b == 0){
s = 1; t = 0;
return abs(a);
}
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.
The if statement is for the case when b=0 (e.g. when we call it like xgcd(some number, 0)). If you want to know why we return abs(a) there instead of abs(b) and why we return s=1 and t=0, check out the information inside the spoiler here.
Calculating the Modular 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))
/* 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;
}
}
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.
So this function calculates the modular 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.
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 modular 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) or throw (C++) an exception when there is no modular 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 modular 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 modular multiplicative inverse. An exception will occur, since 15 mod 10 does not have a modular 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) or 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
We've put all of the functions discussed on this page in a single file for, such that you can play with it. You can view or download them below.
'''
Source: extendedeuclideanalgorithm.com
'''
import math
#Warning: can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can
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)
#Can handle b=0
def gcd_iterative_2(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(b > 0):
#The calculations
q = math.floor(a/b)
r = a - q * b
#The values for the next iteration
a = b
b = r
return abs(a)
def gcd(a, b):
""" Calculating the greatest common divisor
using the Euclidean Algorithm (recursive)
(Source: extendedeuclideanalgorithm.com/code)
"""
if(b == 0):
return abs(a)
q = math.floor(a/b)
r = a - q * b
return abs(b) if (r == 0) else gcd(b, r)
#Warning: this version can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can.
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
#Can handle b=0
def xgcd_iterative_2(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(b > 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)
'''
a = b
b = r
s1 = s2
s2 = s3
t1 = t2
t2 = t3
return abs(a), s1, t1
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)
"""
if(b == 0):
return abs(a), 1, 0
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;
//Source: extendedeuclideanalgorithm.com
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//Warning: can\'t handle b=0. See extendedeuclideanalgorithm.com/code for a version that can
/* 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 (non-recursive)
(Source: extendedeuclideanalgorithm.com/code) */
int gcd_iterative2(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(b > 0){
//The calculations
q = floor(a/b);
r = a - q * b;
//The values for the next iteration
a = b;
b = r;
}
return abs(a);
}
/* Calculating the greatest common divisor
using the Euclidean Algorithm (recursive)
(Source: extendedeuclideanalgorithm.com/code) */
int gcd(int a, int b){
if(b == 0){
return abs(a);
}
int q = floor(a/b);
int r = a - q * b;
return (r == 0)? abs(b) : gcd(b, r);
}
//Global variables used by the Extended Euclidean Algorithm
int s = 0;
int t = 0;
//Warning: this version can\'t handle b=0. See extendedeuclideanalgorithm.com/code for a version that can.
/* 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-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);
}
//Can handle b=0
/* Calculates the gcd and Bézout coefficients,
using the Extended Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code) */
int xgcd_iterative2(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(b > 0){
//The calculations
q = floor(a/b);
r = a - q * b;
s3 = s1 - q * s2;
t3 = t1 - q * t2;
a = b;
s1 = s2;
t1 = t2;
b = r;
s2 = s3;
t2 = t3;
}
s = s1;
t = t1;
return abs(a);
}
/* 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){
if(b == 0){
s = 1; t = 0;
return abs(a);
}
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);
}
/* 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 = 20;
int b = 15;
cout << gcd(a, b);
//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;
}