Hello everyone. In this video, we're going to talk about a problem that we did as a clicker question, and it's the following CRT problem. I've slightly modified the numbers, but the idea will be the same.
Find the number of integer solutions to
$$\begin{align*} x&\equiv 5 \mod {17}\\ 2x&\equiv 3\mod{11} \end{align*}$$with $-1500< x < 1500$.
Again, I advise trying the problem out first and then watching the video if you get stuck.
So in this case, what are we doing? How are we going to do it? We have two options, right? Well we have lots of options, let me throw out a couple of options though.
Option $1$ is to take $x\equiv 5\bmod{17}$, and write this as $x=5+17k$, plug that into the second equation, solve, in the end we're going to get some solution that's unique $\bmod {17(11)}$, and we can run through that.
Option $2$, we can take the second equation and we can modify it so that it looks like it's of the form for the Chinese Remainder Theorem, and then we have two options. $1$, solve it explicitly, or $2$, note that a solution must exist since $17$ and $11$ are co-prime. If $17$ and $11$ weren't co-prime, then you would have to go down that first route where you just make $x=5+17k$, plug it into the second one, rearrange, and hope for the best, but here we have a couple options.
So let's do the second option. Let's change this into something with the form of Chinese Remainder Theorem.
So here, with the second equation, what do we want to do? Well we want to write this as $x\equiv\text{something}\bmod{11}$. So the way to do that is to invert $2$. So we're going to try to find the number that when I multiply $2$ by something, I'm going to get $1$.
If you think about it, $2(1)=2\neq 1$. $2(2)=4\neq 1$. $2(5)=10\equiv -1\bmod{11}$. So if I use $-5\equiv 6 \bmod{11}$, so $2(6)=12$, and reduce that $\bmod {11}$ I should get $1$. So I multiply both sides of equation $2$ by $6$ to get
$$\begin{align*} x&\equiv 5 \mod {17}\\ x&\equiv 7\mod{11} \end{align*}$$The Chinese Remainder Theorem now says there is a unique solution modulo $17(11)=187$. So I should maybe mention why I can use the Chinese Remainder Theorem, it is valid since $\gcd(11,17)=1$.
So now we know there's a unique solution modulo $187$. So now we'd like to know all the total solutions between $-1500$ and $1500$.
Let's give the solution a name. Call the solution $a$. Hence, all solutions are given by
$$x=a+187k$$where $k$ is an integer.
So in class, the $5$ and the $7$ ended up being equal and here they're not. So what are we going to do? To find $a$, we use the fact that $x=5+17\ell$, for some integer $\ell$, and plug in to the second equation to yield
$$5+17\ell\equiv 7 \mod{11}$$Simplifying gives
$$6\ell\equiv 2\mod{11}$$We can use Congruences and Divisibility from our course. We can divide by $2$, since $\gcd(2,11)=1$.
$$3\ell\equiv 1 \mod{11}$$Multiplying by $4$ gives
$$\ell\equiv 12\ell \equiv 4 \mod{11}$$So $11=4+11m$ for some integer $m$. Plugging back in yields $x=5+17(4+11m)$, giving $x=73+187m$.
Alright, excellent. So we know what the answer is. Well we know that $x=73+187m$. So now let's plug it into the condition, right?
By the way, I guess before we go on, we should always double check our answer, right? So $x=73+187m$. So let's just plug that into the original two equations. So for $x\equiv 5\mod{11}$
$$\begin{align*} x&\equiv 7 \mod{11}\\ 73+187m&\equiv 5 \mod{11}\\ (73-5)+(0)m&\equiv 0 \mod{11}\\ 66&\equiv 0 \mod{11}\\ 0&\equiv 0 \mod{11} \end{align*}$$That is a true statement so we're good there. Let's check out the second equation.
$$\begin{align*} x&\equiv 5 \mod{17}\\ 73+187m&\equiv 5 \mod{17}\\ (73-5)+(0)m&\equiv 0 \mod{17}\\ 68&\equiv 0 \mod{17}\\ 0&\equiv 0 \mod{17} \end{align*}$$So that equation is good too. So this actually is the solution, and the Chinese Remainder Theorem says that of this form gives us all solutions.
So since we have $-1500 < x < 1500$, I can plug in this x value.
$$-1500 < 73+187m < 1500\\ -1573 < 187m < 1427\\ -8.3 < m < 7.6$$Now the question is how many multiples of $187$ lie in this range? So how many integers is this? It’s between $7$ and $-8$ as an integer, so $7-(-8)=15+1=16$. So hence, there are $16$ integers.
So on an exam, you should expect that the numbers work out a lot nicer. So for example, in the clicker question that we did for this week, the numbers turned out a lot nicer than they did here. Here I did use a calculator just to keep my life a little easier.
Okay so let's take a step back and let's go through what we did, okay? So we started with the system $x\equiv 5\bmod{17}$ and $2x\equiv 3\bmod{11}$.
By simplifying the second equation, or finding $2^{-1}$, we saw this is equivalent to $x\equiv 5\bmod{17}$, and $x\equiv 7\bmod{11}$.
We use the Chinese Remainder Theorem to find our solution that was given by $x=73+187m$ where $m$ ranges over the integers, any of these will work because $187=11(17)\equiv 0\bmod{17}$ and $\bmod{11}$.
Plug it in, simplify, and when you get to the point of simplifying the range of $x$, you either guess and check, or use a calculator like I did, find out there are only $16$ integers.
So this gives you a little bit of practice with the Chinese Remainder Theorem with these types of arguments. That I think is all I have to say. Thank you very much for your time, and hopefully this helps you out.