Finding Modular Inverses
Summary
TLDRThis 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
π’ 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.
Mindmap
Keywords
π‘Modular Inverses
π‘Multiplicative Inverses
π‘Greatest Common Divisor (GCD)
π‘Congruences
π‘Modulo Operation
π‘Inverse of a Number
π‘Modular Arithmetic
π‘Negative Numbers in Modular Arithmetic
π‘Shortcut for Finding Inverses
π‘No Inverse Scenario
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]
Browse More Related Video
Extended Euclidean Algorithm and Inverse Modulo Tutorial
Komposisi Fungsi Part 3 - Fungsi invers dan Sifat-sifatnya [ Matematika Wajib Kelas X ]
8.1 Hashing Techniques to Resolve Collision| Separate Chaining and Linear Probing | Data structure
Inverse Functions
Functions
ARITHMETIC MEANS OF A SEQUENCE || GRADE 10 MATHEMATICS Q1
5.0 / 5 (0 votes)