1 00:00:00,000 --> 00:00:01,266 Hello everyone. 2 00:00:01,266 --> 00:00:05,466 In this sequence of videos, we’re going 
to talk about the solutions to an old 3 00:00:05,466 --> 00:00:06,200 4 00:00:06,200 --> 00:00:09,900 Math 135 exam from the University of Waterloo. 5 00:00:09,900 --> 00:00:14,166 This was the Fall 2000 exam 
available on the MathSoc Exam Bank. 6 00:00:14,166 --> 00:00:15,666 7 00:00:15,666 --> 00:00:18,600 This was meant to be a live stream performance, but 8 00:00:18,600 --> 00:00:21,266 the live stream… 9 00:00:21,266 --> 00:00:25,166 I was using Twitch and for 
some reason it wasn't working, 10 00:00:25,166 --> 00:00:29,033 it kept crashing, so after an hour I decided to 11 00:00:29,033 --> 00:00:32,033 call an audible and say okay we're 
not going to do this as a live stream, 12 00:00:32,033 --> 00:00:36,033 we're going to be as an offline session and 
I will put the videos online after the fact. 13 00:00:36,033 --> 00:00:40,266 So the first two problems we actually 
did manage to cover in the online session, 14 00:00:40,266 --> 00:00:41,133 15 00:00:41,133 --> 00:00:44,533 which - I had some questions, I’m going 
to hopefully answer them all in this video, 16 00:00:44,533 --> 00:00:47,400 and if not again throughout this video series 17 00:00:47,400 --> 00:00:51,600 do feel free to send me an email if you 
need a clarification about something. 18 00:00:51,600 --> 00:00:52,766 19 00:00:52,766 --> 00:00:54,900 I’m more than happy to help. 20 00:00:54,900 --> 00:00:55,733 21 00:00:55,733 --> 00:00:59,533 So first question of the exam was solve 
the following system of linear congruences 22 00:00:59,533 --> 00:01:03,633 11x is congruent to 12 mod 24 
and x is congruent to 4 mod 25. 23 00:01:03,633 --> 00:01:06,533 So if you see a question like this, you should be jumping for joy. 24 00:01:06,533 --> 00:01:07,866 This question - 25 00:01:07,866 --> 00:01:11,533 there's really only one way to attack it, it's a 
Chinese Remainder Theorem type question, 26 00:01:11,533 --> 00:01:15,766 and you have to use some sort of Chinese
Remainder Theorem type arguments, okay? 27 00:01:15,766 --> 00:01:19,200 So I'm going to happily go through this 
with the Chinese Remainder Theorem. 28 00:01:19,200 --> 00:01:23,433 Because in the second equation x is 
already isolated, x is congruent to 4 mod 25, 29 00:01:23,433 --> 00:01:25,233 I am going to start with this equation. 30 00:01:25,233 --> 00:01:30,566 So by definition, x is equal to 
4 plus 25k for some integer k. 31 00:01:30,566 --> 00:01:33,300 We're going to take this, we're going to plug it 
into the first equation. What are we going to get? 32 00:01:33,300 --> 00:01:38,166 We're going to get 11 times 4 plus 
25k is congruent to 12 mod 24. 33 00:01:38,166 --> 00:01:40,466 That’s great, so let’s simplify. 34 00:01:40,466 --> 00:01:43,033 So we thing we can do, and I probably should have 
done something, or mentioned this, in the stream, 35 00:01:43,033 --> 00:01:45,066 is reduce 25 mod 24, 36 00:01:45,066 --> 00:01:47,233 that would have given me 1, and I 
would have immediately gotten that 37 00:01:47,233 --> 00:01:50,400 11 times 25 is congruent to 11k, 38 00:01:50,400 --> 00:01:53,366 but I didn't do that. If you don't 
see all these tricks, it's okay. 39 00:01:53,366 --> 00:01:57,833 So I just decided to multiply it out, so 11 times 4 is 44 plus 275k 40 00:01:57,833 --> 00:01:59,833 is congruent to 12 mod 24. 41 00:01:59,833 --> 00:02:01,100 42 00:02:01,100 --> 00:02:02,933 I know that 240 is a power - 43 00:02:02,933 --> 00:02:05,200 or a multiple 24 close to 275, 44 00:02:05,200 --> 00:02:08,266 so if I subtract by 240, I get 35k. 45 00:02:08,266 --> 00:02:10,500 44 subtracted by 24 is 20. 46 00:02:10,500 --> 00:02:11,500 47 00:02:11,500 --> 00:02:14,900 So that gives me 20 plus 35k 
is congruent to 12 mod 24. 48 00:02:14,900 --> 00:02:15,766 49 00:02:15,766 --> 00:02:20,033 Bring the 20 over I get negative
8, negative 8 plus 24 is 16. 50 00:02:20,033 --> 00:02:22,533 35 I can reduce one more time, 
like I said earlier, and I get 51 00:02:22,533 --> 00:02:25,700 11k is congruent to 16 mod 24. 52 00:02:25,700 --> 00:02:27,633 Okay, so that's great. 53 00:02:27,633 --> 00:02:30,300 Now at this point you have options. 54 00:02:30,300 --> 00:02:33,666 I always like to try to find the inverse 55 00:02:33,666 --> 00:02:36,766 of the number mod 24. So 
again the gcd of 11 and 24 is 56 00:02:36,766 --> 00:02:40,666 definitely 1 because 11 doesn't 
divide 24 and 11 is prime. 57 00:02:40,666 --> 00:02:43,400 So that's fantastic, so I know 
that the inverse exists, 58 00:02:43,400 --> 00:02:47,533 and I kind of find it fun to try to find the inverse 
of these numbers, so I always try to do it. 59 00:02:47,533 --> 00:02:48,733 60 00:02:48,733 --> 00:02:52,266 It's not necessarily always 
easy, but I did give it a shot. 61 00:02:52,266 --> 00:02:54,966 Now, in the live stream, I actually struggled a little bit 62 00:02:54,966 --> 00:02:58,566 until I started doing it intelligently and instead of counting by multiples of 11, 63 00:02:58,566 --> 00:03:02,500 I counted by multiples of 24 and tried 
to recognize a multiple of 11 near one. 64 00:03:02,500 --> 00:03:07,066 So I started 24, the closest 
multiple of 11 near 24 is 22. 65 00:03:07,066 --> 00:03:11,800 48 closest multiple of 11 near there 
is 44, that's not going to give me 1. 66 00:03:11,800 --> 00:03:12,700 67 00:03:12,700 --> 00:03:15,766 So 24, 48, 72 is the next one, 68 00:03:15,766 --> 00:03:17,966 that's not close to 77 or 66. 69 00:03:17,966 --> 00:03:22,566 So let's do it again, 96 it's 
close to 99, but not close enough. 70 00:03:22,566 --> 00:03:25,233 96 plus 24 is 120, 71 00:03:25,233 --> 00:03:27,533 120 is close to a multiple of 11, 72 00:03:27,533 --> 00:03:31,633 really close, 120 is really close 
to 121, which is 11 squared, 73 00:03:31,633 --> 00:03:32,766 74 00:03:32,766 --> 00:03:36,133 right, so I know if I multiply 11 by 11, I get 75 00:03:36,133 --> 00:03:40,666 121, and because 120 is the same as 0 mod 24, 76 00:03:40,666 --> 00:03:43,200 I know that 121 will reduce to 1. 77 00:03:43,200 --> 00:03:45,366 So if I multiply both sides by 11, 78 00:03:45,366 --> 00:03:47,800 I can reduce the left-hand side down to 1, 79 00:03:47,800 --> 00:03:52,066 and I can reduce the right-hand side 
down to 11 times 16, that's 176, 80 00:03:52,066 --> 00:03:56,333 and if I subtract 120, I get 56. So subtract 81 00:03:56,333 --> 00:03:59,800 48, I get k is congruent to 8 mod 24. 82 00:03:59,800 --> 00:04:02,600 So what am I doing here? 
I'm finding the inverse of 11. 83 00:04:02,600 --> 00:04:05,366 11 happens to be a self inverse mod 24. 84 00:04:05,366 --> 00:04:08,200 So 11 times 11 happens to be 1, 85 00:04:08,200 --> 00:04:11,333 which is cool, and it doesn't happen over the real numbers, right? It's only 86 00:04:11,333 --> 00:04:13,833 plus or minus 1 that if I square it I get 1, 87 00:04:13,833 --> 00:04:17,566 but mod 24 sometimes things 
like 11 squared can give you 1. 88 00:04:17,566 --> 00:04:18,466 89 00:04:18,466 --> 00:04:21,633 So it's pretty neat, and it does work, okay? 90 00:04:21,633 --> 00:04:24,133 So, great, so I have k is congruent 
to 8 mod 24, so therefore 91 00:04:24,133 --> 00:04:27,833 k is equal to 8 plus 24l for some integer l. 92 00:04:27,833 --> 00:04:30,900 If I plug all this in, I get x 
is equal to 4 plus 25k. 93 00:04:30,900 --> 00:04:35,533 So plug in 8 plus 24l, simplify, I get 204 plus 600l. 94 00:04:35,533 --> 00:04:38,000 Thus, x is congruent to 204 mod 600. 95 00:04:38,000 --> 00:04:39,000 96 00:04:39,000 --> 00:04:43,533 Now I should mention at this point that students 
did get a calculator, I believe, on this exam, 97 00:04:43,533 --> 00:04:46,266 which is fine. I mean, we could do the 
computations without a calculator. 98 00:04:46,266 --> 00:04:49,166 I think it's kind of fun to challenge 
yourself and to do that. 99 00:04:49,166 --> 00:04:51,533 It's very good practice, it's 
very good for your mind too. 100 00:04:51,533 --> 00:04:54,000 Even though they are little 101 00:04:54,000 --> 00:04:56,966 simplistic computations, I still 
think it's good for your mind to do. 102 00:04:56,966 --> 00:04:59,566 It's kind of like a Sudoku puzzle but in math. 103 00:04:59,566 --> 00:05:03,566 I guess a Sudoku puzzle is math. Okay, anyways, not the point. 104 00:05:03,566 --> 00:05:05,566 The point is 105 00:05:05,566 --> 00:05:07,733 you could do these combinations 
by hand, it's not too, too bad. 106 00:05:07,733 --> 00:05:10,533 107 00:05:10,533 --> 00:05:13,566 On an exam, you should 
always check your answer. 108 00:05:13,566 --> 00:05:15,166 109 00:05:15,166 --> 00:05:17,566 Here it's a little bit big, but 
you could still do it, right? 110 00:05:17,566 --> 00:05:23,566 If I take 204 times 11 and subtract 
12 and divide by 24, I should get 0. 111 00:05:23,566 --> 00:05:27,833 It's worth checking out that 204 
actually is a solution to this, 112 00:05:27,833 --> 00:05:30,866 and if it is, you should firmly 
believe that your answer is correct 113 00:05:30,866 --> 00:05:33,133 because the answer - once you find one solution, 114 00:05:33,133 --> 00:05:36,733 you know that the moduli is just the product 
of 24 and 25 because they're co-prime 115 00:05:36,733 --> 00:05:41,000 that's by Chinese Remainder Theorem, 
and that should give you all solutions. 116 00:05:41,000 --> 00:05:44,733 So these are checkable on an exam. 
I strongly advise that you do that. 117 00:05:44,733 --> 00:05:45,766 118 00:05:45,766 --> 00:05:48,266 Here I won’t, I’ll leave it to you to double-check, 119 00:05:48,266 --> 00:05:51,233 but very good to not get this 
type of question wrong, right? 120 00:05:51,233 --> 00:05:55,233 If you get asked this kind of question you can check the answer so just check the answer. 121 00:05:55,233 --> 00:05:57,066 122 00:05:57,066 --> 00:05:59,366 Okay that's it. So that's question 1, 123 00:05:59,366 --> 00:06:00,600 124 00:06:00,600 --> 00:06:01,433 good luck.