1 00:00:00,000 --> 00:00:04,766 Hello everyone. Welcome to week 7 of Carmen's 
Core Concepts, my name is Carmen Bruni, 2 00:00:04,766 --> 00:00:08,833 and in this video series, specifically for Math 135, 3 00:00:08,833 --> 00:00:11,400 we talk about what 
we did in week 7 4 00:00:11,400 --> 00:00:14,266 of this week's content for the 5 00:00:14,266 --> 00:00:17,900 first-year algebra course 
at the University of Waterloo. 6 00:00:17,900 --> 00:00:20,600 Congruence definition. So as you 
notice there's nothing on the page. 7 00:00:20,600 --> 00:00:24,000 What I'd like you to do now is actually 
take out a piece of paper and a pencil, 8 00:00:24,000 --> 00:00:27,700 pause the video, and try to remember 
the definition of congruence. 9 00:00:27,700 --> 00:00:28,633 10 00:00:28,633 --> 00:00:31,066 This needs to be 
something that you know. 11 00:00:31,066 --> 00:00:36,000 What does it mean for two integers to be 
congruent modulo n for some natural number n? 12 00:00:36,000 --> 00:00:39,366 This is a definition that 
you need to have down, 13 00:00:39,366 --> 00:00:43,233 just like you do with an equal sign. You 
don't really think when you write down, 14 00:00:43,233 --> 00:00:45,900 you know, x equals 2. You 
know what that means, 15 00:00:45,900 --> 00:00:49,600 you don't have to pause and parse the statement, you just know. 16 00:00:49,600 --> 00:00:51,266 And in the same sort of sense… 17 00:00:51,266 --> 00:00:54,966 in the same sort of way, congruences 
have to fall into that feeling. 18 00:00:54,966 --> 00:00:58,400 They have to just be something that you're 
very comfortable with manipulating. 19 00:00:58,400 --> 00:01:01,200 So now hopefully you've 
written down the definition. 20 00:01:01,200 --> 00:01:03,033 If not, here it is. 21 00:01:03,033 --> 00:01:05,100 So let a and b be integers 
and n a natural number, 22 00:01:05,100 --> 00:01:08,733 then a is congruent to b modulo n 
if and only if n divides a minus b, 23 00:01:08,733 --> 00:01:11,700 and we write a is 
congruent to b mod n. 24 00:01:11,700 --> 00:01:13,733 This is equivalent to saying 
there's an integer k 25 00:01:13,733 --> 00:01:16,000 such that a minus b 
is equal to k times n, 26 00:01:16,000 --> 00:01:17,866 or a equals b plus k n. 27 00:01:17,866 --> 00:01:21,666 Again this is just unwinding the definition 
of divisibility, so there's nothing new there. 28 00:01:21,666 --> 00:01:24,633 Some examples: 5 is 
congruent to 11 mod 6 29 00:01:24,633 --> 00:01:28,933 because 5 minus 11 is negative 
6 and 6 divides negative 6. 30 00:01:28,933 --> 00:01:32,633 Similarly 723 is congruent to 
negative 17 mod 20 because 31 00:01:32,633 --> 00:01:37,733 723 minus negative 17 is 740 and that’s divisible by 20. 32 00:01:37,733 --> 00:01:39,366 33 00:01:39,366 --> 00:01:41,733 One way I like to think of of moduli 34 00:01:41,733 --> 00:01:45,633 like this, is that I like to think 
of the 6 and the 20 as being 0, 35 00:01:45,633 --> 00:01:47,900 and we'll see more of this, 36 00:01:47,900 --> 00:01:51,866 or why that's true, or how that's true 
in a couple of the following theorems, 37 00:01:51,866 --> 00:01:55,733 but in that sense well because - so 
in that sense thinking of 6 as being 0, 38 00:01:55,733 --> 00:01:58,200 well I can always add and 
subtract 0. So for example, 39 00:01:58,200 --> 00:02:01,233 11 is the same as 11 
minus 6 which is 5, 40 00:02:01,233 --> 00:02:04,800 or it's the same as 11 plus 6 which 
is 17, and so on and so forth. 41 00:02:04,800 --> 00:02:06,833 So that's what I mean by I 
like to think of 6 as being 42 00:02:06,833 --> 00:02:09,133 0 in these cases, 
and 20 as being 0. 43 00:02:09,133 --> 00:02:12,000 I find that it helps me out a lot when 
doing computations and things like that 44 00:02:12,000 --> 00:02:14,000 so it's something, 
if it helps you out, 45 00:02:14,000 --> 00:02:16,800 go with it, and if not then 
forget I ever said it. 46 00:02:16,800 --> 00:02:19,166 47 00:02:19,166 --> 00:02:21,700 Congruence is an equivalence relation. So this is the 48 00:02:21,700 --> 00:02:23,533 first theorem that we 
have with congruences, 49 00:02:23,533 --> 00:02:25,600 and it's actually a 50 00:02:25,600 --> 00:02:29,333 more general thing. An equivalence 
relation is something that satisfies these 3 51 00:02:29,333 --> 00:02:32,666 properties, there's a relation that 
satisfies these 3 properties: 52 00:02:32,666 --> 00:02:35,200 it's reflexive, symmetric, and transitive. 53 00:02:35,200 --> 00:02:36,800 So a is congruent to a mod n, 54 00:02:36,800 --> 00:02:39,833 a is congruent to b mod n implies 
that b is congruent to a mod n, 55 00:02:39,833 --> 00:02:42,366 that's the symmetry, 
we flip the a and b, 56 00:02:42,366 --> 00:02:45,766 and transitivity, if a is congruent to b 
mod n, and b is congruent to c mod n, 57 00:02:45,766 --> 00:02:47,933 then a is congruent to c mod n. 58 00:02:47,933 --> 00:02:48,700 59 00:02:48,700 --> 00:02:51,333 Now something to note, or to 
recall, right, remember we had 60 00:02:51,333 --> 00:02:56,000 Transitivity of Divisibility: if a divides 
b and b divides c, then a divides c, 61 00:02:56,000 --> 00:02:57,033 62 00:02:57,033 --> 00:02:58,933 and this has that same feeling. 63 00:02:58,933 --> 00:03:02,866 a is congruent to b, b is congruent 
to c implies that a is congruent to c. 64 00:03:02,866 --> 00:03:06,333 Notice that the equal signs, 
just normal ordinary equals, 65 00:03:06,333 --> 00:03:09,633 is also an equivalence relation, that's where this name comes from 66 00:03:09,633 --> 00:03:10,566 67 00:03:10,566 --> 00:03:13,400 And these are the 3 properties that 
an equivalence relation must satisfy. 68 00:03:13,400 --> 00:03:16,933 So these are emulating equals… 69 00:03:16,933 --> 00:03:20,700 these properties emulate equals 
in the way that you want it… 70 00:03:20,700 --> 00:03:23,833 in the way that you want it to 
basically is what this is trying to say. 71 00:03:23,833 --> 00:03:25,466 72 00:03:25,466 --> 00:03:27,266 So it's great, so congruence 
is an equivalence relation. 73 00:03:27,266 --> 00:03:29,333 Again these proofs are… 74 00:03:29,333 --> 00:03:32,333 these proofs are actually relatively straightforward, 
and you should be able to do them 75 00:03:32,333 --> 00:03:33,133 76 00:03:33,133 --> 00:03:35,600 without me showing you. I'm 
actually not going to show you. 77 00:03:35,600 --> 00:03:37,800 That's something that you can do… 78 00:03:37,800 --> 00:03:40,533 it's not hard and I 
encourage you to do it. 79 00:03:40,533 --> 00:03:42,466 80 00:03:42,466 --> 00:03:44,633 Next we have properties of congruences. 81 00:03:44,633 --> 00:03:48,000 Again, same sort of idea 82 00:03:48,000 --> 00:03:50,666 with the fact that like these 
proofs are not too hard, 83 00:03:50,666 --> 00:03:51,733 84 00:03:51,733 --> 00:03:54,766 but, again, I won't 
show them to you 85 00:03:54,766 --> 00:03:57,500 here. Again you can check the notes if you'd like to see them. 86 00:03:57,500 --> 00:04:00,733 Let a, a prime, b, b 
prime be integers. 87 00:04:00,733 --> 00:04:04,166 If a is congruent to a prime mod m, 
and b is congruent to b prime mod m, 88 00:04:04,166 --> 00:04:06,533 then their sums are congruent mod m, 89 00:04:06,533 --> 00:04:08,166 their differences are 
congruent mod m, 90 00:04:08,166 --> 00:04:10,033 and their products 
are congruent mod m. 91 00:04:10,033 --> 00:04:11,666 92 00:04:11,666 --> 00:04:13,633 Again, it's not hard, you can 
actually prove all of these 93 00:04:13,633 --> 00:04:16,633 by using some combination of DIC. 94 00:04:16,633 --> 00:04:20,933 So again I recommend you do it, but I'm not 
going to do it here. It's a good exercise to do. 95 00:04:20,933 --> 00:04:23,666 As a corollary, if a is 
congruent to b mod m, then 96 00:04:23,666 --> 00:04:25,600 a to the k is congruent 
to b to the k mod m. 97 00:04:25,600 --> 00:04:27,833 This corollary is the one that 
I actually use the most. 98 00:04:27,833 --> 00:04:29,900 Follows immediately from 3, 99 00:04:29,900 --> 00:04:33,366 you just take a and b to be the same, and a prime and b prime to be the same, 100 00:04:33,366 --> 00:04:35,900 and if you really want to be 
pedantic, you would prove this by 101 00:04:35,900 --> 00:04:39,466 using induction on the natural numbers. Not going to do it. 102 00:04:39,466 --> 00:04:40,233 103 00:04:40,233 --> 00:04:41,766 It's not hard, but… 104 00:04:41,766 --> 00:04:46,600 and then the corollary is the thing that I 
use the most. I think I like this the most 105 00:04:46,600 --> 00:04:50,233 of the properties of congruences 
that we have here. 106 00:04:50,233 --> 00:04:51,800 107 00:04:51,800 --> 00:04:54,533 Okay that's great, and again 
so what is this saying? 108 00:04:54,533 --> 00:04:58,933 This is saying that congruence basically 
behaves the way you want it to. 109 00:04:58,933 --> 00:05:01,266 In the sense of like all these things 
you could do with equal signs, 110 00:05:01,266 --> 00:05:02,833 you can also do 
them with congruences, 111 00:05:02,833 --> 00:05:05,500 and that's sort of the idea here, 
right, is to make congruences 112 00:05:05,500 --> 00:05:08,900 feel as much as equals as we possibly can. 113 00:05:08,900 --> 00:05:11,166 Again it's not the same 
as equals, remember that 114 00:05:11,166 --> 00:05:13,800 a is congruent to a prime 
mod m if and only if 115 00:05:13,800 --> 00:05:16,400 m divides the difference, 
right? That's what it means. 116 00:05:16,400 --> 00:05:17,600 117 00:05:17,600 --> 00:05:20,000 But again we have that same feeling. You want to put 118 00:05:20,000 --> 00:05:24,133 congruence in that same class of things 
as you have with your equal sign, okay? 119 00:05:24,133 --> 00:05:26,000 You want to be that familiar with it. 120 00:05:26,000 --> 00:05:28,000 121 00:05:28,000 --> 00:05:29,900 Let's take a look at an example. 122 00:05:29,900 --> 00:05:35,000 Is 5 to the 9 plus 62 to to the 
2000 minus 14 divisible by 7? 123 00:05:35,000 --> 00:05:37,700 So again, stop the video 
here, actually give this a shot. 124 00:05:37,700 --> 00:05:41,333 It's not too hard. hopefully you can 
make some progress on it on your own. 125 00:05:41,333 --> 00:05:43,466 But do pause the video, try it. 126 00:05:43,466 --> 00:05:44,800 And now that you're back, 127 00:05:44,800 --> 00:05:46,066 128 00:05:46,066 --> 00:05:48,200 let's talk about this. What does 
it mean to be divisible by 7? 129 00:05:48,200 --> 00:05:50,766 Well it means that you’re 
congruent to 0 mod 7. 130 00:05:50,766 --> 00:05:53,566 So that's what we're going to do. 
We're going to look at this mod 7, 131 00:05:53,566 --> 00:05:54,900 132 00:05:54,900 --> 00:05:56,633 and these numbers so… 133 00:05:56,633 --> 00:05:59,533 when you see these 
numbers, the exponents look 134 00:05:59,533 --> 00:06:01,833 big and scary, but 
usually there's ways to 135 00:06:01,833 --> 00:06:04,500 simplify the computations, 
which we'll see in a second. 136 00:06:04,500 --> 00:06:07,366 And one of the ways that I like to 
do this is actually instead of using 137 00:06:07,366 --> 00:06:12,133 the 5 and the 62, sometimes I like to go to 
the negative number that's equivalent to it. 138 00:06:12,133 --> 00:06:13,700 So... 139 00:06:13,700 --> 00:06:17,333 for example, 5 is equivalent 
to negative 2 mod 7, 140 00:06:17,333 --> 00:06:19,700 and negative 2 to the 9, 
that's actually not too hard. 141 00:06:19,700 --> 00:06:23,200 Negative 2 to the 
9 is negative 512, 142 00:06:23,200 --> 00:06:25,866 and then from there I can try to 
figure out the remainder when I 143 00:06:25,866 --> 00:06:28,533 try to reduce it mod 7. 144 00:06:28,533 --> 00:06:29,366 145 00:06:29,366 --> 00:06:32,433 That's something you can do and we'll 
see a couple of other tricks in a minute 146 00:06:32,433 --> 00:06:34,200 of how to deal with the 
negative 2 to the 9, 147 00:06:34,200 --> 00:06:37,266 but that usually is an 
easier computation 148 00:06:37,266 --> 00:06:40,233 because in size 2 is 
smaller than 5, right? 149 00:06:40,233 --> 00:06:44,800 Same with 62, 62 is actually really 
close to a multiple of 7, namely 63, 150 00:06:44,800 --> 00:06:47,800 so 62 will reduce to 6 mod 7, 151 00:06:47,800 --> 00:06:50,633 and if you think about it, 6 
is a little hard so if you… 152 00:06:50,633 --> 00:06:53,566 well 6 is a little bit big to 
deal with, but if you take 153 00:06:53,566 --> 00:06:56,300 one more 7 away from 
it, you get negative 1, 154 00:06:56,300 --> 00:06:58,066 so 62 is the same 
as minus 1, so 155 00:06:58,066 --> 00:07:01,233 62 to the 2000 is the same 
as minus 1 to the 2000. 156 00:07:01,233 --> 00:07:02,933 That's really easy to deal with. 157 00:07:02,933 --> 00:07:05,466 So let's take a look at the 158 00:07:05,466 --> 00:07:06,166 159 00:07:06,166 --> 00:07:08,533 computation based on all that. 160 00:07:08,533 --> 00:07:09,633 161 00:07:09,633 --> 00:07:13,400 So that first line is exactly what we 
said, so 5 is the same as minus 2. 162 00:07:13,400 --> 00:07:15,500 And again 62 is the 
same as minus 1. 163 00:07:15,500 --> 00:07:18,300 Another way to see this, by the way, of 
course is just directly using the definition. 164 00:07:18,300 --> 00:07:21,133 62 is congruent to minus 1 mod 7, 165 00:07:21,133 --> 00:07:25,233 since 62 minus negative 
1 is 63, and 7 divides 63. 166 00:07:25,233 --> 00:07:28,366 So that’s one way to see it. 
And 14 is going to be 0 mod 7 167 00:07:28,366 --> 00:07:32,300 because 7 divides 14, so 
those two things are equal. 168 00:07:32,300 --> 00:07:35,000 Now from here, it's actually not too bad. Negative 1 to the 2000 169 00:07:35,000 --> 00:07:36,933 is really easy to do, that's just 1, 170 00:07:36,933 --> 00:07:40,600 and negative 2 to the power of 9, that's 
just negative 2 to the power of 9, 171 00:07:40,600 --> 00:07:44,266 right, I can pull the negative out because 
negative 1 to the 9 is negative 1. 172 00:07:44,266 --> 00:07:45,100 173 00:07:45,100 --> 00:07:48,533 Now 2 to the 9, again we can 
just evaluate it and simplify it, 174 00:07:48,533 --> 00:07:52,000 or we can do this little trick 
and write it as 2 cubed cubed. 175 00:07:52,000 --> 00:07:55,433 I love to find these 
little arithmetic tricks 176 00:07:55,433 --> 00:07:57,900 when solving these types of problems. 
I encourage you to do it too. 177 00:07:57,900 --> 00:08:00,833 There's lots of room to be 
creative in Number Theory 178 00:08:00,833 --> 00:08:03,433 when writing a proof and 
I encourage students 179 00:08:03,433 --> 00:08:06,366 to actually be creative 
and to try to find 180 00:08:06,366 --> 00:08:08,600 multiple ways to solve a problem. 181 00:08:08,600 --> 00:08:11,300 That often shows that you've 
actually mastered the material 182 00:08:11,300 --> 00:08:13,366 if you can solve it in 
3 or 4 different ways. 183 00:08:13,366 --> 00:08:14,433 184 00:08:14,433 --> 00:08:15,933 So here I have 
2 cubed cubed, 185 00:08:15,933 --> 00:08:18,866 2 cubed is 8, and 8 is 
the same as 1 mod 7. 186 00:08:18,866 --> 00:08:23,466 Again, why? Because 8 minus 
1 is divisible by 7, right? 187 00:08:23,466 --> 00:08:26,333 So if 8 is the same as 1, then 8 
cubed is the same as 1 cubed. 188 00:08:26,333 --> 00:08:28,900 That's the corollary to 
Properties of Congruences. 189 00:08:28,900 --> 00:08:32,000 So notice that I don't have Properties of Congruences 190 00:08:32,000 --> 00:08:34,600 written at every step, I just 
wrote it at the beginning. 191 00:08:34,600 --> 00:08:37,866 Usually with computations, we 
don't write every single time 192 00:08:37,866 --> 00:08:42,133 we use Property of Congruences, or 
equivalence relations and things like that. 193 00:08:42,133 --> 00:08:45,066 I mean if you think about it, like with equal 
sign, you don't write them all down, so 194 00:08:45,066 --> 00:08:48,066 why would you write them down with 
congruence that I'm trying to convince you 195 00:08:48,066 --> 00:08:51,966 to put in that same class as equal signs, 
right? So something to think about. 196 00:08:51,966 --> 00:08:52,900 197 00:08:52,900 --> 00:08:56,300 So we do the computation, we 
eventually get minus 1 plus 1 that's 0. 198 00:08:56,300 --> 00:08:59,333 There should be a mod 7 here, 
I've just forgot to write it down. 199 00:08:59,333 --> 00:09:01,866 So it's congruent to 0 mod 7. 200 00:09:01,866 --> 00:09:04,700 And so what does that mean? So I have 
this number, did a bunch of computation, 201 00:09:04,700 --> 00:09:06,833 I show that it's congruent to 0 mod 7. 202 00:09:06,833 --> 00:09:10,600 By definition, that means that this number 
must be divisible by 7, and that's it. 203 00:09:10,600 --> 00:09:12,066 204 00:09:12,066 --> 00:09:15,533 So here's a way to use congruences 
to solve a divisibility problem 205 00:09:15,533 --> 00:09:17,633 fairly neatly and fairly quickly, 206 00:09:17,633 --> 00:09:20,666 and notice that we didn't actually need to compute what this gigantic number was. 207 00:09:20,666 --> 00:09:23,799 We just needed to evaluate it 
mod 7, which is pretty neat.