Simplifying congruences. This is the last thing I want to mention now. This is something that
I found myself just doing haphazardly,
because to me, it seems very clear but
the first time you see it, it might not be so clear.
Let's take a look at this: if x is congruent to 2 or 5 mod 6,
then x is congruent to 2 mod 3 gives the same solution set.
So the integers that satisfy x is congruent to 2 or 5 mod 6,
is the same as the integers that satisfy x is congruent to 2 mod 3.
Pause the video, think about this, give this a shot, okay?
And now that you're back, let's actually think about
why this might be the case.
It turns out it's not… too bad, but it's something that you should think about once,
and try to reason to yourself why this actually holds.
Let's kind of go through the proof. I mean that's probably the best way to see
is just to stumble through the proof here.
So let's look at if x is congruent to 2 or 5 mod 6,
then x is equal to 2 plus 6k or x is equal to 5 plus 6k for some integer k.
That's one of the ways we can interpret a congruence.
So in either case, let's think about it. So if I
bring the 2 over, then I'm going to get x minus 2 equals 6k
and 3 divides 6k, so therefore 3 must divide x minus 2.
And by similar logic, 3 must divide x minus 5, whichever one of these cases is true.
So either x is congruent to 2 mod 3, or x is congruent to 5,
which is the same as 2, mod 3. So that's something…
that's maybe the easy direction, right? So
if you see 2 and 5 mod 6 and I reduce it mod 3,
well 5 is the same as 2 mod 3, so x is congruent to
2 mod 3 gives the same solution sets.
If x is congruent to 2 or 5 mod 6.
Going the other way, it's almost like you're lifting now.
So now you have a solution mod 3, and you want to know what happens mod 6.
And it turns out, you get one of two cases:
x is either congruent to 2, or it's congruent to 5.
One way to see this quickly, right, take 2 and just keep adding 3.
So 2, 5, 5 is different than 2 mod 6,
if I add 3 again, I get 8, but 8 is the same as 2 mod 6.
If I add 3 again I get 11, well 11 is the same as 5 mod 6,
and you keep going in this like cyclical pattern.
But how does this really work formally?
So if x is congruent to 2 mod 3, then x is equal to 2 plus 3k for some integer k.
Now if you look at 6 divided by 3 is 2,
so if you look at the remainder of k when I divide by 2,
we're going to get some information that we want.
If the remainder is 0, then k is equal to 2 times l for some integer l,
and hence x is equal to 2 plus 6l,
which is the same as x is congruent to 2.
If the remainder is 1, then I'm going to write k as 2l plus 1,
for some integer l, and plug it in I'm going to get
x equals 2 plus 3 times 2l plus 1,
and what does that give you? Well if I expand this out, it's
going to be 2 plus 3 which is 5, and 3 times 2 which is 6l,
and thus what do I have? I have x is equal to 5 plus 6l
and that’s the same as x is congruent to 5 mod 6.
So hopefully, once you've seen this once, you'll be able to
go back and forth. If I change the 6 and the 3 to other numbers,
you should be able to go very quickly.
Something to try out, what if I have x is congruent to…I don’t know…
6 mod 7,
then what are my solutions mod 28?
Maybe that's something you might want to try and test yourself,
make sure that you can quickly come up with the answer.
You shouldn't need to do this argument here.
I'm only including it once just so that, you know,
because this is your first time seeing congruences,
this stuff might be coming at you fast and furious,
and you might want to take a minute to ground yourself
and be like, “Okay, why is this true?” Make sure you know the basics before you start
building - remember you don't want to build like a house
on a weak foundation, right, that doesn't work.
If your foundation’s weak, your house is going to collapse on itself.
So make sure that your foundation is strong, that you know these little facts,
so that if you do need to prove them in a pinch, you actually can justify them
to yourself.
So that's all I really want to say in part 1.
Again I do have part 2 separate just because
it's a bigger topic. I do a couple more abstract things in the other video
that I wanted to isolate from this video.
So I left that on the side.
But that's basically it. So thank you very much for listening,
hopefully this gave you some insight into congruences
and helped summarize
the thickness that is becoming Math 135. The course is getting…
there's a lot of stuff in the course now, so
it's very easy to get overwhelmed. Just, you know,
relax, take a couple of minutes. Try
to practice memorizing, or maybe not memorizing is the right word, but
make sure that you know these things. Recall these theorems to yourself.
You're on the bus, try to think, “Okay what did we do this week?
What theorems are there? What do they mean? When can I use them?”
These are things that you should be constantly reminding yourself
as you, you know,
as you go about your day. Just little, you know, little tests.
Test yourself along the day, make sure you know where
we are in the course and what we're doing.
That'll help you out in the long term and it'll make studying and things and
learning this course a lot easier.
So that's it. Thank you very much your time.