Hello everyone. Welcome to Week 8 of Carmen's Core Concepts.
My name is Carmen Bruni. In these video series, I go
through the content of the current week in Math 135,
and try to give you a brief overview of what we covered.
Again this isn't a substitute for lectures or anything like that,
it's going to be very quick.
The idea is to try to highlight the main points from the week,
and to help you remember everything.
I mean recalling things is very important in mathematics. So
hopefully these videos give you a good recall of what we did this week.
Let's start with the following proposition. So,
we haven't seen this acronym yet, TFAE:
"the following are equivalent".
So here we have a laundry list of things that are equivalent,
so a is congruent to b mod m, m divides a minus b,
there exists an integer k such that a minus b is equal to k m,
there exists an integer k such that a equals k m plus b,
a and b have the same remainder when divided by m,
(remember that this followed by Congruent If and Only If Same Remainder, CISR),
and then we have the equivalence class of a is equal to the equivalence class of b in Z mod m.
Again, all of these are equivalent.
One way to prove that things are equivalent
is to, let's say we number these, and you can prove that
so for example 1 implies 2, 2 implies 3, 3 implies 4,
4 implies 5, 5 implies 6, and 6 implies 1.
It's a very common way to do it, just prove everything is equal in a cycle.
Sometimes if certain ones are harder,
you might use if and only if statements so like 1 if and only if 2, and then
you prove that 1 implies 3, and 3 implies 4, and 4 implies 1,
something like that is also possible too.
Most of these are pretty straightforward though
so you don't need to do anything fancy to prove this.
And let me just give you a quick example, so for example solving
the equivalence class of 10 times the equivalence class of x
is equal to the equivalence class of 1 in Z mod m,
is the exact same as solving that 10x is congruent to 1 mod m.
So these two are related. So for example if you have difficulties
with this notation, bring it back down to 10x is congruent to 1 mod m,
bring it to this notation, and it should be a little bit easier.
Okay.
Inverses, so we spent a lot of time in the last
two weeks talking about rings and fields,
at least the general picture. We didn't talk
anything too, too specific but I wanted to give you a big
overview idea of what abstract algebra…
some of the objects in abstract algebra: rings and fields.
And so we saw that in a ring, we have to have additive inverses of elements, okay
and in the case of Z mod m, the additive inverse is very simple.
If you're dealing with the element 5 in Z mod m, the additive inverse is minus 5.
Now you might want to shift that, for example, to make it positive by adding m.
So you would have the equivalence class of m minus 5, which is the same
as the equivalence class of minus 5,
but either way is fine, and again remember that the additive inverse satisfies
the property that a plus minus a must be 0.
So whatever element this is
when I add it to a gives me 0, that's the additive inverse.
Now multiplicative inverses we saw,
and we'll deal with this in the next couple slides,
we saw that not all Z mod m have multiplicative inverses,
but when we do have it… so what is a multiplicative inverse?
Well if I multiply a by b, I get the multiplicative identity, 1,
just like when I added a and minus a I got the additive identity, 0.
So if there is an element b such that a times b is 1
and I've written down b times a here just in case,
in future courses, your ring might not be…
commutative. So you would have to at least examine both cases
until you show that inverses are unique and things like that.
Here these are the same thing but anyways,
a times b gives you 1, we call b the multiplicative inverse of a
and we write b is equal to a inverse, or sometimes we denote
b is congruent to a inverse mod m, okay? So
something to think about here. a inverse, when you look at this,
I don't - you should try to get away from thinking that this is 1 over a.
That’s going to take a little bit of time to used to because you've
thought about this as 1 over a your whole life,
but you should really be thinking of this as the
element when I multiply it to a, it gives me 1.
Now over the rational numbers let's say, that's
equivalent to 1 over a.
But in other rings like Z mod m where we don't really have a notion of
1 over a, you have to be a little bit careful.
So try to get yourself into that habit of rewiring your brain and saying,
“Hey okay, a inverse, that's this number when I multiply it by a gives me 1.”
Alright.
So again, multiplicative inverses. Multiplicative inverses don't always exist;
depends on the b, it depends on the m, and let's talk about that.
So a proposition, let a be an integer and m be a natural number.
Then the inverse of a exists in Z m if and only if
the gcd of a and m is 1,
and we'll see very quickly this follows from our Linear Congruence Theorem
work.
a inverse is unique if it exists
the last part of our proposition, okay?
So let's talk about this. So the multiplicative inverse of a exists if and only if
a times x equals 1, as equivalence classes,
is solvable in Z mod m.
But we can use the following…well we can -
I guess it's not really from “the following are equivalent”,
but when we do? We can translate this, I guess using a couple of things,
to the Linear Diophantine Equation that
a x plus m y equals 1 is solvable.
So here a and m are fixed and x and y vary over the integers.
So this has the solution if and only if a x is equal to 1 is solvable
in Z mod m.
This is from, this is actually from LCT, not LDE.
So LCT gives us that
this is solvable if and only if this is solvable.
Actually LCT1 and LDET2 are really the two things that are happening here
And then once we have this Linear Diophantine Equation, well we know
this has a solution if and only if the gcd of a and m is 1,
you can say by LDET1 or 2, or GCD Of One, all of these work.
This is going to complete the proof.
So what's the idea here? The idea here is that the inverse exists
if and only if this linear congruence is solvable,
and the linear congruence corresponds to a Linear Diophantine Equation,
and that we've done a couple of theorems of earlier in the course.
Now to prove that it's unique, remember that
if we want to prove that something is unique,
pretend that you have two elements that have the same property,
and then show that they must be equal.
So in this case, we have
that a inverse exists and we're going to suppose there's some
imposter element b that satisfies the same criteria.
Then what can we do? Well let's look at…what are we going to look at…
we're going to look at a b is equal to 1, and we're going to multiply both sides
by this inverse element, a inverse.
And if we do that, what do we notice? Well a inverse times 1, that's a inverse,
and a inverse times a well that's 1,
and 1 times anything is just the anything.
So here we see that b is equal to a inverse in Z mod m.
So the inverse is unique if it exists.
Okay so, key summary from this slide:
inverse is unique, so this notation makes sense.
I probably should've done 2 before 1, but that's okay.
The other thing that's important here is that the inverse exists
if and only if the gcd of my number and the modulus is 1.
So something to keep in mind. For example, if m were prime,
then all elements not divisible by p, would be invertible.
We actually call such things fields. So we say that Z mod p is a field.
We'll get to that in a couple of weeks again, but something to keep in mind for now.
So just rewording, so Linear Congruence Theorem 2, so this is just a quick slide.
We already have Linear Congruence Theorem 1,
and this is just the statement of Linear Congruence Theorem 1,
except in equivalence class notation.
Let a and c be integers and m a natural number.
Let the gcd of a and m be d, then the equation…
the equivalence class of a times the equivalence class of x
is equal to the equivalence class of c in Z mod m has a solution
if and only if
the gcd of a and m divides c,
and if you have one solution then you can find all solutions
by adding multiples of m over d.
How many multiples can we add to get unique elements?
Well we can add up to d minus 1 of them.
So we have x naught, x naught plus m over d, x naught plus 2m over d
and all the way up to x naught plus d minus 1 times m over d.