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.
Theorem (CISR): $a\equiv b\pmod 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 the notes for Math 135 in the fall 2015 term.
Theorem (CISR restated):
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.
Does $13$ divide $2^{70}+3^{70}$?
So take a couple of minutes now and actually try this problem. It's worth thinking about and at least trying to come up with a solution to this.
How do we do this? So does $13$ divide 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
$$2^{70}+3^{70}\equiv 0\pmod {13}$$So hopefully you got to this point and you at least knew how to do this. Again, I would recommend taking a minute 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^{70}$ and at least start to evaluate it. A way to do this is to actually take the $70$, and use the fact that $70=2(35)$, and then look at $(2^2)^{35}$ then see where that gets us.
$$\begin{align*} 2^{70}+3^{70}&\equiv (2^2)^{35}+3^{70} \pmod{13}\\ &\equiv(4)^{35}+3^{70}\pmod{13} \end{align*}$$Now what am I going to do? Okay so now it's not clear. Again, you might want to take a minute and try to think about what to do now.
If you look at this, so now $4 \bmod {13}$, well again it's not obvious but $4$ isn't really the right number to use. So $4 \bmod {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\equiv -9 \pmod {13}$.
$$\begin{align*} 2^{70}+3^{70}&\equiv (2^2)^{35}+3^{70} \pmod{13}\\ &\equiv(4)^{35}+3^{70}\pmod{13}\\ &\equiv(4-13)^{35}+3^{70}\pmod{13}\\ &\equiv(-9)^{35}+3^{70}\pmod{13} \end{align*}$$So how do we see that? Well you can do that just directly by definition, right? $13\mid 4-(-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 \equiv 0\pmod{13}$. 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. And now with $-9$, what do I do now?
Well $(-9)^{35}=(-1)^{35}(9)^{35}=-(9)^{35}$, so let's do that.
$$\begin{align*} 2^{70}+3^{70}&\equiv (2^2)^{35}+3^{70} \pmod{13}\\ &\equiv(4)^{35}+3^{70}\pmod{13}\\ &\equiv(4-13)^{35}+3^{70}\pmod{13}\\ &\equiv(-9)^{35}+3^{70}\pmod{13}\\ &\equiv-(9)^{35}+3^{70}\pmod{13} \end{align*}$$Now I have $9^{35}$, well let's go backwards now. $9=3^2$ so we do that and we get
$$\begin{align*} 2^{70}+3^{70}&\equiv (2^2)^{35}+3^{70} \pmod{13}\\ &\equiv(4)^{35}+3^{70}\pmod{13}\\ &\equiv(4-13)^{35}+3^{70}\pmod{13}\\ &\equiv(-9)^{35}+3^{70}\pmod{13}\\ &\equiv-(9)^{35}+3^{70}\pmod{13}\\ &\equiv-(3^2)^{35}+3^{70}\pmod{13}\\ &\equiv-(3)^{70}+3^{70}\pmod{13}\\ &\equiv 0 \end{align*}$$Therefore $13$ divides $2^{70}+3^{70}$
It's a little bit magical, so you didn't have to evaluate $2^{70}$ and $3^{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 I got to $2^4$ and I said oh that's $16$ well $16 \bmod {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 $-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^{70}$ to instead of with $2^{70}$. $3^2=9$, $9\equiv -4 \pmod {13}$, and then the same sort of trick works. So I encourage you to try that if you don't see this.
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.