E.E.A. .com
It doesn't have to be difficult if someone just explains it right.

Code examples

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.

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

Table of contents

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.

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.

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:

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.

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:

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.

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.