Hello everyone. Welcome to week 7 of Carmen's Core Concepts, my name is Carmen Bruni,
and in this video series, specifically for Math 135,
we talk about what we did in week 7
of this week's content for the
first-year algebra course at the University of Waterloo.
Congruence definition. So as you notice there's nothing on the page.
What I'd like you to do now is actually take out a piece of paper and a pencil,
pause the video, and try to remember the definition of congruence.
This needs to be something that you know.
What does it mean for two integers to be congruent modulo n for some natural number n?
This is a definition that you need to have down,
just like you do with an equal sign. You don't really think when you write down,
you know, x equals 2. You know what that means,
you don't have to pause and parse the statement, you just know.
And in the same sort of sense…
in the same sort of way, congruences have to fall into that feeling.
They have to just be something that you're very comfortable with manipulating.
So now hopefully you've written down the definition.
If not, here it is.
So let a and b be integers and n a natural number,
then a is congruent to b modulo n if and only if n divides a minus b,
and we write a is congruent to b mod n.
This is equivalent to saying there's an integer k
such that a minus b is equal to k times n,
or a equals b plus k n.
Again this is just unwinding the definition of divisibility, so there's nothing new there.
Some examples: 5 is congruent to 11 mod 6
because 5 minus 11 is negative 6 and 6 divides negative 6.
Similarly 723 is congruent to negative 17 mod 20 because
723 minus negative 17 is 740 and that’s divisible by 20.
One way I like to think of of moduli
like this, is that I like to think of the 6 and the 20 as being 0,
and we'll see more of this,
or why that's true, or how that's true in a couple of the following theorems,
but in that sense well because - so in that sense thinking of 6 as being 0,
well I can always add and subtract 0. So for example,
11 is the same as 11 minus 6 which is 5,
or it's the same as 11 plus 6 which is 17, and so on and so forth.
So that's what I mean by I like to think of 6 as being
0 in these cases, and 20 as being 0.
I find that it helps me out a lot when doing computations and things like that
so it's something, if it helps you out,
go with it, and if not then forget I ever said it.
Congruence is an equivalence relation. So this is the
first theorem that we have with congruences,
and it's actually a
more general thing. An equivalence relation is something that satisfies these 3
properties, there's a relation that satisfies these 3 properties:
it's reflexive, symmetric, and transitive.
So a is congruent to a mod n,
a is congruent to b mod n implies that b is congruent to a mod n,
that's the symmetry, we flip the a and b,
and transitivity, if a is congruent to b mod n, and b is congruent to c mod n,
then a is congruent to c mod n.
Now something to note, or to recall, right, remember we had
Transitivity of Divisibility: if a divides b and b divides c, then a divides c,
and this has that same feeling.
a is congruent to b, b is congruent to c implies that a is congruent to c.
Notice that the equal signs, just normal ordinary equals,
is also an equivalence relation, that's where this name comes from
And these are the 3 properties that an equivalence relation must satisfy.
So these are emulating equals…
these properties emulate equals in the way that you want it…
in the way that you want it to basically is what this is trying to say.
So it's great, so congruence is an equivalence relation.
Again these proofs are…
these proofs are actually relatively straightforward, and you should be able to do them
without me showing you. I'm actually not going to show you.
That's something that you can do…
it's not hard and I encourage you to do it.
Next we have properties of congruences.
Again, same sort of idea
with the fact that like these proofs are not too hard,
but, again, I won't show them to you
here. Again you can check the notes if you'd like to see them.
Let a, a prime, b, b prime be integers.
If a is congruent to a prime mod m, and b is congruent to b prime mod m,
then their sums are congruent mod m,
their differences are congruent mod m,
and their products are congruent mod m.
Again, it's not hard, you can actually prove all of these
by using some combination of DIC.
So again I recommend you do it, but I'm not going to do it here. It's a good exercise to do.
As a corollary, if a is congruent to b mod m, then
a to the k is congruent to b to the k mod m.
This corollary is the one that I actually use the most.
Follows immediately from 3,
you just take a and b to be the same, and a prime and b prime to be the same,
and if you really want to be pedantic, you would prove this by
using induction on the natural numbers. Not going to do it.
It's not hard, but…
and then the corollary is the thing that I use the most. I think I like this the most
of the properties of congruences that we have here.
Okay that's great, and again so what is this saying?
This is saying that congruence basically behaves the way you want it to.
In the sense of like all these things you could do with equal signs,
you can also do them with congruences,
and that's sort of the idea here, right, is to make congruences
feel as much as equals as we possibly can.
Again it's not the same as equals, remember that
a is congruent to a prime mod m if and only if
m divides the difference, right? That's what it means.
But again we have that same feeling. You want to put
congruence in that same class of things as you have with your equal sign, okay?
You want to be that familiar with it.
Let's take a look at an example.
Is 5 to the 9 plus 62 to to the 2000 minus 14 divisible by 7?
So again, stop the video here, actually give this a shot.
It's not too hard. hopefully you can make some progress on it on your own.
But do pause the video, try it.
And now that you're back,
let's talk about this. What does it mean to be divisible by 7?
Well it means that you’re congruent to 0 mod 7.
So that's what we're going to do. We're going to look at this mod 7,
and these numbers so…
when you see these numbers, the exponents look
big and scary, but usually there's ways to
simplify the computations, which we'll see in a second.
And one of the ways that I like to do this is actually instead of using
the 5 and the 62, sometimes I like to go to the negative number that's equivalent to it.
So...
for example, 5 is equivalent to negative 2 mod 7,
and negative 2 to the 9, that's actually not too hard.
Negative 2 to the 9 is negative 512,
and then from there I can try to figure out the remainder when I
try to reduce it mod 7.
That's something you can do and we'll see a couple of other tricks in a minute
of how to deal with the negative 2 to the 9,
but that usually is an easier computation
because in size 2 is smaller than 5, right?
Same with 62, 62 is actually really close to a multiple of 7, namely 63,
so 62 will reduce to 6 mod 7,
and if you think about it, 6 is a little hard so if you…
well 6 is a little bit big to deal with, but if you take
one more 7 away from it, you get negative 1,
so 62 is the same as minus 1, so
62 to the 2000 is the same as minus 1 to the 2000.
That's really easy to deal with.
So let's take a look at the
computation based on all that.
So that first line is exactly what we said, so 5 is the same as minus 2.
And again 62 is the same as minus 1.
Another way to see this, by the way, of course is just directly using the definition.
62 is congruent to minus 1 mod 7,
since 62 minus negative 1 is 63, and 7 divides 63.
So that’s one way to see it. And 14 is going to be 0 mod 7
because 7 divides 14, so those two things are equal.
Now from here, it's actually not too bad. Negative 1 to the 2000
is really easy to do, that's just 1,
and negative 2 to the power of 9, that's just negative 2 to the power of 9,
right, I can pull the negative out because negative 1 to the 9 is negative 1.
Now 2 to the 9, again we can just evaluate it and simplify it,
or we can do this little trick and write it as 2 cubed cubed.
I love to find these little arithmetic tricks
when solving these types of problems. I encourage you to do it too.
There's lots of room to be creative in Number Theory
when writing a proof and I encourage students
to actually be creative and to try to find
multiple ways to solve a problem.
That often shows that you've actually mastered the material
if you can solve it in 3 or 4 different ways.
So here I have 2 cubed cubed,
2 cubed is 8, and 8 is the same as 1 mod 7.
Again, why? Because 8 minus 1 is divisible by 7, right?
So if 8 is the same as 1, then 8 cubed is the same as 1 cubed.
That's the corollary to Properties of Congruences.
So notice that I don't have Properties of Congruences
written at every step, I just wrote it at the beginning.
Usually with computations, we don't write every single time
we use Property of Congruences, or equivalence relations and things like that.
I mean if you think about it, like with equal sign, you don't write them all down, so
why would you write them down with congruence that I'm trying to convince you
to put in that same class as equal signs, right? So something to think about.
So we do the computation, we eventually get minus 1 plus 1 that's 0.
There should be a mod 7 here, I've just forgot to write it down.
So it's congruent to 0 mod 7.
And so what does that mean? So I have this number, did a bunch of computation,
I show that it's congruent to 0 mod 7.
By definition, that means that this number must be divisible by 7, and that's it.
So here's a way to use congruences to solve a divisibility problem
fairly neatly and fairly quickly,
and notice that we didn't actually need to compute what this gigantic number was.
We just needed to evaluate it mod 7, which is pretty neat.