It doesn't have to be difficult if someone just explains it right.
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: ".)
- 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).
- 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.
Table of contents
- Euclidean Algorithm (non-resursive)
- Euclidean Algorithm (recursive)
- Extended Euclidean Algorithm (non-recursive)
- Extended Euclidean Algorithm (recursive)
- Calculating the Modular Multiplicative Inverse
- ⇨ Everything on this page put together into one program/script
Euclidean Algorithm (non-recursive)
We start with the non-recursive version of the algorithm.
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.
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.
while(r > 0)is changed to
while(b > 0)
- we just use
b=ras last line in the while loop now
- we return
Euclidean Algorithm (recursive)
Now that you understand what is going on, we'll show that we can actually do this a lot shorter:
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:
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.
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:
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
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.
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.)
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 ;)
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.