0:00

In our previous lesson,

Â we showed that division is not defined in

Â modular arithmetic and then even when it might appear that it should work,

Â it might not, and therefore,

Â should always be avoided.

Â We also mentioned that there was an analog to division,

Â which is the multiplicative inverse.

Â In this lesson, we'll introduce the concept of a multiplicative inverse,

Â explore what is required for such an inverse to exist,

Â and learn how to use the Euclidean Algorithm to

Â find the greatest common divisor of two numbers,

Â which will tell us whether a multiplicative inverse actually exists.

Â We'll then look at how efficient this algorithm

Â is and finally prove that it actually works.

Â This will set the stage for a future lesson in which

Â we will extend the Euclidean algorithm so that

Â we can use it not only to determine if

Â a multiplicative inverse exists but to actually find it.

Â Let's recast our division into multiplication.

Â We know that dividing by some number is the same as multiplying by its reciprocal

Â and that the reciprocal can be written as the power raised to the negative one power.

Â We also know that another name for the reciprocal of

Â a number is its multiplicative inverse because,

Â by definition, the product of a number and

Â its multiplicative inverse is the multiplicative identity, which is one.

Â Note that some authors argue, with some justification,

Â that using an exponent of minus one to indicate the multiplicative inverse is an abuse

Â of notation since it is so strongly associated with the vision in normal arithmetic.

Â Nonetheless, it is perhaps the most common notation

Â used and others argue, again with merit,

Â that not only does it have a lot to recommend it so that is no more of

Â an abuse than many other common notations that have far greater potential for ambiguity.

Â You'll even see some authors use the division operator with

Â the understanding that since division isn't defined in modular arithmetic

Â that this indicates multiplication by the multiplicative inverse of

Â the denominator but most people feel this is too much of an abuse and more to the point,

Â far too likely to lead people to improperly perform the division itself.

Â So we'll stick with the negative one exponent.

Â We can use this definition directly in the mods in world.

Â For example, consider a mod-7 world,

Â we can build a multiplication table very easily and then pick

Â off the multiplicative inverses of each residue class by inspection.

Â Note that zero does not have a multiplicative inverse.

Â Hardly surprising since anything multiplied by zero is zero and hence,

Â there is nothing we can multiply it by to get one,

Â but all other residue classes do have a multiplicative inverse.

Â Sometimes, it's itself, again, hardly surprising,

Â since in the normal integers one is its own multiplicative inverse.

Â In a mod-n world,

Â it turns out that in minus one is also always its own multiplicative inverse.

Â You might see if you can prove that this must be the case.

Â There are a couple of fairly easy ways to do this.

Â You might also see if you can construct a modulus such that some number other than

Â one and in minus one is its own multiplicative inverse.

Â But what about in a mod-15 world?

Â We see that while some residues do have multiplicative inverses,

Â many don't and that three is among them.

Â So, when we try to divide 15 by three,

Â this must be equivalent to multiplying 15 by the multiplicative inverse of three,

Â which is a number that doesn't exist.

Â Therefore, it's not surprising that we can get nonsensical answers.

Â It's sort of like those proofs that we've all seen that

Â two equals one and when we look at them carefully,

Â we discover that at some point,

Â we had to divide by an expression that was equal to zero, another undefined operation.

Â The next reasonable question is,

Â "Why do some numbers have multiplicative inverses in

Â a particular modular world and others don't?"

Â A related question is,

Â "How can we determine whether or not a number has

Â a multiplicative inverse in a given modular world?"

Â Let's look at our mod-15 table and see if we notice anything that

Â distinguishes those numbers that have multiplicative inverses from those that don't.

Â It may not jump out at you immediately,

Â but the only numbers that have multiplicative inverses

Â are those that are relatively prime to the modulus.

Â This turns out to be both a necessary and a sufficient

Â condition for the multiplicative inverse of a number to exist,

Â but can we prove this?

Â We need to prove this claim in both directions.

Â First, let's prove the sufficient claim.

Â Assume that we have a number a and a modulus m that are relatively prime.

Â Now, let's create a sequence containing m values by multiplying

Â a by every non-negative integer less than m. Now,

Â pick any two different multipliers x and y in this range.

Â Meaning that they are not congruent modular m. Can x

Â times a and y times a be in the same residue class?

Â This requires that the difference of x and y multiplied by a must be

Â a multiple of m. Since a and m do not contain any common prime factors,

Â this means that x minus y must be a multiple of

Â m. Since x and y are both strictly less than m,

Â there are difference lies strictly between minus m and plus m,

Â making the only possible multiple zero,

Â which requires x and y to be the same but we specify that they are different.

Â The conclusion is that no two members of our sequence can be in

Â the same residue class and since there are m members and m residue classes,

Â the Pigeonhole principle thus demands that every residue class is represented in

Â that sequence exactly once including the residue class containing one.

Â Whatever coefficient of a corresponds to this member is, by definition,

Â the multiplicative inverse of a mod m. Thus,

Â being relatively prime to the modulus is sufficient to have a multiplicative inverse.

Â Now, let's tackle the necessary claim.

Â When a and m are not relatively prime,

Â the GCD of a and m,

Â let's call it c, is greater than one.

Â This means that we can write a and m in terms of c and

Â two other integers b and n that are relatively prime,

