0:00

In previous lessons we've seen that modular division is not defined and

indeed we need to be careful not to use it even when the result appears obvious.

But we do have the concept of a multiplicative inverse,

namely that a number multiplied by its multiplicative inverse

is congruent to one in the given module list.

We've also seen that the multiplicative inverse of a number exists, if and

only if the number is relatively prime to the modulus.

And that the Euclidean algorithm can be used to determine whether or

not two numbers are relatively prime.

Now we extend the Euclidean algorithm to have it not only tell us whether

a multiplicative inverse exists, but when it does, to also find out what it is.

We'll first look at the intended result of the extended Euclidean algorithm and

what it can tell us.

But instead of developing the full algorithm,

we'll instead develop a narrower version of it tailored to our goals.

Finally we'll work a few examples,

including some where the multiplicative inverse exist, and one way it doesn't.

0:58

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.

5:36

Since our recurrence relation needs values two steps back, we need initial values for

the first two members of the sequence.

Looking back to our first step, we see that r0 must be the modulus and

r1 must be the number we are seeking the multiplicative inverse for.

This continues until either the second argument becomes 1,

meaning that the two initial arguments are relatively prime, or it becomes 0,

meaning that they aren't and no inverse exists.

Our next task is to tie the recurrence relation for the Euclidean algorithm

directly to our goal of finding the multiplicative inverse, a,

defined by the congruence of the product of of a and x, with 1 (mod m).

Noting that 1 is the final value of r[i], assuming an inverse exists,

we can define an auxiliary congruence relation in which we have a sequence of

a values, which can be described as a sequence of coefficients,

that when multiplied by x are congruent to a corresponding r value.

Next, we use our defining relation for modular arithmetic

to rewrite the recurrence relation we already have directly in an integer world.

The quotient, which is also a sequence of quotients,

is the floor of the residue two back, divided by the previous residue.

If a big red flag just went up when I mentioned performing division in

any way shape or form, then you've been paying attention.

So, we need to be sure that what we were doing is legitimate.

The first thing to note that this equation lives in an integer world.

Notice the equal sign as opposed to a congruency sign.

Second, it is part of the defining relationship for

being able to bridge the world from integers to a modular world.

Finally, this particular division operation is merely a means to select

a particular integer value of the quotient, that corresponds to a particular

value of the residue, so as to satisfy our defining relation.

7:28

The reason that we took our reconciliation into the integer world, is because it

involves a module reduction that is done using a different modulus at each step,

while our auxiliary congruence relation always lives in a mod m world.

Hence we take it into a purely integer world, solve it for r of i and

then reduce it mod m.

Now we can replace each residue with the corresponding product

using our congruence relation, since everything is in the same mod m world.

Notice that every term is multiplied by x.

We can't just blindly cancel them out because that is performing division

in a modular world.

But if x has a multiplicative inverse mod m,

then we can multiply every term by that value and cancel out the x's that way.

But we don't know whether or

not x has a multiplicative inverse mod m, that's what we're trying to find out.

But we can speculate that it does since if we're correct,

we can perform the cancellation and proceed.

If we're wrong, it might mess up our result.

But that's okay, because there is no correct result since no inverse exists.

Our sequence of remainders will reveal whether we guessed correctly.

And, if we didn't, we get to ignore our results.

Thus we have our recurrence relation for our coefficient sequence.

Before continuing, a word of caution.

You might be tempted, and it's easy to get real tempted, to simplify the equation for

the quotient by substituting in the auxiliary congruence,

cancelling the x, and taking the floor of the quotient of the two prior members of

the coefficient sequence.

This will cause problems,

because our auxiliary equation is a congruence relation in a modular world.

Simply put, the ratio of two members of a congruence class

does not remain the same as you substitute in different members of the class.

This is the heart of why modular division is not defined.

9:37

Just as we need to initialize the first two elements of our residue sequence,

we need to initialize the first two elements of our coefficient sequence.

This is very easily done using our auxiliary equation directly.

Since we know the values of r[0] and r[1],

we can just plug them into this equation and get the values for a[0] and a[1].

Since r[0] = m which is congruent to 0 mod m, a[0] must also be congruent to 0.

We choose to make it = 0 for convenience.

Similarly, since r[1] = x, a[1] must also be congruent to 1.

And we choose to make it = 1.

Now we have everything we need.

So let's collect our two recurrence relations in one place.

Our first recurrence relation is nothing more than the normal Euclidean algorithm.

Our second recurrence relation is split into two pieces purely for convenience.

The first part is the quotient of the prior residues,

which is then used to update our coefficient sequence.

Now that we don't need the first two values of the quotient sequence

since our first update involves q2.

Let's first do the simple example from earlier, in which we want to find

the multiplicative inverse of 7 in a mod 11 world.

At each step, the residue is congruent to 7 times the coefficient mod 11,

as we would expect.

Now let's try it on something larger,

say the multiplicative inverse of 2,000 in a mod 2017 world.

Since the coefficient values lie in a mod 17 world,

we can replace any of them with any other values from the same residue class,

something that can make the math quite a bit easier sometimes.

For instance, we can choose negative values for

any coefficient greater than half the modulus.

This also provides a useful check,

since the sign of the coefficient value should alternate.

11:26

What if there is no multiplicative inverse?

Then the remainder will never be equal to one, it will become zero at some point,

and the value of the previous remainder is the GCD,

just like in the normal Euclidean algorithm.

For example, let's attempt to find the multiplicative inverse of 22 mod 3.

After reaching r[i] equals 0,

we can look at the prior step and see that it is not 1.

Hence they are not relatively prime and no multiplicative inverse exists.

While the congruences between the coefficient times x

in the residue may still hold, it is not guaranteed.

Recall that to get our updated equation we cancelled out x from both sides,

which required multiplying by the multiplicative inverse of x.

which doesn't exist in this case.

So our coefficient values might become bogus at some point.

Let's pick a more challenging example.

Does 14,019 have a multiplicated inverse in a 1,247,290 world, and

if so, what is it?

I'd recommend pausing the video and setting up a spreadsheet.

But it's not it all difficult, to work through it by hand,

even without a calculator.

And remember that you don't have to use the principal residues.

If it's more convenient to work with -10

instead of 1,247,290, then by all means do that.

You should come up with an answer of 1,169,529 after just 5 iterations,

Remember you get steps 0 and 1 for free.

12:58

Recapping what we've learned in this lesson,

we first saw that the full extended Euclidean algorithm,

solves a particular integer equation, that can reveal the multiplicative inverse of

several integers in several modular worlds.

But in order to minimize our book keeping burden,

We developed a lighter weight version, more appropriate to our specific goal.

With the resulting recurrence relations, we can efficiently find

out whether a multiplicative inverse exists and if so, what it is.

If our sequence of residues ever produces a 1,

then the multiplicative inverse exists.

But if we reach a residue of 0 first, then the greatest common divisor of

the two numbers is the prior residue, which could potentially be useful.

But in any event the multiplicative inverse does not exist.