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 x is congruent to 5 mod 17
and 2x is congruent to 3 mod 11.
Okay.
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? Option 1 is we can -
well we have lots of options, let me throw out a couple of options though.
Option 1 is to take x is congruent to 5, and write this as x equals 5 plus 17k,
plug that into the second equation, solve,
in the end we're going to get some solution that's unique
mod 17 times 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 equal to 5 plus 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 textbf, solution.
So here,
with the second equation, what do we want to do?
Well we want to write this as x is congruent to something mod 11, right?
And 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 times 2 is -
2 times 1 is 2, it's not 1. 2 times 2 is 4, it's not 1,
6, 8,
now 10. 2 times 2 is -
or 2 times 5 is 10,
and 10 is the same as negative 1 mod 11.
So if I use negative 5, which is 6,
so 2 times [6] which is 12,
and reduce that mod 11 I should get 1.
So solution, notice that…
and so multiplying both sides of equation 2…
as follows.
Oh, sorry. Opened a new tab.
Command s, not command t. Okay.
So since 2 times 6 is 1 mod 11 and
multiply both sides of equation 2 by 6 gives the equivalent system…
probably not 17,
but so 6 times 2 is 12, 12 is 1,
so that's the same as that, and then 6 times 3 is 18,
and 18 mod 11 is 7 not 17 so let's change 17.
So great, okay.
The Chinese Remainder Theorem
now says that
there is a unique
solution modulo
17 times 11, which is…187?
Does that sound right? That sounds good.
So the Chinese Remainder Theorem now says that there's a unique solution modulo [187].
So I should maybe mention why I can use the Chinese Remainder - valid since
the gcd of 11 and 17 is equal to 1.
Okay, great.
So now we know there's a unique solution
modulo 187, okay?
So now we'd like to know all the total solutions between negative 1500 and 1500.
This is a range of…
okay, so let's be exact here, okay? So...
so we want to know…
let's give the solution a name.
Call this solution a.
Hence, all solutions are given by
x is equal to a plus 187k,
where k is an integer.
So all solutions to this
are given by x is equal to a plus 187k.
Where k is an integer, I guess we should maybe be precise. Okay,
do you want to solve this? Yeah maybe we should solve this.
Can we eyeball the solution? Nah, you know what? Let's not eyeball the solution,
let's just actually do it. Well okay I guess actually…
yeah that's actually it. So in class, the 5 and the 7 ended up being equal
and here they're not.
what are we going to do? Let’s…
what do I want to do? Do I really want to go through it? Yeah let's go through it, what the heck, okay.
To find a,
we use the fact that
x is equal to 5 plus 17l,
for some integer l,
and plug into the second equation to yield
5 plus 17l is equivalent to 7
mod 11.
So we're going to use the fact
that well if x is congruent to 5 mod 17, that means that x is equal to 5 plus 17l
for some integer l. I'm going to plug that into the second equation, what are we going to get?
We're going to get 5 plus 17l is congruent to 7 mod 11.
Simplifying gives…
so 17 is the same as 6,
and this is equivalent to 2 mod 11.
We can use
Congruences
and Divisibility from our course.
We can divide by 2,
since the gcd of 2 and 11 is 1.
To get that…
actually I don't even want to do that, yeah maybe I do.
So we're going to get that 3l is equivalent to 1 mod 11.
Multiplying by 4
gives us that well 12l - so…
gives us that l is congruent to
4 mod 11.
So 11 is equal to 4 plus 11m.
For some integer m.
Plugging back in yields x is equal to 5
plus 17 [times] 4 plus 11m,
giving x is equal to 17 times 4,
68, 73, 73 plus 187m.
Alright, excellent. So we know what the answer is.
Well we know that x is equal to 73 plus 187m. So
now let's plug it into the condition, right? So we have bounds on x,
right, which are given by
negative 1500 to 1500.
So x is [between] negative 1500 and 1500, and -
oh by the way, I guess before we go on, we should always double check our answer, right?
So x is equal to 73 plus 187m.
So let's just plug that into here, so 73
minus 7 is 66,
which is divisible by 11, so that’s good. 73 minus 5 is 68,
and I'm hoping that 4 times 17 is 68, I believe it is.
So, fantastic, okay.
So this actually is the solution, and the Chinese Remainder Theorem says that
of this form gives us all solutions.
So since this is the case, I can plug in this x value.
So x is 73 plus 187m.
Simplifying yields - so if I subtract 73 from either side,
I get negative 1573 is less than
187m, which is less than
1427, let’s see if that looks good.
Let’s see what we have here.
So since x is bounded in this range, we have that
negative 1573 is less than 187[m] is less than
1427.
I'm subtracting 73 from either number.
That looks good.
Now the question is how many times is 187…
or how many multiples 187 lie in this range?
So if we think about it, do I want to do this by hand or not?
I mean, 187 times 10 is [1870],
and then I'd have to subtract a couple multiples of 187.
Am I in the mood to do this or do I just want to pull up the old calculator?
187 times 7, 9, 4, 0…
you know what, let's just do it just so that it's easier to see.
The odds of me doing it correctly on a video are probably pretty small anyways.
Okay, so 187,
how many times does it go into these numbers? So 1427
divided by 187,
7 times.
So let's simplify once more.
So 7.63, so m is definitely less than 7.6,
and let's go the other way, 1573
divided by 187,
8.4.
So this is going to be - so m is going to be at least…
whatever, at least negative 8.3.
Fantastic. So how many integers is this?
What is that? There’s…so what is this?
It’s between 7 and negative 8 as an integer,
so 7 minus negative 8 is 15
plus 1 is 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 is congruent to 5 mod 17
and 2x is congruent to 3 mod 11.
By simplifying the second equation, or finding the inverse of 2,
we saw this is equivalent to x is congruent to 5 mod 17, and x is congruent to 7 mod 11.
We use the Chinese Remainder Theorem to find our solution
that was given by 73 plus 187m
where m ranges over the integers, any of these will work
because 187 is 11 times 17, and that’s congruent to 0
mod 17 and mod 11.
Plug it in, simplify,
and when you get to this point, 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.