This video will be split into three major parts: exploring the ancient Chinese problem,
a mathematical tool that LaGrange took credit for, and finally the connection. If you want
to marvel at the connection, you really have to watch it all the way through.
So here comes the ancient Chinese problem: there are a number of objects on the table.
If you count them in groups of 3, 2 will be left ungrouped; in groups of 5, 3 will be
left ungrouped; in groups of 7, 2 will be left ungrouped. What is the smallest number
of objects? The numbers here are not very large, so you can start by trial and error,
and get the answer to be 23. Let’s just check that it is true. It leaves a remainder
of 2 divided by 3, a remainder of 3 divided by 5, and remainder of 2 when divided by 7,
so 23 definitely satisfies all three conditions. But if the numbers are much larger, how can
you derive the answer?
We first introduce a notation that will make our discussion a lot more systematic. We write
a congruent to b modulo m, if a leaves a remainder of b, when divided by m. When you think about
it, the notion of remainder means a = km+b, for some integer k. If we rearrange this equation,
a-b = km, so a-b is divisible by m. This is what I want you to think of when you see this
notation.
If we have a congruent to b and c congruent to d modulo m, that means the difference between
a and b, and that between c and d are divisible by m. So a+c-b-d is divisible by m, and hence
a+c is congruent to b+d modulo m. So we can do addition in this notation.
If we have a congruent to b modulo m, then the difference between a and b is divisible
by m, and hence k times (a-b) is also divisible by m. Since ka - kb divisible by m, ka is
congruent to kb modulo m, so we can do multiplication by a constant on this notation.
The original problem has not left us yet. Using this notation, if we write x as the
number of objects, then x is congruent to 2 modulo 3,3 modulo 5 and 2 modulo 7. If we
want to generalize this problem, we have this system of equations. This does look scary,
so we would do what any normal humans would do in this situation: procrastinate. Now we
look at the other side of the story - LaGrange.
One thing that LaGrange is known for is polynomial interpolation. Suppose that you have these
different data points which are absolutely error-free, and you want to figure out the
relationship between the two variables. There are tons of different models like linear,
logarithmic, or exponential, but when there are more than three data points, it is not
guaranteed that those data points would fit any of those models. Polynomial models are
the most versatile, and can fit as many data points as you want.
So let's say p(x) is the required polynomial, which passes through the points (x_1,y_1)
all the way to (x_n,y_n). That means we have a system of equations like so. This monstrosity
is quite familiar, don't you think?
Enough with the procrastination, now we have more problems to deal with. However, we can
tackle these two in similar ways, which is the connection. Let’s tackle the polynomial
problem on the right first because it is actually less complicated.
The general idea is to first tackle a lot of much simpler cases. Instead of this general
case, we solve this case. Let’s say we have solved it, and call the polynomial to be p_1.
Then similarly, we can solve for p_2, all the way to p_n. Now what LaGrange did was
really simple but amazing, so I highly encourage you to pause the video and think about how
we can make use of p_1 all the way to p_n to solve for the general case. Consider this
polynomial. When x equals x_1, this polynomial returns y_1 times 1 + y_2 times 0 all the
way to y_n times 0, so this polynomial returns y_1 when it is fed with x_1 as input. Similarly,
when x equals x_2, this polynomial would return y_2, and so on, and so it satisfies the original
set of equations. So can we pull a similar trick for the ancient Chinese problem?
Again, for this complicated case, we split it into smaller cases, and solve for them
separately, and now similarly consider the number x defined as a_1x_1 adding all the
way to a_nx_n. We need to be careful here, because we are dealing with these congruent
signs not equal signs. Luckily, we have previously demonstrated that you can view them as pretty
much the same thing when it comes to addition and multiplication, so we have the same valid
conclusion that x fulfils the entire system of equations.
Right now, the connection is pretty clear: these two seemingly unrelated problems have
a very similar general problem-solving strategies, and it would be even more amazing if there
is a more subtle similarity between the two problems. There is, and that relation is about
the solution of those simpler cases of the general case.
For both problems, we first solve for all the equations except for the one with one
in it. This is pretty easy for both problems. Then, we adjust this solution by multiplying
by something so that the remaining equation is also satisfied. This adjusting step, however,
is much more difficult for the Chinese problem in general.
For the polynomial problem, we use something called factor theorem, which says that if
f of lambda equals 0, and f is a polynomial with degree higher than 1, then x - lambda
must be a factor of f. That means p has to be composed of factors including x - x_2 all
the way to x - x_n. So if we ignore the first equation for a sec, we have the solution to
be the product of these factors. If we need to consider the first equation, we multiply
by a constant k. To obtain this constant, we just need to substitute x = x_1. Since
p of x_1 is 1, k has to be the reciprocal of the product of these x_1 minus something.
Then this polynomial p_1 fulfils all these equations. By doing this for all the other
simpler cases, we finally have LaGrange polynomial. Usually it is written much more succinctly
like so. If you don’t understand this notation, don’t worry it is just shorthand version
of the entire expression. This looks complicated, but the principle of obtaining such an expression
is pretty easy to understand.
A similar trick can be used for the simpler cases of the ancient Chinese problem. If we
ignore the first equation for a sec, that means x is a multiple of all m's except m_1,
so we call for the lowest common multiple of them. Then we just have to multiply by
some constant so that it also satisfies the first equation. There is a specific algorithm
to do this, but this video is long enough, so I will put the algorithm in the next video.
If you are really interested, visit or revisit my very first two videos because that algorithm
is related to continued fractions, which are mentioned in them.
We are now going to do an actual implementation of this entire solution on the ancient Chinese
problem we started off with.
We need to find solutions to these three sets of equations first. For the first set, x_1
is congruent to 1 modulo 3 and divisible by 5 and 7. 35 is not congruent to 1 modulo 3,
so 35 is not a solution here. What about 70? 70 is definitely congruent to 1 modulo 3,
so we set x_1 to be 70. What about the second set? x_2 has to be congruent to 1 modulo 5,
and a multiple of 3 and 7. 21 fits these criteria, so we set x_2 to be 21. Similarly, for the
third set, we set x_3 to be 15.
So now, since the original system of equations has remainders 2, 3, and 2, so we multiply
x_1 by 2, x_2 by 3, and x_3 by 2, and now we get 233. This isn't quite 23 that we found
by trial and error in the beginning. So what's the problem? There is no flaw in our reasoning
when we try to work this out theoretically, so why would there be such a discrepancy?
23 and 233 are indeed solutions to the system of equations, so that tells us that solutions
are not unique. If there are two roots x and x dash, then the difference between x and
x dash must be divisible by 3, 5, and 7, which means divisible by 105. So since we have worked
out 233, to get 23, we just have to subtract 105 until we get something smaller than 105,
in this case 23, and then now we know that 23 is the smallest positive solution.
This entire process was known since the ancient Chinese. They even had poems about this process.
This poem basically states that multiply the remainder with divisor 3 by 70, that with
divisor 5 by 21, and that with divisor 7 by 15, then subtract 105 until you get the answer.
It is important to note that we would definitely have solutions using this process if all the
m's are mutually relatively prime. But if not, it is not guaranteed that this would
have any solutions at all. Since 3, 5, and 7 are mutually coprime, we definitely have
solutions for the original Chinese problem. This small caveat is known as the Chinese
remainder theorem.
This entire video has been taken from a book written by a late famous Chinese mathematician
Hua Luogeng. He was definitely one of the most influential mathematicians in China,
and had opened up a lot of research areas.
Personally, the reason I found this book inspiring is that prior to reading, I knew LaGrange
polynomial interpolation and the Chinese remainder theorem separately, but had never thought
that these two are correlated. This only means that there are much more in Mathematics to
discover, because even two seemingly unrelated topics can still be intricately related.
If you enjoyed this video, please give it a like, leave a comment and subscribe with
notifications on for more of these Math videos. If you see one of my videos on the suggested,
click on it to help support this channel. Bye!