Hello everyone.
In this sequence of videos, we’re going to talk about the solutions to an old
Math 135 exam from the University of Waterloo.
This was the Fall 2000 exam available on the MathSoc Exam Bank.
This was meant to be a live stream performance, but
the live stream…
I was using Twitch and for some reason it wasn't working,
it kept crashing, so after an hour I decided to
call an audible and say okay we're not going to do this as a live stream,
we're going to be as an offline session and I will put the videos online after the fact.
So the first two problems we actually did manage to cover in the online session,
which - I had some questions, I’m going to hopefully answer them all in this video,
and if not again throughout this video series
do feel free to send me an email if you need a clarification about something.
I’m more than happy to help.
So first question of the exam was solve the following system of linear congruences
11x is congruent to 12 mod 24 and x is congruent to 4 mod 25.
So if you see a question like this, you should be jumping for joy.
This question -
there's really only one way to attack it, it's a Chinese Remainder Theorem type question,
and you have to use some sort of Chinese Remainder Theorem type arguments, okay?
So I'm going to happily go through this with the Chinese Remainder Theorem.
Because in the second equation x is already isolated, x is congruent to 4 mod 25,
I am going to start with this equation.
So by definition, x is equal to 4 plus 25k for some integer k.
We're going to take this, we're going to plug it into the first equation. What are we going to get?
We're going to get 11 times 4 plus 25k is congruent to 12 mod 24.
That’s great, so let’s simplify.
So we thing we can do, and I probably should have done something, or mentioned this, in the stream,
is reduce 25 mod 24,
that would have given me 1, and I would have immediately gotten that
11 times 25 is congruent to 11k,
but I didn't do that. If you don't see all these tricks, it's okay.
So I just decided to multiply it out, so 11 times 4 is 44 plus 275k
is congruent to 12 mod 24.
I know that 240 is a power -
or a multiple 24 close to 275,
so if I subtract by 240, I get 35k.
44 subtracted by 24 is 20.
So that gives me 20 plus 35k is congruent to 12 mod 24.
Bring the 20 over I get negative 8, negative 8 plus 24 is 16.
35 I can reduce one more time, like I said earlier, and I get
11k is congruent to 16 mod 24.
Okay, so that's great.
Now at this point you have options.
I always like to try to find the inverse
of the number mod 24. So again the gcd of 11 and 24 is
definitely 1 because 11 doesn't divide 24 and 11 is prime.
So that's fantastic, so I know that the inverse exists,
and I kind of find it fun to try to find the inverse of these numbers, so I always try to do it.
It's not necessarily always easy, but I did give it a shot.
Now, in the live stream, I actually struggled a little bit
until I started doing it intelligently and instead of counting by multiples of 11,
I counted by multiples of 24 and tried to recognize a multiple of 11 near one.
So I started 24, the closest multiple of 11 near 24 is 22.
48 closest multiple of 11 near there is 44, that's not going to give me 1.
So 24, 48, 72 is the next one,
that's not close to 77 or 66.
So let's do it again, 96 it's close to 99, but not close enough.
96 plus 24 is 120,
120 is close to a multiple of 11,
really close, 120 is really close to 121, which is 11 squared,
right, so I know if I multiply 11 by 11, I get
121, and because 120 is the same as 0 mod 24,
I know that 121 will reduce to 1.
So if I multiply both sides by 11,
I can reduce the left-hand side down to 1,
and I can reduce the right-hand side down to 11 times 16, that's 176,
and if I subtract 120, I get 56. So subtract
48, I get k is congruent to 8 mod 24.
So what am I doing here? I'm finding the inverse of 11.
11 happens to be a self inverse mod 24.
So 11 times 11 happens to be 1,
which is cool, and it doesn't happen over the real numbers, right? It's only
plus or minus 1 that if I square it I get 1,
but mod 24 sometimes things like 11 squared can give you 1.
So it's pretty neat, and it does work, okay?
So, great, so I have k is congruent to 8 mod 24, so therefore
k is equal to 8 plus 24l for some integer l.
If I plug all this in, I get x is equal to 4 plus 25k.
So plug in 8 plus 24l, simplify, I get 204 plus 600l.
Thus, x is congruent to 204 mod 600.
Now I should mention at this point that students did get a calculator, I believe, on this exam,
which is fine. I mean, we could do the computations without a calculator.
I think it's kind of fun to challenge yourself and to do that.
It's very good practice, it's very good for your mind too.
Even though they are little
simplistic computations, I still think it's good for your mind to do.
It's kind of like a Sudoku puzzle but in math.
I guess a Sudoku puzzle is math. Okay, anyways, not the point.
The point is
you could do these combinations by hand, it's not too, too bad.
On an exam, you should always check your answer.
Here it's a little bit big, but you could still do it, right?
If I take 204 times 11 and subtract 12 and divide by 24, I should get 0.
It's worth checking out that 204 actually is a solution to this,
and if it is, you should firmly believe that your answer is correct
because the answer - once you find one solution,
you know that the moduli is just the product of 24 and 25 because they're co-prime
that's by Chinese Remainder Theorem, and that should give you all solutions.
So these are checkable on an exam. I strongly advise that you do that.
Here I won’t, I’ll leave it to you to double-check,
but very good to not get this type of question wrong, right?
If you get asked this kind of question you can check the answer so just check the answer.
Okay that's it. So that's question 1,
good luck.