1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:04,766 Simplifying congruences. This is the last thing I 
want to mention now. This is something that 3 00:00:04,766 --> 00:00:08,700 I found myself just 
doing haphazardly, 4 00:00:08,700 --> 00:00:11,766 because to me, it seems very clear but 5 00:00:11,766 --> 00:00:14,800 the first time you see it, 
it might not be so clear. 6 00:00:14,800 --> 00:00:16,366 7 00:00:16,366 --> 00:00:19,666 Let's take a look at this: if x 
is congruent to 2 or 5 mod 6, 8 00:00:19,666 --> 00:00:22,233 then x is congruent to 2 mod 3 
gives the same solution set. 9 00:00:22,233 --> 00:00:25,966 So the integers that satisfy x 
is congruent to 2 or 5 mod 6, 10 00:00:25,966 --> 00:00:30,833 is the same as the integers that 
satisfy x is congruent to 2 mod 3. 11 00:00:30,833 --> 00:00:34,266 Pause the video, think about 
this, give this a shot, okay? 12 00:00:34,266 --> 00:00:34,966 13 00:00:34,966 --> 00:00:37,600 And now that you're back, 
let's actually think about 14 00:00:37,600 --> 00:00:39,666 why this might be the case. 15 00:00:39,666 --> 00:00:41,766 16 00:00:41,766 --> 00:00:46,733 It turns out it's not… too bad, but it's 
something that you should think about once, 17 00:00:46,733 --> 00:00:49,900 and try to reason to yourself 
why this actually holds. 18 00:00:49,900 --> 00:00:51,366 19 00:00:51,366 --> 00:00:54,066 Let's kind of go through the proof. I mean 
that's probably the best way to see 20 00:00:54,066 --> 00:00:56,666 is just to stumble 
through the proof here. 21 00:00:56,666 --> 00:00:59,433 So let's look at if x is congruent to 2 or 5 mod 6, 22 00:00:59,433 --> 00:01:03,666 then x is equal to 2 plus 6k or x is 
equal to 5 plus 6k for some integer k. 23 00:01:03,666 --> 00:01:07,933 That's one of the ways we 
can interpret a congruence. 24 00:01:07,933 --> 00:01:08,866 25 00:01:08,866 --> 00:01:10,800 So in either case, let's 
think about it. So if I 26 00:01:10,800 --> 00:01:14,300 bring the 2 over, then I'm going 
to get x minus 2 equals 6k 27 00:01:14,300 --> 00:01:18,433 and 3 divides 6k, so therefore 
3 must divide x minus 2. 28 00:01:18,433 --> 00:01:23,466 And by similar logic, 3 must divide x minus 
5, whichever one of these cases is true. 29 00:01:23,466 --> 00:01:24,300 30 00:01:24,300 --> 00:01:27,633 So either x is congruent to 2 
mod 3, or x is congruent to 5, 31 00:01:27,633 --> 00:01:31,033 which is the same as 2, 
mod 3. So that's something… 32 00:01:31,033 --> 00:01:33,133 that's maybe the easy 
direction, right? So 33 00:01:33,133 --> 00:01:36,466 if you see 2 and 5 mod 6 
and I reduce it mod 3, 34 00:01:36,466 --> 00:01:39,166 well 5 is the same as 2 
mod 3, so x is congruent to 35 00:01:39,166 --> 00:01:41,233 2 mod 3 gives the 
same solution sets. 36 00:01:41,233 --> 00:01:42,200 37 00:01:42,200 --> 00:01:44,766 If x is congruent to 2 or 5 mod 6. 38 00:01:44,766 --> 00:01:47,033 Going the other way, it's 
almost like you're lifting now. 39 00:01:47,033 --> 00:01:51,233 So now you have a solution mod 3, and 
you want to know what happens mod 6. 40 00:01:51,233 --> 00:01:52,833 And it turns out, you 
get one of two cases: 41 00:01:52,833 --> 00:01:56,166 x is either congruent to 
2, or it's congruent to 5. 42 00:01:56,166 --> 00:01:59,033 One way to see this quickly, right, 
take 2 and just keep adding 3. 43 00:01:59,033 --> 00:02:02,900 So 2, 5, 5 is different 
than 2 mod 6, 44 00:02:02,900 --> 00:02:06,233 if I add 3 again, I get 8, but 8 is the same as 2 mod 6. 45 00:02:06,233 --> 00:02:09,333 If I add 3 again I get 11, well 
11 is the same as 5 mod 6, 46 00:02:09,333 --> 00:02:13,166 and you keep going in 
this like cyclical pattern. 47 00:02:13,166 --> 00:02:15,666 But how does this 
really work formally? 48 00:02:15,666 --> 00:02:19,800 So if x is congruent to 2 mod 3, then x 
is equal to 2 plus 3k for some integer k. 49 00:02:19,800 --> 00:02:20,533 50 00:02:20,533 --> 00:02:22,933 Now if you look at 
6 divided by 3 is 2, 51 00:02:22,933 --> 00:02:25,666 so if you look at the remainder 
of k when I divide by 2, 52 00:02:25,666 --> 00:02:28,066 we're going to get some 
information that we want. 53 00:02:28,066 --> 00:02:31,400 If the remainder is 0, then k is equal 
to 2 times l for some integer l, 54 00:02:31,400 --> 00:02:34,266 and hence x is 
equal to 2 plus 6l, 55 00:02:34,266 --> 00:02:36,400 which is the same as 
x is congruent to 2. 56 00:02:36,400 --> 00:02:40,233 If the remainder is 1, then I'm 
going to write k as 2l plus 1, 57 00:02:40,233 --> 00:02:43,166 for some integer l, and 
plug it in I'm going to get 58 00:02:43,166 --> 00:02:46,900 x equals 2 plus 3 
times 2l plus 1, 59 00:02:46,900 --> 00:02:49,033 and what does that give you? 
Well if I expand this out, it's 60 00:02:49,033 --> 00:02:53,766 going to be 2 plus 3 which is 
5, and 3 times 2 which is 6l, 61 00:02:53,766 --> 00:02:54,566 62 00:02:54,566 --> 00:02:56,833 and thus what do I have? I 
have x is equal to 5 plus 6l 63 00:02:56,833 --> 00:02:59,133 and that’s the same as x 
is congruent to 5 mod 6. 64 00:02:59,133 --> 00:03:02,033 So hopefully, once you've seen 
this once, you'll be able to 65 00:03:02,033 --> 00:03:05,300 go back and forth. If I change the 
6 and the 3 to other numbers, 66 00:03:05,300 --> 00:03:07,200 you should be able to go very quickly. 67 00:03:07,200 --> 00:03:11,600 Something to try out, what if I have 
x is congruent to…I don’t know… 68 00:03:11,600 --> 00:03:13,266 6 mod 7, 69 00:03:13,266 --> 00:03:15,500 then what are my 
solutions mod 28? 70 00:03:15,500 --> 00:03:18,166 Maybe that's something you might 
want to try and test yourself, 71 00:03:18,166 --> 00:03:20,200 make sure that you can quickly 
come up with the answer. 72 00:03:20,200 --> 00:03:22,400 You shouldn't need to 
do this argument here. 73 00:03:22,400 --> 00:03:25,133 I'm only including it once just so that, you know, 74 00:03:25,133 --> 00:03:27,166 because this is your first 
time seeing congruences, 75 00:03:27,166 --> 00:03:29,766 this stuff might be coming 
at you fast and furious, 76 00:03:29,766 --> 00:03:32,466 and you might want to take a minute to ground yourself 77 00:03:32,466 --> 00:03:37,133 and be like, “Okay, why is this true?” Make 
sure you know the basics before you start 78 00:03:37,133 --> 00:03:39,166 building - remember you don't 
want to build like a house 79 00:03:39,166 --> 00:03:41,233 on a weak foundation, 
right, that doesn't work. 80 00:03:41,233 --> 00:03:43,400 If your foundation’s weak, your house is going to collapse on itself. 81 00:03:43,400 --> 00:03:46,466 So make sure that your foundation is 
strong, that you know these little facts, 82 00:03:46,466 --> 00:03:49,233 so that if you do need to prove them 
in a pinch, you actually can justify them 83 00:03:49,233 --> 00:03:50,800 to yourself. 84 00:03:50,800 --> 00:03:51,800 85 00:03:51,800 --> 00:03:54,400 So that's all I really 
want to say in part 1. 86 00:03:54,400 --> 00:03:55,833 87 00:03:55,833 --> 00:03:59,200 Again I do have part 
2 separate just because 88 00:03:59,200 --> 00:04:03,733 it's a bigger topic. I do a couple more 
abstract things in the other video 89 00:04:03,733 --> 00:04:06,133 that I wanted to 
isolate from this video. 90 00:04:06,133 --> 00:04:06,866 that I wanted to 
isolate from this video. 91 00:04:06,866 --> 00:04:08,633 So I left that on the side. 92 00:04:08,633 --> 00:04:11,800 But that's basically it. So thank 
you very much for listening, 93 00:04:11,800 --> 00:04:14,666 hopefully this gave you some 
insight into congruences 94 00:04:14,666 --> 00:04:16,733 and helped summarize 95 00:04:16,733 --> 00:04:20,666 the thickness that is becoming 
Math 135. The course is getting… 96 00:04:20,666 --> 00:04:22,533 there's a lot of stuff in the course now, so 97 00:04:22,533 --> 00:04:24,866 it's very easy to get 
overwhelmed. Just, you know, 98 00:04:24,866 --> 00:04:28,366 relax, take a couple of minutes. Try 99 00:04:28,366 --> 00:04:31,900 to practice memorizing, or maybe 
not memorizing is the right word, but 100 00:04:31,900 --> 00:04:34,500 make sure that you know these things. 
Recall these theorems to yourself. 101 00:04:34,500 --> 00:04:37,333 You're on the bus, try to think, “Okay what did we do this week? 102 00:04:37,333 --> 00:04:40,200 What theorems are there? What do 
they mean? When can I use them?” 103 00:04:40,200 --> 00:04:43,500 These are things that you should 
be constantly reminding yourself 104 00:04:43,500 --> 00:04:44,833 as you, you know, 105 00:04:44,833 --> 00:04:45,666 106 00:04:45,666 --> 00:04:48,300 as you go about your day. Just little, you know, little tests. 107 00:04:48,300 --> 00:04:50,866 Test yourself along the day, 
make sure you know where 108 00:04:50,866 --> 00:04:52,933 we are in the course and what we're doing. 109 00:04:52,933 --> 00:04:56,000 That'll help you out in the long term 
and it'll make studying and things and 110 00:04:56,000 --> 00:04:58,233 learning this course a lot easier. 111 00:04:58,233 --> 00:05:00,499 So that's it. Thank you 
very much your time.