Chinese Remainder Theorem. So,
here's the…this is the simplified Chinese Remainder Theorem.
The generalized one just uses more equations,
but the idea reduces to the two
equation Chinese Remainder Theorem. So
let me just give you the two equation Chinese Remainder Theorem: if the gcd of
m1 and m2 is 1, so if m1 and m2 are co-prime
moduli,
then for any choice of integers, a1 and a2, there exists a solution
to the simultaneous congruences n is congruent to a1 mod m1,
and n is congruent to a2 mod m2.
Moreover, if we have some solution, n naught,
then the complete solution is given by n is congruent to n naught mod m1 m2.
So super powerful theorem; it says a couple things.
One that this has a solution,
and it always has a solution if m1 and m2 are co-prime.
One thing to note, this is the first time that we've used different moduli.
So up to this point, we've always been looking at, let's say, a linear congruence,
which has only used 1 moduli, but now we have 2.
So this is the first time we're interplaying 2 moduli.
Moreover, what does this say? Well if we have 1 solution,
then we can find all solutions.
So buy 1, get infinitely many for free is what I like to look at these theorems as, okay?
So if I have 1 solution, I can find them all by just taking the product of the moduli
and looking at n congruent to n naught mod the product.
This is one of these theorems where the proof is actually basically given by an example.
You can do it abstractly, which is fine,
but it basically is just do an example and go through it,
which I think I'm going to do on the next slide.
So solve the simultaneous congruence x is congruent to 2 mod 7
and x is congruent to 7 mod 11.
Now...
if you’re looking at this for the first time, take a minute, pause the video,
actually should pause the video regardless. Make sure you can do this.
Try to solve this problem.
Now if you're back,
let's try to solve this together, okay?
So when we're solving these simultaneous congruences,
what I like to do is I like to start with…
what you should really do - so this is not what I'm going to do here.
I'm going to probably start with the mod 7 in my solution in this slide,
but it actually helps to start with a bigger number, usually because
when I go to the smaller number mod 7, it's easier to reduce.
Okay?
But, however, that’s not the way I'm going to do it. I'm going to start left to right,
which is perfectly fine as well. You just might have to deal with
harder computations mod 11. Something to think about.
Okay, so...
x is congruent to 2 mod 7, we use the
first slide in this presentation to write x as
2 plus 7k for some integer k.
Then we plug this x into the second equation,
and we simplify, and we're going to get
7k is congruent to 5 mod 11.
So here we brought the 2 over to the other side.
Now when we get to this point…
there's lots of ways to approach this, okay? One way to do this, if
you don't see an immediate answer,
you can turn this to a Linear Diophantine Equation, you can solve it.
You can try to guess the answer for k, right, because
this is a linear congruence and once we know 1 answer we know all of them.
I know that the gcd of 7 and 11 is 1,
1 divides 5, so there is a solution by LCT1,
and there's exactly 1 solution mod 11.
So once you find one value for k, it's good.
Another way to do this - the way I like to look at this is I like to look at this as I'm
trying to divide by 7, right, that's what I would do
over if it was an equal sign.
So remember that we don't really have division, but we do have
multiplication by the inverse, which you should think of as the same as division.
So multiplying by the inverse, which we know exists, again
since the gcd of 7 and 11 is [1]
so we try to find the inverse.
Turns out that the inverse to 7 is 8. 8 times 7 is 56, but
8 is also congruent to negative 3.
And one thing to notice, if I multiply this equation by 3
on both sides, which is valid by Properties of Congruence, let's say.
What does that give me? So it gives me 3 times 7k is congruent to 15,
that’s 21k is congruent to 4 mod 11.
And 21 mod 11, well 21 is the same as
negative 1. Why?
Because 21 minus negative 1, that's 22, and 11 divides 22.
Another way to look at this is I have 21 and I'm subtracting 22 from it,
which is valid because negative 22 is the same as 0 mod 11.
So that gives me negative k is congruent to 4 mod 11,
and then here we can multiply both sides by minus 1.
So k is congruent to minus 4 mod 11, and minus 4 is the same as 7 mod 11.
So therefore,
k equals 7 plus 11l, for some integer l,
and since x is equal to 2 plus 7k and k is equal to 7 plus 11l
we can substitute the k value
into here and what do we get? We're going to get x is equal to 51 plus 77l.
And a couple of ways to think about this, so
what does this mean? So x equals 51 plus 77l.
x was some arbitrary solution at the beginning.
So no matter what solution we pick,
we see that x must be equal to 51 plus some multiple of 77.
And it's very quick to see that all of these are actually solutions to this,
and therefore x is congruent to 51 mod 77 gives the complete solution set.
So there's a little bit of a step there to get the logic around
because we are doing things like oh well we're taking for some l,
and then we're getting rid of it, and then we're claiming that all of these are solutions,
so there's a little bit to think about there.
But I don't want to get too bogged down by those details.
I’d rather you think, “Okay, well if I started with a solution x,
I got down to x is equal to 51 plus some 77l,
and each of these 51 plus 77l are solutions to this equation.”
And that's it.
So that's the Chinese Remainder Theorem. Now you can do this with,
instead of 2 equations, 3 equations, and 4 equations, all that's fine. Just take
2 of them, simplify it, and then take the next 2 and simplify it, and so on and so forth.
So it's not any harder to do this with more equations.
Well it's more work, but it's not mentally harder.
And there are a couple twists that we saw in class,
but I don't believe I'm going to go through them now, no I'm not.
For the extra twists and things that we can do to…
not trick you but to…
let me just say trick you even though it’s not true.
To make it more complicated.
So things that we do to make it more complicated, you can check those out on the website.
Splitting the Modulus, this was the last thing we talked about.
I had a student ask a good question this week and they said, “Well
okay so if we have the Chinese Remainder Theorem, it's like we're combining moduli,”
and the student asked, “Well can we
break them apart?” And I said well yes absolutely we can,
in certain cases.
That's we're going to talk about
here with Splitting the Modulus.
So if we have the following simultaneous system
of congruences, x is congruent to a mod m, and x is congruent to a mod n,
then this is true if and only if x is congruent to a mod m times n,
where m and n are co-prime integers here. Okay so again that's really important.
The proof in one direction is just the Chinese Remainder Theorem, right,
x equals a is a solution to this simultaneous congruence
so therefore x is congruent to a mod m n gives us the full solution
by the Chinese Remainder Theorem.
To go the opposite direction, it actually turns out to be
an argument in transitivity.
So m n divides x minus a,
and m divides m n, so therefore m divides x minus a,
that's the first equation. Similarly for n.
Actually a very simple theorem to prove.
This is pretty powerful when you can actually get the x
congruent to the same a mod m and n.
Sometimes you can do it by guessing, which is pretty neat.
It's not often, but sometimes you can.
If the numbers are small, you should be able to guess the solution fairly quickly.
If the numbers are big, you should try to use the Chinese Remainder Theorem,
use Linear Diophantine Equation stuff, the Extended Euclidean Algorithm, things like that
to get you the answer very quickly.
But anyways here it is; Splitting the Modulus.
So we've seen some examples in class, I don't think I'm going to do any here.
Again check the notes for some examples of the use of this.
You'll actually see it though in RSA, at least in the proof of RSA, next week.