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 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. 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.
Question: Solve the following system of linear congruences:
$$\begin{align*} 11x&\equiv 12\pmod{24}\\ x&\equiv 4 \pmod{25} \end{align*}$$So if you see a question like this, you should be jumping for joy. 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, I am going to start with this equation. So by definition, $x=4+25k$ for some $k\in\mathbb{Z}$.
We're going to take this, we're going to plug it into the first equation. What are we going to get?
$$11(4+25k)\equiv 12 \pmod{24}$$That’s great, so let’s simplify.
$$\begin{align*} 44+275k&\equiv 12 \pmod{24}\\ 20+35k&\equiv 12 \pmod{24}\\ 11k&\equiv 16 \pmod{24} \end{align*}$$So we thing we can do, and I probably should have mentioned this in the stream, is reduce $25 \bmod {24}$ when I first plugged in $x$, that would have given me $1$, and I would have immediately gotten that $11k\equiv 16\pmod{24}$, but I didn't do that. If you don't see all these tricks it's okay.
Now at this point you have options. I always like to try to find the inverse of the number $\bmod 24$. So again $\gcd(11,24)=1$ because $11\nmid 24$ and $11$ is prime.
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 with $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 $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+24=120$, $120$ is close to a multiple of $11$, really close, $120$ is really close to $121=11^2$, right, so I know $11\cdot 11=121\equiv 1 \bmod{24}$.
$$\begin{align*} 11\cdot 11k&\equiv 11\cdot 16\pmod{24}\\ 121k&\equiv 176 \pmod{24}\\ k&\equiv 8\pmod{24} \end{align*}$$So what am I doing here? I'm finding the inverse of $11$. $11$ happens to be a self inverse $\bmod {24}$. So $11\cdot 11\equiv 1 \bmod{24}$, which is cool, and it doesn't happen over the real numbers, right? It's only $\pm 1$ that if I square it I get $1$, but $\bmod {24}$ sometimes things like $11^2$ can give you $1$. So it's pretty neat, and it does work.
So, great, so I have $k\equiv 8\pmod{24}$, so therefore $k=8+24\ell$ for some $\ell\in\mathbb{Z}$.
$$\begin{align*} x&=4+25k\\ &=4+25(8+24\ell)\\ &=204+600\ell \end{align*}$$Thus, $x\equiv 200\pmod {600}$.
Now I should mention at this point that the 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, anyway, 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\cdot 11)-12$, I should get a number divisible by $24$. 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 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.