Hello everyone. In this video, we're going to talk about
solving a congruence equation.
Now...
this time I've actually written out the solution,
so we'll just talk about the solution as a change of pace.
This is actually not
an extremely…
it's actually something that you know, and I want to put it like this. It's pretty straightforward,
you're going to do sort of the things that you already suspected
from high school sort of solving linear equations.
It's the same techniques that will apply here.
So solve the congruence equations in Z 11 given by the following two equations, okay?
So by the way, something to keep in mind, this is different from
Chinese Remainder type problems, if you've seen these,
because we have two variables here. Two variables
and two equations, so two unknowns two equations, we should be able to solve this.
It holds true over just integers and it's still going to hold true over
the integers modulo m.
So because I prefer to deal with congruences, I'm going to immediately
swap this into a congruence… congruence equations.
So the congruence equations are 3x plus 4y equals 5 mod 11,
and 5x plus 2y is congruent to 1 mod 11.
Now when you get to this point, you can use any
technique you want. Isolating for one of the variables is going to be tricky
because then you have to find an inverse and it's usually just easier to eliminate.
So here we're going to use elimination. We're going to take -
notice that 4 and 2 - so 2 times 2 is 4, so we're going to take
double the second equation away from the first,
and what is that going to give us? So we're going to eliminate the y’s,
so that's going to be 5 minus 2 that's 3,
and 3 minus 2 times 5 which is 10
so 3 minus 10 and that's negative 7.
Now we could make the negative 7 positive 4 and deal with that, but
I'm just going to leave it as minus 7 and we're going to try to find the inverse of minus 7,
right, this is our goal now. Our goal now is to isolate for x and we'd like to divide by negative 7,
but that doesn't really make sense. We need to take…
we can't just divide, right? We've already talked about division
in these linear congruences.
But what we can do instead of dividing is we can
find the inverse and multiply by the inverse, which is basically dividing.
So here we want to find the inverse of minus 7.
Now there's two ways we can do this, well there's lots of ways we can do this.
We could either…we could guess,
we can use the Extended Euclidean Algorithm, we could also compute -
because 11 happens to be prime, we can compute minus 7 to the power of
9, right, p minus 2, that we saw in class,
and if we compute that, that's also the inverse.
However, that might not be any easier than
doing the other things that I've suggested.
Since we only have ten numbers to try, let's just guess. That sounds like the easiest way to do this.
So when we guess, what do we get? Well
negative 7 times 3, that's minus 21.
So by the way, why did I use 3? Well okay 1 and 2 didn't work,
So let's try 3. 7 times 3 is minus 21,
and if I add 22, which is the same as 0 mod 11,
that's going to give us the 1.
So it turns out that 3 is the inverse of minus 7.
So if I multiply both sides of this congruence by 3,
the left-hand side becomes just x, and the right-hand side becomes 3 times 3 which is 9.
So that gives us our x value. The solution for x
is x is congruent to 9 mod 11, we plug that in,
and we can get our y value from this.
So let's do that, so we're going to have 3 times 9 plus 4y is equal to 5.
Plug it in, reduce,
the 5’s actually cancel and we're actually left with 4y is congruent to 0,
that's easy to solve. Whatever the inverse - so by the way,
4 is invertible because it's co-prime to 11,
same with minus 7 up there. Minus 7 and 11 are…
the gcd between minus 7 and 11 is 1.
Here the gcd between 4 and 11 is also 1, they’re co-prime, so
4 has an inverse whatever it is,
so multiply both sides by the inverse and I get y equals 0.
You know what? Maybe I'll even put in that extra step,
just to show what happened here.
So there we go. So what happened here?
Well I multiply both sides by the inverse, which I know exists,
and that's going to give me y equals 0.
Maybe I should make a note here that the inverse exists.
Inverse exists since
gcd of 4 and 11 is equal to 1.
Let's see how that looks.
And hence the solution is given by - well remember we started our
question with the square bracket notation, the equivalence class notation,
so we should probably finish the question with the equivalence class notation. So
x is equal to 9 and y is equal to 0 is the set of solutions.
And that's it.
So again sort of a “follow your nose” proof. Once you change to congruence land,
you can just treat it like equality and deal with it like you normally would.
Everything passes through, you're allowed to add and subtract and multiply equalities,
those are all the Properties of Congruences,
and you're allowed to simplify and get to sort of a final answer.
Well you're allowed to get to the final answer.
That's all I have to say for this. So
thank you very much for tuning in, and hopefully this
gives you a little bit of a boost.