1 00:00:00,000 --> 00:00:02,633 Chinese Remainder Theorem. So, 2 00:00:02,633 --> 00:00:03,933 3 00:00:03,933 --> 00:00:06,233 here's the…this is the simplified Chinese Remainder Theorem. 4 00:00:06,233 --> 00:00:09,733 The generalized one just 
uses more equations, 5 00:00:09,733 --> 00:00:13,600 but the idea reduces to the two 6 00:00:13,600 --> 00:00:15,766 equation Chinese Remainder Theorem. So 7 00:00:15,766 --> 00:00:18,966 let me just give you the two equation Chinese Remainder Theorem: if the gcd of 8 00:00:18,966 --> 00:00:23,133 m1 and m2 is 1, so if 
m1 and m2 are co-prime 9 00:00:23,133 --> 00:00:24,400 moduli, 10 00:00:24,400 --> 00:00:26,900 then for any choice of integers, a1 
and a2, there exists a solution 11 00:00:26,900 --> 00:00:29,933 to the simultaneous congruences 
n is congruent to a1 mod m1, 12 00:00:29,933 --> 00:00:32,233 and n is congruent to a2 mod m2. 13 00:00:32,233 --> 00:00:35,166 Moreover, if we have 
some solution, n naught, 14 00:00:35,166 --> 00:00:39,700 then the complete solution is given by 
n is congruent to n naught mod m1 m2. 15 00:00:39,700 --> 00:00:43,466 So super powerful theorem; 
it says a couple things. 16 00:00:43,466 --> 00:00:44,033 17 00:00:44,033 --> 00:00:45,800 One that this has a solution, 18 00:00:45,800 --> 00:00:49,266 and it always has a solution if m1 and m2 are co-prime. 19 00:00:49,266 --> 00:00:52,966 One thing to note, this is the first time that we've used different moduli. 20 00:00:52,966 --> 00:00:55,600 So up to this point, we've always been 
looking at, let's say, a linear congruence, 21 00:00:55,600 --> 00:00:58,333 which has only used 1 
moduli, but now we have 2. 22 00:00:58,333 --> 00:01:01,166 So this is the first time 
we're interplaying 2 moduli. 23 00:01:01,166 --> 00:01:03,600 Moreover, what does this say? Well if we have 1 solution, 24 00:01:03,600 --> 00:01:05,533 then we can find all solutions. 25 00:01:05,533 --> 00:01:09,600 So buy 1, get infinitely many for free is what 
I like to look at these theorems as, okay? 26 00:01:09,600 --> 00:01:11,000 27 00:01:11,000 --> 00:01:14,966 So if I have 1 solution, I can find them all 
by just taking the product of the moduli 28 00:01:14,966 --> 00:01:18,000 and looking at n congruent to 
n naught mod the product. 29 00:01:18,000 --> 00:01:20,000 30 00:01:20,000 --> 00:01:24,266 This is one of these theorems where the proof 
is actually basically given by an example. 31 00:01:24,266 --> 00:01:25,200 32 00:01:25,200 --> 00:01:27,666 You can do it abstractly, which is fine, 33 00:01:27,666 --> 00:01:30,133 but it basically is just do an 
example and go through it, 34 00:01:30,133 --> 00:01:32,500 which I think I'm going 
to do on the next slide. 35 00:01:32,500 --> 00:01:35,433 So solve the simultaneous congruence 
x is congruent to 2 mod 7 36 00:01:35,433 --> 00:01:37,866 and x is congruent to 7 mod 11. 37 00:01:37,866 --> 00:01:38,733 38 00:01:38,733 --> 00:01:39,966 Now... 39 00:01:39,966 --> 00:01:40,700 40 00:01:40,700 --> 00:01:43,733 if you’re looking at this for the first 
time, take a minute, pause the video, 41 00:01:43,733 --> 00:01:46,700 actually should pause the video 
regardless. Make sure you can do this. 42 00:01:46,700 --> 00:01:48,733 Try to solve this problem. 43 00:01:48,733 --> 00:01:50,533 44 00:01:50,533 --> 00:01:52,133 Now if you're back, 45 00:01:52,133 --> 00:01:52,733 46 00:01:52,733 --> 00:01:55,000 let's try to solve this together, okay? 47 00:01:55,000 --> 00:01:57,466 So when we're solving these 
simultaneous congruences, 48 00:01:57,466 --> 00:02:00,500 what I like to do is 
I like to start with… 49 00:02:00,500 --> 00:02:02,300 what you should really do - so this 
is not what I'm going to do here. 50 00:02:02,300 --> 00:02:05,700 I'm going to probably start with the mod 7 in my solution in this slide, 51 00:02:05,700 --> 00:02:08,766 but it actually helps to start with 
a bigger number, usually because 52 00:02:08,766 --> 00:02:12,000 when I go to the smaller number 
mod 7, it's easier to reduce. 53 00:02:12,000 --> 00:02:13,233 Okay? 54 00:02:13,233 --> 00:02:14,300 55 00:02:14,300 --> 00:02:17,233 But, however, that’s not the way I'm going 
to do it. I'm going to start left to right, 56 00:02:17,233 --> 00:02:19,533 which is perfectly fine as well. You just might have to deal with 57 00:02:19,533 --> 00:02:22,600 harder computations mod 11. 
Something to think about. 58 00:02:22,600 --> 00:02:24,533 59 00:02:24,533 --> 00:02:27,000 Okay, so... 60 00:02:27,000 --> 00:02:29,766 x is congruent to 2 
mod 7, we use the 61 00:02:29,766 --> 00:02:33,700 first slide in this 
presentation to write x as 62 00:02:33,700 --> 00:02:36,533 2 plus 7k for some integer k. 63 00:02:36,533 --> 00:02:38,766 Then we plug this x into the second equation, 64 00:02:38,766 --> 00:02:40,633 and we simplify, and we're going to get 65 00:02:40,633 --> 00:02:44,000 7k is congruent to 5 mod 11. 66 00:02:44,000 --> 00:02:46,666 So here we brought the 
2 over to the other side. 67 00:02:46,666 --> 00:02:47,766 68 00:02:47,766 --> 00:02:50,066 Now when we get to this point… 69 00:02:50,066 --> 00:02:53,000 70 00:02:53,000 --> 00:02:56,466 there's lots of ways to approach
this, okay? One way to do this, if 71 00:02:56,466 --> 00:02:59,000 you don't see an immediate answer, 72 00:02:59,000 --> 00:03:02,166 you can turn this to a Linear 
Diophantine Equation, you can solve it. 73 00:03:02,166 --> 00:03:05,066 You can try to guess the 
answer for k, right, because 74 00:03:05,066 --> 00:03:08,600 this is a linear congruence and once we know 1 answer we know all of them. 75 00:03:08,600 --> 00:03:11,200 I know that the gcd 
of 7 and 11 is 1, 76 00:03:11,200 --> 00:03:14,400 1 divides 5, so there 
is a solution by LCT1, 77 00:03:14,400 --> 00:03:16,266 and there's exactly 1 solution mod 11. 78 00:03:16,266 --> 00:03:18,966 So once you find one 
value for k, it's good. 79 00:03:18,966 --> 00:03:20,200 80 00:03:20,200 --> 00:03:23,166 Another way to do this - the way I like to 
look at this is I like to look at this as I'm 81 00:03:23,166 --> 00:03:25,966 trying to divide by 7, right, 
that's what I would do 82 00:03:25,966 --> 00:03:27,900 over if it was an equal sign. 83 00:03:27,900 --> 00:03:30,933 So remember that we don't really 
have division, but we do have 84 00:03:30,933 --> 00:03:34,566 multiplication by the inverse, which you 
should think of as the same as division. 85 00:03:34,566 --> 00:03:35,366 86 00:03:35,366 --> 00:03:37,800 So multiplying by the inverse, 
which we know exists, again 87 00:03:37,800 --> 00:03:40,000 since the gcd of 7 and 11 is [1] 88 00:03:40,000 --> 00:03:42,666 so we try to find the inverse. 89 00:03:42,666 --> 00:03:47,333 Turns out that the inverse to 7 is 8. 8 times 7 is 56, but 90 00:03:47,333 --> 00:03:48,533 91 00:03:48,533 --> 00:03:51,000 8 is also congruent to negative 3. 92 00:03:51,000 --> 00:03:53,766 And one thing to notice, if I 
multiply this equation by 3 93 00:03:53,766 --> 00:03:57,300 on both sides, which is valid by Properties of Congruence, let's say. 94 00:03:57,300 --> 00:03:58,133 95 00:03:58,133 --> 00:04:01,433 What does that give me? So it gives 
me 3 times 7k is congruent to 15, 96 00:04:01,433 --> 00:04:04,100 that’s 21k is congruent to 4 mod 11. 97 00:04:04,100 --> 00:04:08,033 And 21 mod 11, well 21 is the same as 98 00:04:08,033 --> 00:04:09,800 negative 1. Why? 99 00:04:09,800 --> 00:04:14,900 Because 21 minus negative 1, 
that's 22, and 11 divides 22. 100 00:04:14,900 --> 00:04:18,500 Another way to look at this is I have 
21 and I'm subtracting 22 from it, 101 00:04:18,500 --> 00:04:21,900 which is valid because negative 
22 is the same as 0 mod 11. 102 00:04:21,900 --> 00:04:23,166 103 00:04:23,166 --> 00:04:25,733 So that gives me negative k 
is congruent to 4 mod 11, 104 00:04:25,733 --> 00:04:28,300 and then here we can multiply both sides by minus 1. 105 00:04:28,300 --> 00:04:33,033 So k is congruent to minus 4 mod 11, 
and minus 4 is the same as 7 mod 11. 106 00:04:33,033 --> 00:04:35,033 So therefore, 107 00:04:35,033 --> 00:04:40,233 k equals 7 plus 11l, 
for some integer l, 108 00:04:40,233 --> 00:04:44,600 and since x is equal to 2 plus 
7k and k is equal to 7 plus 11l 109 00:04:44,600 --> 00:04:47,000 we can substitute the k value 110 00:04:47,000 --> 00:04:51,200 into here and what do we get? We're 
going to get x is equal to 51 plus 77l. 111 00:04:51,200 --> 00:04:52,733 112 00:04:52,733 --> 00:04:55,733 And a couple of ways 
to think about this, so 113 00:04:55,733 --> 00:04:58,166 what does this mean? 
So x equals 51 plus 77l. 114 00:04:58,166 --> 00:05:00,733 x was some arbitrary 
solution at the beginning. 115 00:05:00,733 --> 00:05:01,733 116 00:05:01,733 --> 00:05:04,300 So no matter what solution we pick, 117 00:05:04,300 --> 00:05:08,866 we see that x must be equal 
to 51 plus some multiple of 77. 118 00:05:08,866 --> 00:05:09,933 119 00:05:09,933 --> 00:05:13,200 And it's very quick to see that all of 
these are actually solutions to this, 120 00:05:13,200 --> 00:05:17,133 and therefore x is congruent to 51 mod 
77 gives the complete solution set. 121 00:05:17,133 --> 00:05:18,366 122 00:05:18,366 --> 00:05:21,333 So there's a little bit of a step 
there to get the logic around 123 00:05:21,333 --> 00:05:24,000 because we are doing things like 
oh well we're taking for some l, 124 00:05:24,000 --> 00:05:27,100 and then we're getting rid of it, and then 
we're claiming that all of these are solutions, 125 00:05:27,100 --> 00:05:29,033 so there's a little bit to think about there. 126 00:05:29,033 --> 00:05:32,533 But I don't want to get too 
bogged down by those details. 127 00:05:32,533 --> 00:05:35,500 I’d rather you think, “Okay, well 
if I started with a solution x, 128 00:05:35,500 --> 00:05:38,733 I got down to x is equal 
to 51 plus some 77l, 129 00:05:38,733 --> 00:05:43,300 and each of these 51 plus 77l 
are solutions to this equation.” 130 00:05:43,300 --> 00:05:44,500 131 00:05:44,500 --> 00:05:45,800 And that's it. 132 00:05:45,800 --> 00:05:47,000 133 00:05:47,000 --> 00:05:49,100 So that's the Chinese Remainder 
Theorem. Now you can do this with, 134 00:05:49,100 --> 00:05:53,066 instead of 2 equations, 3 equations, 
and 4 equations, all that's fine. Just take 135 00:05:53,066 --> 00:05:57,433 2 of them, simplify it, and then take the next 
2 and simplify it, and so on and so forth. 136 00:05:57,433 --> 00:06:00,900 So it's not any harder to do 
this with more equations. 137 00:06:00,900 --> 00:06:01,733 138 00:06:01,733 --> 00:06:04,366 Well it's more work, but 
it's not mentally harder. 139 00:06:04,366 --> 00:06:05,966 140 00:06:05,966 --> 00:06:08,466 And there are a couple 
twists that we saw in class, 141 00:06:08,466 --> 00:06:11,466 but I don't believe I'm going to go 
through them now, no I'm not. 142 00:06:11,466 --> 00:06:12,433 143 00:06:12,433 --> 00:06:16,433 For the extra twists and 
things that we can do to… 144 00:06:16,433 --> 00:06:18,566 not trick you but to… 145 00:06:18,566 --> 00:06:19,500 146 00:06:19,500 --> 00:06:21,733 let me just say trick you 
even though it’s not true. 147 00:06:21,733 --> 00:06:23,766 To make it more complicated. 148 00:06:23,766 --> 00:06:27,566 So things that we do to make it more complicated, 
you can check those out on the website. 149 00:06:27,566 --> 00:06:30,066 Splitting the Modulus, this was the last thing we talked about. 150 00:06:30,066 --> 00:06:32,000 I had a student ask a good question 
this week and they said, “Well 151 00:06:32,000 --> 00:06:35,766 okay so if we have the Chinese Remainder 
Theorem, it's like we're combining moduli,” 152 00:06:35,766 --> 00:06:38,266 and the student asked, “Well can we 153 00:06:38,266 --> 00:06:41,066 break them apart?” And I said 
well yes absolutely we can, 154 00:06:41,066 --> 00:06:42,666 in certain cases. 155 00:06:42,666 --> 00:06:44,733 That's we're going to talk about 156 00:06:44,733 --> 00:06:46,933 here with Splitting the Modulus. 157 00:06:46,933 --> 00:06:48,300 158 00:06:48,300 --> 00:06:51,433 So if we have the following simultaneous system 159 00:06:51,433 --> 00:06:56,000 of congruences, x is congruent to a 
mod m, and x is congruent to a mod n, 160 00:06:56,000 --> 00:07:00,366 then this is true if and only if x is congruent to a mod m times n, 161 00:07:00,366 --> 00:07:04,000 where m and n are co-prime integers here. 
Okay so again that's really important. 162 00:07:04,000 --> 00:07:05,166 163 00:07:05,166 --> 00:07:07,900 The proof in one direction is just the Chinese Remainder Theorem, right, 164 00:07:07,900 --> 00:07:10,966 x equals a is a solution to 
this simultaneous congruence 165 00:07:10,966 --> 00:07:15,266 so therefore x is congruent to a 
mod m n gives us the full solution 166 00:07:15,266 --> 00:07:16,766 by the Chinese Remainder Theorem. 167 00:07:16,766 --> 00:07:20,000 To go the opposite direction, 
it actually turns out to be 168 00:07:20,000 --> 00:07:21,666 an argument in transitivity. 169 00:07:21,666 --> 00:07:23,900 So m n divides x minus a, 170 00:07:23,900 --> 00:07:27,733 and m divides m n, so therefore m divides x minus a, 171 00:07:27,733 --> 00:07:29,966 that's the first equation. Similarly for n. 172 00:07:29,966 --> 00:07:30,933 173 00:07:30,933 --> 00:07:33,066 Actually a very simple 
theorem to prove. 174 00:07:33,066 --> 00:07:35,366 This is pretty powerful when 
you can actually get the x 175 00:07:35,366 --> 00:07:37,933 congruent to the 
same a mod m and n. 176 00:07:37,933 --> 00:07:39,200 177 00:07:39,200 --> 00:07:41,800 Sometimes you can do it by guessing, which is pretty neat. 178 00:07:41,800 --> 00:07:43,666 It's not often, but sometimes you can. 179 00:07:43,666 --> 00:07:46,733 If the numbers are small, you should be 
able to guess the solution fairly quickly. 180 00:07:46,733 --> 00:07:48,066 181 00:07:48,066 --> 00:07:51,300 If the numbers are big, you should try 
to use the Chinese Remainder Theorem, 182 00:07:51,300 --> 00:07:55,300 use Linear Diophantine Equation stuff, the 
Extended Euclidean Algorithm, things like that 183 00:07:55,300 --> 00:07:57,766 to get you the answer very quickly. 184 00:07:57,766 --> 00:08:00,700 But anyways here it is; 
Splitting the Modulus. 185 00:08:00,700 --> 00:08:04,000 So we've seen some examples in class, 
I don't think I'm going to do any here. 186 00:08:04,000 --> 00:08:07,733 Again check the notes for some 
examples of the use of this. 187 00:08:07,733 --> 00:08:12,199 You'll actually see it though in RSA, at 
least in the proof of RSA, next week.