Home

Welcome to ExtendedEuclideanAlgorithm.com!
A website with a calculator that shows you the intermediate steps
and finally some clear explanations about the Extended Euclidean Algorithm.

What will you find here?

Calculator

We have a really cool calculator that can show you the entire calculations for the Euclidean Algorithm, Extended Euclidean Algorithm and the multiplicative inverse.
You give it any input numbers you wish and choose the algorithm. Then we'll not only show you the correct answer, but also all of the intermediate steps!

• Go to the calculator

Info

To understand the algorithms and the output of the calculator, we have some pages (and videos) explaining stuff:

• The Euclidean Algorithm
• The Extended Euclidean Algorithm
• Calculate the modular multiplicative inverse of a number modulo n using the Extended Euclidean Algorithm

Code examples

Do you want to program an application yourself that uses any of the algorithms? Then have a look at our

• Python and C++ codes for the (Extended) Euclidean Algorithm and Multiplicative Inverse

I'm confused, tired and I want to understand it NOW

Alright, alright, calm down! Take a deep breath, it's al going to be okay. Don't just head over the calculator right away, because I understand that it may seem weird and intimidating when you see its first output. Here's what you need to do.

1. Read the page or watch the video about the Euclidean Algorithm.
   I hear you saying "Why? I am only interested in learning the Extended Euclidean Algorithm. I have wasted enough time already."
   But in order to learn the Extended Euclidean Algorithm, you first have to understand the Euclidean Algorithm. It's actually not that difficult, it won't take much time (I promise!) and it makes you understand the Extended Euclidean Algorithm a lot faster too.
2. Then learn the Extended Euclidean Algorithm.
   Basically the same idea as the Euclidean Algorithm, but with some extra columns.
3. For anything about the modular multiplicative inverse, go to this page.
For those who want to calculate the multiplicative inverse of a number (mod n) using the Extended Euclidean Algorithm.
Don't be ashamed if you're not entirely sure what a multiplicative inverse even is, it's explained there as well.

Feedback & Contact

Do you like this website? Or do you have any suggestions on how to improve it? Let me know!
Please have a look at the Feedback & Contact page.


Enjoy and good luck studying!