Finding Modular Inverses

Summary

This video script explores the concept of modular inverses, focusing on how to find the multiplicative inverse of a number 'a' modulo 'M'. It explains that an inverse exists if and only if the greatest common divisor of 'a' and 'M' is one. The script provides step-by-step examples, demonstrating how to calculate the inverses of numbers like 5 mod 7, 5 mod 11, and 18 mod 19. It also introduces a shortcut for finding inverses when a number is equivalent to a negative value modulo 'M'. The script concludes with an example illustrating that no inverse exists when the greatest common divisor is greater than one, such as with 5 mod 10.

Takeaways

• 🔢 Modular inverses are multiplicative inverses that, when multiplied by a number, result in 1 modulo M.
• 🔄 A number 'a' has an inverse modulo M if and only if the greatest common divisor (GCD) of 'a' and M is 1.
• 🚫 If the GCD of 'a' and M is greater than 1, then 'a' does not have an inverse modulo M.
• 🌰 Examples are given to illustrate how to find the modular inverse, such as finding the inverse of 5 modulo 7 and modulo 11.
• 📝 The notation for expressing a modular inverse is 'a^-1 ≡ b (mod M)', indicating 'b' is the inverse of 'a' modulo M.
• ⏱️ Finding modular inverses can be time-consuming, so shortcuts are sometimes used, like recognizing that 18 is equivalent to -1 modulo 19.
• 🔁 Negative numbers can have modular inverses; for example, the inverse of -2 modulo 19 is -10, which is also 9 modulo 19.
• 💡 A shortcut for finding inverses involves using the property that a number and its negative have the same inverse modulo M.
• ❌ There is no modular inverse when the GCD of the number and the modulus is greater than 1, as shown with the example of 5 modulo 10.
• 📚 The script emphasizes the importance of understanding the relationship between GCD and the existence of modular inverses.

Q & A

What are modular inverses?

Modular inverses are pairs of numbers that, when multiplied together, result in 1 when considering the modulus operation. Specifically, a number 'a' has an inverse mod 'M' if there exists a number 'b' such that (a * b) % M = 1.

How can you determine if a number has a modular inverse modulo M?

A number 'a' has a modular inverse modulo 'M' if and only if the greatest common divisor (GCD) of 'a' and 'M' is equal to one. If the GCD is greater than one, there is no modular inverse.

What is the modular inverse of 5 modulo 7?

The modular inverse of 5 modulo 7 is 3, because 5 * 3 % 7 = 1.

What is the process to find the modular inverse of a number?

To find the modular inverse of a number 'a' modulo 'M', you start with 1 and keep adding 'M' until you find a multiple of 'a'. The quotient of that multiple divided by 'a' is the modular inverse.

What happens if the greatest common divisor between a number and the modulus is greater than one?

If the greatest common divisor between a number 'a' and the modulus 'M' is greater than one, then 'a' does not have a modular inverse modulo 'M'.

Can you provide an example of finding the modular inverse of 5 modulo 11?

To find the modular inverse of 5 modulo 11, you would start with 1 and keep adding 11 until you find a multiple of 5 that is congruent to 1 modulo 11. In this case, 45 is 5 times 9 and 45 % 11 = 1, so the inverse of 5 modulo 11 is 9.

Why is the inverse of 18 modulo 19 equal to 18?

The inverse of 18 modulo 19 is 18 because 18 * 18 % 19 = 1. This is a special case where the number and its inverse are the same.

How can you find the modular inverse of a negative number modulo M?

You can find the modular inverse of a negative number modulo 'M' by recognizing that the negative number is equivalent to a positive number modulo 'M'. For example, if you want to find the inverse of -2 modulo 19, you can see that -2 is equivalent to 17 modulo 19, and then find the inverse of 17.

What is the shortcut mentioned in the script for finding modular inverses?

The shortcut mentioned is to recognize that if a number 'a' is equivalent to a negative number modulo 'M', you can find the inverse of the negative number and then adjust it to be positive if necessary. For example, if 'a' is equivalent to -1 modulo 'M', then 'a' is its own inverse.

Why doesn't the number 5 have a modular inverse modulo 10?

