Hello everyone. In this video, we're going to talk about
CISR, so Congruent If and Only If Same Remainder.
I'd like to start this video by just going over the statement that we have,
and the statement here is written: a is congruent to b mod m if and only if
a and b have the same remainder when divided by m.
So remember this says two things, right, that's what the notes here are saying.
So this comes straight from your…the notes for Math 135
in the fall 2015 term.
So what does this statement say? So it says, if a is congruent to b mod m,
then a and b have the same remainder when divided by m.
That's half of it, and the other half is a and b have the same remainder when divided by m,
then a is congruent to b mod m.
So if we ever want to calculate a congruence, it's the same as computing
the remainder, in some sense,
and that sense is given by this. So let's take a look at an actual example
of this problem.
So the example that I have in mind
is does 13 divided 2 to the 70 plus 3 to the 70?
So take a couple of minutes now,
pause the video, and actually try this problem.
It's worth thinking about and at least trying to come up with a solution to this.
Now that you're back, hopefully you paused it,
let's take a look. How do we do this? So does 13 divided this?
So if 13 divides this number,
then the remainder when I divide by 13 should be 0.
So what does it suffice? Well by Congruent If and Only If Same Remainder,
it suffices to look at this mod 13,
and if I get 0, then 13 divides it and otherwise 13 doesn't divide this number.
So by CISR,
13 divides this number
if and only if…
if and only if this number…
is equivalent to 0
mod 13.
Right, so now it suffices to divide this number,
or to look at this number mod 13.
So hopefully you got to this point and you at least knew how to do this.
Again, I would recommend pausing the video at this point
and if you didn't get to this point, then trying it again.
So now let's look at this number
mod 13. Now
it might not be obvious what to do and with these types of problems,
it might not be,
but what I'm going to do is I'm going to just start to evaluate this, okay?
I'm going to take this first 2 to the 70 and at least start to evaluate it and
the best way to do this - well maybe not the best way…
a way to do this is to actually take the 70,
and use the fact that 70 is 2 times 35,
and then look at 2 squared to the power of 35,
and then see where that gets us.
So I'm going to take this and do exactly what I said.
2 squared to the power of 35.
So let's make that change here.
Those are the same thing, right, by exponent laws.
Now what am I doing? Well now I need to take a look at
2 squared, well that's 4, so let's do that.
Okay so it's 4,
now what am I going to do? Okay so now it's not clear.
Again, you might want to pause and try to think about what to do now.
If you look at this, so now 4 mod 13, well
again it's not…
it's not obvious but 4 isn't really the right number to use. So
4 mod 13, we can actually go to the negative side
of 4 and what do we get if we go to the negative side of 4? So
4 is actually the same as negative 9 mod 13.
So how do we see that? Well…
well 4 is the same as negative 9 mod 13, you can do that just directly by definition, right?
So I'll write that underneath this. So
4 is equivalent to negative 9 mod 13.
So I’m going to write this underneath it should appear here right?
So how did we see that? Well okay, if we bring the negative 9 over, that
becomes 4 plus 9, and 13 divides 4 plus 9.
So that's the simplest way to see it.
I like to think of mod 13 every once in a while as adding or subtracting 0’s, right?
So with mod 13, I can actually just
subtract 13 because 13 is the same as 0 mod 13.
Right?
So I can
add and subtract 0 as much as I want, right?
It works for equality, it works for congruences.
Now if I do this, what do I get? Doesn't look like I get much,
but let's take a look.
Well 4 minus 13, that's negative 9.
And now with negative 9, what do I do now?
Well negative 9, that's the same as -
so negative 1 to the power of 35, well 35 is an odd number so I can pull the negative out.
It’ll look like this,
and now I have 9 to the 35, well let's go backwards now. 9 is the same as 3 squared.
3 squared well okay,
3 squared to the 35 well, just like I did up here,
2 squared to the 35 I'm going to bring those two together what am I going to get?
I'm going to actually get 3 to the 70.
And lo and behold,
we actually get
cancellation.
It's a little bit magical, so you didn't have to evaluate 2 to the 70 and 3 to the 70 completely by hand,
right, you actually get a little bit lucky. Again, how do you know to do this?
It's a matter of feeling and a matter of trying things, right?
My first attempt wasn't this. My first attempt was actually trying…
I got to 2 to the 4 and I said
oh that's 16 well mod 13, that's 3,
and then I tried to use that to help me out.
I didn't really get very far.
It just became more complicated and I thought it was harder than it needed to be.
So then I started saying okay what if I did this splitting up the 2 trick,
then I got to 4 and I was still not confident
and then I decided well okay well
instead of 4 let's go to negative 9, and then I realized oh that's almost the same as 3,
and then I could do it.
You can also play this trick with 3 to the 70 instead of with 2 to the 70.
3 squared is 9, 9 becomes negative 4, and then the same sort of trick works. So
I encourage you to try that if you don't see this.
I guess we should also finish this off, right? So let's
put a nice little concluding sentence. So therefore
13 divides the number.
And that's actually it.
So hopefully, this gives you a little bit of a feeling as to what CISR says
and how to use it in an example,
and this gives you a little bit of feeling about the computation.
Gives you a little bit of a feeling of how I treat mods.
I kind of look at the 13 as being a 0 so I can add and subtract 13 as much as I want.
Hopefully this gives you some insight to solving these types of problems.
So thank you very much and good luck.