Â otherwise c would not be the greatest common divisor.

Â The requirement that we had before on x minus y in terms of a and m reduces to

Â the same problem as before except in terms of

Â b and n. This is the same problem we just solved.

Â Meaning, that we know that as we multiply b by every non-negative integer less than n,

Â we produce all possible n residues including one.

Â To get back to the residues produced by multiplying

Â a by all of the non-negative integers less than m,

Â we just multiply all of the residues in this sequence by c. We can conclude two things.

Â First, we can only produce m divided by the GCD,

Â distinct residues, so each will be repeated that many times.

Â Second and most important,

Â one will not be among them.

Â In order for a number to have a multiplicative inverse in a certain modular world,

Â it is necessary for that number to be relatively prime to the modulus.

Â If you look back at our multiplication table for our mod-15 world and

Â look at say row a equal six for instance,

Â you'll notice that since the GCD of six and 15 is three,

Â the residues are all multiples of three and there are three instances of each.

Â How do we determine whether a and m are relatively prime?

Â We find the GCD of a and m and see if it is one.

Â How do we find the GCD of two integers?

Â By using the oldest-known mathematical algorithm,

Â namely the Euclidean algorithm,

Â which states that given two integers x and y with x greater than y,

Â the GCD of x and y is the same as the GCD of y and x reduced modular y.

Â Notice that the requirement that x be greater than y is merely for convenience.

Â We simply choose to put the largest value first.

Â And, again, for convenience,

Â we'll use the % sign to indicate modular reduction.

Â Let's see if 1024 and 2017 are relatively prime.

Â After just three iterations,

Â we have the GCD of something and one,

Â which is clearly one.

Â Thus, these two numbers are relatively prime.

Â If they hadn't been relatively prime,

Â then the residue would have become zero before becoming one and

Â the value just before that happened would be the GCD we are looking for.

Â Before we prove that the Euclidean Algorithm actually works,

Â let's look at the efficiency that it affords if it does work.

Â After two iterations, the larger of the two numbers goes from x to x%y.

Â What is the largest that x%y can be relative to x?

Â There are three possibilities.

Â The first is only worth noting in passing and that's if y is

Â equal to x over two then y%x is zero.

Â If y is less than x over two then

Â x%y is less than x over two since the residue is always less than y.

Â But if y is greater than x over two then the residue of x%y is simply x minus y,

Â and since y is greater than half of x,

Â the difference must be less than half of x.

Â Thus, if x is greater than y,

Â x%y is less than half of x.

Â So every two iterations of the algorithm,

Â we reduce the larger argument by at least a factor of two.

Â The furthest we can go is when we get to a GCD of one.

Â Thus, a limit on the number of iterations is on the order of

Â the base two logarithm of the larger of the two numbers.

Â Since a larger number is usually the modulus and

Â the base two logarithm is also the number of bits needed to represent a number.

Â The worst case performance for the Euclidean Algorithm

Â is generally twice the number of bits in the modulus,

Â but it almost always does much, much better.

Â Now, comes the question of whether or not it actually works?

Â As long as the claim is true that the GCD of two integers is identical to

Â the GCD of the smaller the integers

Â and the larger one reduced by the smaller then it works.

Â Let's call c the GCD of x and y.

Â This means that c divides both x and y.

Â Let's write x in terms of its residue and then solve for the residue,

Â r which is x%y.

Â Since c divides both x and y,

Â then it can be factored out of both terms.

Â Meaning that it also divides r and is thus a common factor of

Â all three and specifically of y and r. Now,

Â it may not be the GCD of y and r,

Â but we know that the GCD of y and r is at least this large.

Â So, the GCD of y and r is at least as large as the GCD of x and y.

Â Now, let's look at it the other way around.

Â If d is the GCD of y and r,

Â this means that d divides both y and r. Going back to our expression for x,

Â we can thus factor d out of both terms.

Â And therefore, d is a factor of both x and y.

Â But the GCD of x and y might be larger.

Â The only way that both of these inequalities can be

Â simultaneously satisfied is the GCD of

Â x and y is identically equal to the GCD of y and r. Remembering that r is x%y,

Â we have thus proven that the claim underlying the Euclidean Algorithm is true.

Â Personally, I find it remarkable that one of

Â the most efficient algorithms to find

Â the greatest common divisor is also the oldest algorithm known.

Â In fact, many of our bedrock algorithms in cryptography can

Â trace their roots to work that is centuries or even millennia old.

Â But perhaps this isn't so surprising.

Â People back then were just as intelligent as we are today.

Â But they lack the computing tools that we enjoy.

Â Hence, they had great motivation to devise ways to do things very efficiently by hand

Â and efficient hand algorithms generally lend

Â themselves to efficient programmatic implementations.

Â Recapping, in this lesson,

Â we learned the specifics of what a multiplicative inverse means in

Â a modular world and that they exist only for

Â numbers that are relatively prime to the modulus.

Â We also learn that the Euclidean Algorithm efficiently finds the GCD of two numbers,

Â which is the information we need to

Â know in order to determine if they are relatively prime.

Â Finally, we prove that the Euclidean Algorithm really does work.

Â Coming up next, we'll extend the Euclidean Algorithm and

Â use it to not only determine if a multiplicative inverse exists,

Â but also to find out what it is in a very efficient way.

Â