The number 5 does not have a modular inverse modulo 10 because the greatest common divisor of 5 and 10 is 5, which is greater than one. This violates the condition that the GCD must be one for a modular inverse to exist.

Outlines

00:00

🔢 Modular Inverses Explained

The paragraph introduces the concept of modular inverses, which are pairs of numbers that when multiplied together give a product of 1 modulo M. It explains that a number 'a' has an inverse modulo M if the greatest common divisor (GCD) of 'a' and 'M' is 1. If the GCD is greater than 1, there is no modular inverse. The paragraph provides examples to demonstrate how to find the inverse of a number modulo another number, such as finding the inverse of 5 modulo 7 and modulo 11, and explains that if the GCD is not 1, no inverse exists, as illustrated with the inverse of 5 modulo 10.

Keywords

💡Modular Inverses

Modular inverses refer to the concept of finding a number that, when multiplied by another given number, results in a product that is congruent to 1 modulo a third number (M). This is central to the video's theme as it discusses methods for finding such inverses. For example, the script explains how to find the inverse of 5 modulo 7, which is 3, because 5 * 3 ≡ 1 (mod 7).

💡Multiplicative Inverses

Multiplicative inverses are numbers that, when multiplied with another number, yield the multiplicative identity, which is 1 in the context of modular arithmetic. The video emphasizes that these are the same as modular inverses, and they are essential for solving congruences, as demonstrated with the example of finding the inverse of 5 mod 7.

💡Greatest Common Divisor (GCD)

The greatest common divisor of two numbers is the largest number that divides both of them without leaving a remainder. The video explains that a number 'a' has an inverse modulo 'M' if and only if the GCD of 'a' and 'M' is 1. This is a critical condition for the existence of a modular inverse, as shown when discussing why 5 does not have an inverse modulo 10 due to their GCD being 5.

💡Congruences

Congruences are equations that involve the concept of equivalence under a modulo operation. The video uses the term to describe the process of finding modular inverses, as it involves setting up and solving equations of the form 'a * x ≡ 1 (mod M)', where 'x' is the modular inverse of 'a' modulo 'M'.

💡Modulo Operation

The modulo operation, often denoted as 'mod', is a mathematical operation that finds the remainder after division of one number by another. The script uses this operation extensively when explaining how to calculate modular inverses, such as finding the inverse of 5 mod 11 by repeatedly adding 11 until a multiple of 5 is found that gives a remainder of 1 when divided by 11.

💡Inverse of a Number

The inverse of a number, in the context of modular arithmetic, is a number that, when multiplied with the original number, results in 1 modulo 'M'. The video script provides several examples of finding such inverses, like the inverse of 5 mod 11 being 9, because 5 * 9 ≡ 1 (mod 11).

💡Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers 'wrap around' upon reaching a certain value called the modulus. The video's main theme revolves around this concept, as it discusses finding modular inverses, which are integral to many cryptographic algorithms and number theory problems.

💡Negative Numbers in Modular Arithmetic

The video script touches upon the concept of negative numbers in modular arithmetic, explaining that they can be treated as positive numbers by adding or subtracting the modulus. For instance, -1 mod 19 is equivalent to 18, and thus 18 is its own inverse because 18 * 18 ≡ 1 (mod 19).

💡Shortcut for Finding Inverses

The script introduces a shortcut for finding modular inverses when a number is equivalent to a negative number modulo 'M'. It uses the example of finding the inverse of 18 mod 19, where recognizing that 18 is equivalent to -1 mod 19 simplifies the process since -1's inverse is also -1.

💡No Inverse Scenario

The video explains that if the greatest common divisor of 'a' and 'M' is greater than 1, then 'a' does not have an inverse modulo 'M'. This is illustrated with the example of trying to find the inverse of 5 mod 10, which is impossible because their GCD is 5, not 1.

Highlights

Definition of multiplicative inverses: two numbers that multiply together to get one mod M

A has an inverse mod M if and only if the greatest common divisor of a and M is equal to one

If the greatest common divisor between a and M is greater than one, there is no inverse mod M

Example of finding the inverse of 5 mod 7, which is 3

Notation for inverse: 5 inverse is congruent to 3 mod 7

