Given two integers x and y the extended Euclidean alogarithm finds integers a and

b that solve the integer polynomial expression a times x plus b times y,

is equal to the greatest common device of x and y.

Since we are only interested in cases where x and y are core prime.

We normally just set the right hand side equal to 1.

Note that this is not a modular equation, it is in the full world of integers.

Assuming that x and y are relatively prime and we find values for a and b,

then if we reduce the equation module of y, we immediately discover that a and

x are multiplicative inverses mod y.

Similarly, if we reduce at mod x, we discover that b and y,

our multiplicative inverse is mod x.

However, by symmetry, there is nothing that prevents

us from reducing the equation either mod a or mod b.

Doing so, we discover that a and x are also inverses in a mod b world, and

that b and y are inverses in a mod a world.

That's quite a bit of information to get from the solution to a single equation and

there's fair amount of bookkeeping involved to get it.

Which is why we will actually develop a version of the algorithm that

is narrower in scope.

When we force the right hand side of our question to be 1, then there might be

many solutions, no solution at all, or just a single solution.

For instance, if x=1 and y=0,

then there are infinitely many solutions with a = 1 and any value for b.

You might consider how this confirms one thing we already know,

which is that 1 and -1, which is congruent to n- 1 mod n,

are always their own multiplicative inverses in any modular world.

Leaving aside the pathological case of a mod zero world.

On the other hand, if x = 2 and y = 4, then there are no solutions.

Because it requires that an integer equation on the left

be equal to a non integer fraction on the right.

Clearly this is impossible.

In fact, if x and y are not relatively prime, then they have a common

fact greater than 1 that can be factored out of the left side,

resulting in a new integer expression that must be equal to a non-integer fraction,

which is not possible.

Hence, there are no solutions unless x and y are relatively prime.

Something that we should find comforting since we already know that this

must be the case since we know that multiplicative inverses

is do not exist in this situation.

Now let's use x = 7 and y = 11.

The one solution to this equation has a = eight and b = -5.

If we reduce this equation in modulo 11,

we discover that 7 and 8 are multiplicative inverses in this world.

But notice that if we reduce it modulo five since modulo negative n and

modulo n are the same world Something you should convince yourself of

by revisiting our defining relation.

Then 7 and 8 are still multiplicative inverses.

This makes sense since 11 times 5 is 55 and 7 times 8 which is 56,

is 1 greater than an integer multiple of either modulus.

Similarly, if we reduce this equation modulo 7, or

modulo 8, we discover that -5 and

11 are multiplicative inverses in either world, but there's a bit of a catch here.

Since in a mod 7 world these are congruent to 2 and 4 respectively,

while in a mod 8 world, they are both congruent to 3.

Making 3 it's own multiplicative inverse in this world.

As noted previously,

this is a lot of information gained from the solution to just one equation.

And while interesting and potentially useful,

it's somewhat a case of information overload.

We want to know just one thing, for example,

what is the multiplicative inverse of 7 modulo 11.

And if we can streamline the book keeping that we need to get the answer to just

that question, it's probably worth doing so.

So, instead of building up and using the full extent of Euclidean algorithm,

we'll now build up a version of it that's much narrower in scope, but

still sufficient to answer this specific question.