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.

Â