Finding the inverse of 5 mod 11, which is 9

Finding the inverse of 6 mod 17, which is 3

Finding the inverse of 18 mod 19, which is 18

Shortcut for finding inverse when the number is equivalent to negative 1 mod M

Example of inverse of negative 2 mod 19, which is negative 10

Inverse of negative 2 is congruent to 9 mod 19

If the greatest common divisor of two values is greater than one, there is no inverse

Example of no inverse for 5 mod 10 due to a greatest common divisor of five

Practical application of modular inverses in solving congruences

The importance of the theorem for determining the existence of modular inverses

Methodology for finding modular inverses through iterative addition and subtraction

Concept of using negative numbers to simplify finding modular inverses

Practical example of finding the inverse of 1790 mod 19

Explanation of why certain numbers do not have modular inverses

Transcripts

modular inverses please pause the video

and read the definition and then we'll

talk about it so we're finding

multiplicative inverses and that's two

numbers that multiply together to get

you one mod M we were really finding

multiplicative inverses in the last

video when we were solving many or

congruences we just didn't give them

that name and this theorem is important

a has an inverse mod M if and only if

the greatest common divisor of a and M

is equal to one if the greatest common

divisor between a and M is greater than

one then there is no inverse mod M so

let's take a look at some examples

suppose we want to find the inverse of 5

mod 7 that's going asking us to find

what we can multiply 5 by to get 1 mod 7

so we do as we've done in the past mod 7

1 is congruent to 8 that's not a

multiple of 5 so we add 7 again and we

get 15 15 is 5 times 3 mod 7 so 3 is the

inverse of 5 mod 7 a notation we'll

write 5 inverse is congruent to 3 mod 7

now pause the video and you try this one

find the inverse of 5 mod 11 so

hopefully you said one was congruent to

12 model evan with 1 and add the mod on

congruent to 23 adding 1134 and

eventually we get to 45 and that's 5

times 9 mod 11 so the inverse of 5 is

congratulate my 11 again if you feel

comfortable pause the video and try this

one

so you've got one congruent to 18

because we're adding 17 this time and

that's 6 times 3 mod 17 so 6 inverse is

congruent to 3 mod 17 now we want to

find the inverse of 18 mod 19 now we

want to find the inverse of 18 mod 19 so

we could do 1 is congruent to 20 and

that's not a multiple of 18

is congruent to adding 19 we get 39 and

then we get 58 and then we get 77 still

no multiples of 18 eventually if you

keep adding on you're going to get up to

324 which is 18 times 18 so 18 inverse

is 18 okay so that will always work but

sometimes you end up spending a lot of

time trying to find the inverse and

there's a little bit of a shortcut you

can do for this problem if you realize

that 18 is the same thing as negative 1

mod 19 we're used to adding adding 19

but we can subtract 19 as well what's

the inverse of negative 1 well we

multiply negative 1 to get positive by

positive 1 that's negative 1 right 1 is

the same thing as negative 1 times

negative 1 and since 18 is negative 1 18

is its own inverse okay it would work

the same way let's suppose I asked you

to find the inverse of 1790 17 is the

same thing as negative 2 mod 19 all

right if I had 19 2 negative 2 I get 17

looking back up here 20 is negative 2

times negative 10 so negative 2 the

inverse of negative 2 is negative 10 mod

19 negative 2 adding 19 gives us 17 so

the inverse of 17 is congruent to I'm

going to add 19 to that negative 10

because I want positive numbers is equal

to 9 mod 19 okay if you did this a long

way eventually you would get up to in

your list of congruences up here 17

times 9 which would be 153 so you get

there it just takes a little bit longer

ok so now what if I was asked to find

the inverse of 5 mod 10 you could start

chugging along and add 10 to 1 and you

get 11 and 21 and 31

and you could spend the rest of your

life adding ten to one or multiples of

one and you would never get a multiple

of five so what's the problem here

well the problem is that the greatest

common divisor of five and ten is five

which is not one so the answer is that

there is no inverse so if there's a

greatest common divisor greater than one

between those two values then there is

no inverse so I hope that helps and I

think you're ready to practice so have a

great day

[Music]