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 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.
Solve the congruence equation in $\mathbb{Z}_{11}$ given by
$$[3][x]+[4][y]=[5]\\ [5][x]+[2][y]=[1]$$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 here is the full solution, and then we will discuss it.
Changing to a congruence gives
$$\begin{align*} 3x+4y&\equiv 5 \mod {11}\\ 5x+2y&\equiv 1 \mod{11} \end{align*}$$Taking double the second equation from the first (that is, eliminating $y$) gives
$$-7x\equiv 3 \mod{11}$$Here, we can find the inverse of $(-7)$ by either guessing or using the Extended Euclidean Algorithm. Since we only have to try $10$ numbers at worst let's guess. Notice that
$$-7(3)\equiv -21\equiv -21+2(11)\equiv 1\mod{11}$$Thus, multiplying the previous equation by $3$ gives
$$x\equiv 9\mod{11}$$Substituting back into the first equation gives
$$\begin{align*} 3(9)+4y&\equiv 5\mod{11}\\ 27+4y&\equiv 5\mod{11}\\ 5+4y&\equiv 5\mod{11}\\ 4y&\equiv 0\mod{11}\\ 4^{-1}\cdot 4y&\equiv 4^{-1}\cdot 0\mod{11}&&\text{Inverse exists since }\gcd(4,11)=1\\ y&\equiv 0\mod{11} \end{align*}$$Hence, the solution is given by $[x]=[9]$ and $[y]=[0]$.
Starting from the beginning, because I prefer to deal with congruences, I'm going to immediately swap this into congruence equations. So the congruence equations are $3x+4y\equiv 5 \mod {11}$, and $5x+2y\equiv 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 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.
$$-7x\equiv 3 \mod{11}$$Now we could make the $-7$ into $4$ and deal with that, but I'm just going to leave it as $-7$ and we're going to try to find the inverse of $-7$, right, this is our goal now.
Our goal now is to isolate for $x$ and we'd like to divide by $-7$, but that doesn't really make sense. 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 $-7$. Now there's two ways we can do this, well there's lots of ways we can do this. We could guess, we can use the Extended Euclidean Algorithm, since $11$ happens to be prime, we can compute $(-7)^9$, right, $p-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 $-7(3)=-21$.
So by the way, why did I use $3$? Well okay $1$ and $2$ didn't work, so let's try $3$. $-7(3)=-21$, and if I add $22\equiv 0\mod{11}$, that's going to give us the $1$.
So it turns out that $3=7^{-1}$. So if I multiply both sides of this congruence by $3$, I get
$$x\equiv 9\mod{11}$$So that gives us our $x$ value. The solution for $x$ is $x\equiv 9\mod{11}$, we plug that in, and we can get our $y$ value from this.
$$\begin{align*} 3(9)+4y&\equiv 5\mod{11}\\ 27+4y&\equiv 5\mod{11}\\ 5+4y&\equiv 5\mod{11}\\ 4y&\equiv 0\mod{11}\\ 4^{-1}\cdot 4y&\equiv 4^{-1}\cdot 0\mod{11}&&\text{Inverse exists since }\gcd(4,11)=1\\ y&\equiv 0\mod{11} \end{align*}$$So by the way, $4$ is invertible because it's co-prime to $11$, same with $-7$ we found the inverse of earlier. $\gcd(7,11)$. Here $\gcd(4,11)=1$, they’re co-prime, so $4$ has an inverse whatever it is, so multiply both sides by the inverse and I get $y=0$.
Hence the solution is given by - well remember we started our question with the square bracket notation, equivalence class notation, so we should probably finish the question with the equivalence class notation. So $[x]=[9]$ and $[y]=[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 the 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.