In the previous video, we have introduced this particular notation, which is called
a congruence relation. This notation simply means that the difference between the two
numbers on each side of the congruent sign is divisible by the modulus. We have also
shown in the previous video that it resembles an equal sign when it comes to addition and
multiplication. In fact, by introducing these two operations, we have already stumbled onto
modular arithmetic. There are more properties that we can talk about in modular arithmetic,
and by looking at them, the congruence sign really behaves like an ordinary equal sign.
However, all these properties do not include division, and that is for a good reason.
Let’s consider this congruence relation. If we divide both sides by 7, we arrive at
a some nonsense, because these kinds of relations only make sense for integers. So is it that
if after division all the numbers are integers, then the congruence relation holds? Let’s
consider this case. If we divide both sides by 2, even though all numbers here are integers,
this is still nonsense. However, this does not mean that we can never do division. Consider
another case. If we now divide both sides by 2, this new relation makes perfect sense.
So what can we conclude here? Let’s just compare the two different cases together.
The most important difference is the modulus used. The case that works uses odd modulus,
while the case that doesn’t work uses even modulus. We can appropriately generalize to
this statement: when dividing by 2 on both sides, we need the modulus to be odd. In fact,
we can further generalize this like so: if ka congruent kb modulo m, then we can divide
both sides by k, provided that k and m are coprime. This is our first rule for division.
We can prove this pretty easily. Given this congruence relation, then there must exist
an integer lambda where this equation holds. We now just write it in another way. Since
k and m are coprime, in order for the product on the left to be divisible by m, that means
a-b must be divisible by m. Here lambda dash is just another integer. So we can conclude
that a is congruent to b modulo m. However, this rule of division relies on the fact that
k and m are coprime, so what if they are not coprime?
We take inspiration from the previous cases again. Although the conclusion does not make
any sense, if we tweak it a little bit, it would make sense. Here, 3 is obtained when
we divide 6 by 2. When we generalize this, we get the second rule for division on modular
arithmetic. This is actually easier to prove. Starting with the given information, we must
have this equation when lambda is an integer. By simplifying, we get the ultimate congruence
relation we need. However, we are not done yet. These two rules rely on the fact that
both sides of the relation have the same factor. What if these two numbers are coprime? The
reason we need to consider such cases is that sometimes we would encounter this type of
equation, called linear congruence equation. Actually if you have watched the previous
video, you have already seen it. In the previous video, we considered this system of equations.
We only focus on the case when all these m’s are mutually relatively prime. Now, if we
ignore the first equation, we would have the solution to be k times the product of all
the m’s except for m_1. Now if we substitute this solution back to the first equation,
we have this. Now for this equation, everything in white is known constants, and we need to
solve for k. This is basically in the form ax congruent to b modulo m, where we need
to solve for x, which is exactly the linear congruence equation that we want to solve.
You will expect that the answer is x congruent to something modulo m, but we know that we
cannot directly do division by a on both sides due to reasons you have seen before. The more
frustrating thing is that we know that a solution must exist so long as all the m’s are mutually
coprime, and we don’t know how to obtain the solution. So what should we do?
Again, there are several different cases for us to consider. First, if a and m are not
coprime, and b is not divisible by their greatest common divisor, then there is simply no solution
for this linear congruence equation. This can be proved rather easily. The congruence
equation means ax - b = m*lambda where lambda is an integer. Rearranging, we have ax - m*lambda
= b. If a and m are not coprime, then let's say their gcd is k, then b has to be k times
something. If b is not divisible by k, there is no solution to this, and thus the original
equation. The second case is where a and m are not coprime, and b is divisible by their
gcd. In this case, we could use this second rule of division on modular arithmetic to
reduce this case into the third case, where a and m are coprime. To tackle this third
case, we need something quite tricky. Let's say there is another integer k, so that k
times a is congruent to 1 modulo m, then now if we multiply both sides by k, then we would
have x congruent to kb modulo m, which will be the solution. But why does it work? Must
there be an integer k so that ak congruent to 1 modulo m? Yes, and the proof of this
is quite involved.
Consider the numbers a, 2a, all the way to (m-1)a. We claim two things: none of these
numbers are divisible by m, and no two numbers here leave the same remainder when divided
by m, that means no two numbers here are congruent modulo m. For the first claim, let's suppose
ja is divisible by m. Since a and m are coprime, j is divisible by m. However, j should be
the values from 1 to m-1, none of which is divisible by m, so there exists a contradiction.
Hence, there is no such j in the first place, and so the first claim is proved. For the
second claim, again let's suppose ia congruent to ja modulo m. Then (i-j) times a is divisible
by m. Now, both I and j are taken from 1 to m-1, and so their difference must be smaller
than m, and so according to the first claim, there is again a contradiction, and thus the
second claim is also correct. With these two claims, consider the remainders when all these
numbers are divisible by m. Here, 0 is not an option due to the first claim, and no two
numbers should have the same remainder, each number should have a unique remainder from
1 to m-1. That means that there must be one number which has remainder 1 when divided
by m. So there has to be a number k so that ak congruent to 1 modulo m, and so this method
of attacking the equation works.
However, the problem is, of course, how exactly do we find this number. We would use the example
here to illustrate the entire process. Now, you can see that 31 and 415 are coprime, and
so we directly go to the third case and figure out the number k such that 31k congruent to
1 modulo 415. We first consider the continued fraction expression of 415 over 31 and then
we
now consider the penultimate continued-fraction convergent. This can be done by using the
property mentioned in the first-ever video on Mathemaniac. Now, we will consider the
products of red and yellow numbers separately. We can clearly see that they are one apart.
Now what we know is that 31 times 174 is one less than a multiple of 415, so we have this
negative number on the right side. It is a little weird to use negative numbers, but
eventually we are looking for the difference between the two numbers on each side, so we
are good here. Now we multiply both sides by -1, and finally, add 31 times 415 on the
left side to get this. Finally multiply both sides by 9 to get this yellow congruence relation.
So by comparing with the original equation we started off with, we get x congruent to
2169 modulo 415. This is a valid solution, but you might want to make it smaller. This
is done by considering its remainder when divided by 415. So we can get an equivalent
solution. If you don’t believe me, you can check that this equation is true.
As a summary of the entire process, we first consider the continued fraction expression,
like 415 over 31 in the example. Then we consider the second-to-last continued fraction convergent.
It can be done directly or using the property of continued fraction mentioned in the first
ever video on Mathemaniac. Then do a cross multiplication to see which product is bigger.
Finally do some polishing on modular arithmetic to get the final answer. For example, in the
case above, we need to multiply by -1 before multiplying by 9.
To prove that this always works, we still need the property mentioned in the first video.
So we copy this property here, and consider this expression. Then we simply do some algebraic
manipulation. Now focus on these two white boxed expressions. They are basically identical
with the subscripts off by 1. That means if we consider the sequence of numbers like this,
because we have the negative sign, if we denote the first number as a, then this sequence
would be just oscillating with a and -a. But what is the value of a? We first figure out
the values of p_0, q_0, p_1 and q_1. Then we can start calculating a.
Now that we know a is 1, that means the original sequence is made up of 1 and -1. That means
by doing cross product between the two consecutive continued fraction convergents, we get either
1 or -1. Actually we can pinpoint exactly whether it is 1 or -1, but it might be easier
to just check the units digit of the cross products. So now we have fully justified why
we can use the continued fraction method to find out the solution of a linear congruence
equation. In fact, the value of k such that ak is congruent to 1 modulo m, is known as
the multiplicative inverse of a modulo m, denoted as power -1. Here, we are not saying
k congruent to 1 over a, because this notation is only valid for integers, but since it *behaves*
like one, we use this notation of power -1. This is similar to the notation of a matrix
inverse. We are not saying 1 divided by a matrix, but it again *behaves* like so, so
we use this notation.
So now going back to the rules of division on modular arithmetic, even if the two numbers
on both sides are coprime, we can still quote unquote divide both sides by a number k by
considering its inverse modulo m, and of course k has to be coprime with m, otherwise the
inverse of k modulo m would not exist.
I understand that this might be a little different from the videos that I have previously produced,
as this is more like a lecture or a crash course in modular arithmetic, which I admit
is boring, but I feel that this video is necessary as a continuation of the previous video and
because not every viewer of mine knows modular arithmetic. The reason I know this is that
there is a Google form linked in the description that asks for your math levels, and some of
my viewers responded. This form is crucial for me to know your Math levels so that I
know how much detail I need to go into when introducing the background knowledge required
for the video, so please fill in that form linked in the description to help me as a
content creator.
Here is a list of ideas for future videos. I don’t know exactly when I will post them
so I don’t want to make any promises here. So if you want to see these videos, be sure
to subscribe with notifications on so that you don't miss out any of the videos that
I will upload. If you enjoyed this video, give it a like and if you happen to see one
of my videos on the suggested, click on it to help support this channel. See you in the
next video!