We made good use of this technique when counting the number of legal Go positions [1].
"Clever use of the Chinese Remainder Theorem allows for splitting the computation into 9 independent parts, each computing L19 modulo 2^64 minus some small number, contributing 64 bits of the 566 bit result."
> the Chinese mathematician Sun Tzu (not to be confused with Sun Tzu who wrote The Art of War almost 1,000 years earlier).
Well, this is the kind of result you get if you insist on referring to people by the combination of a common last name and a standard courtesy title. Imagine if we referred to the author of The Wealth of Nations as "Mr. Smith" instead of "Adam Smith".
Imagine referring to someone by common first name found by flicking through the first pages of the bible, and then a a reference to a vague class of ubiquitous professions.
There's a pretty large difference between referring to someone by a name held by less than 2% of the population vs a title extended to closer to 100% of the relevant population. Identifying people by full name is far, far more informative than identifying them by surname alone.
Writing the tones could help a lot as it basically multiplies the number of possible names by 5 per character, so for 3 character names (which seem common in China) we get 125 fold increase in the possible names.
I never heard of this during my university days. Or maybe I did, and I’ve just forgotten about it. But it’s really nice piece of math, and quiet useful.
Last year’s Advent of Code had a problem that could be solved quickly using this.
CRT is one of the core results of elementary number theory. Elementary number theory is arguably one of the two most axiomatic and most beautiful branches of elementary mathematics, the other being Euclidean geometry. It is, in my opinion, the best pedagogical subject to teach mathematical thinking, and should be taught to more middle schoolers / high schoolers. Unfortunately, I don’t think it will work in places where most middle school / high school teachers themselves have abysmal understanding of mathematics and can only teach you to recite shit or plug numbers into formulae.
One problem with elementary number theory in middle school might be picking how to approach it.
Consider divisibility, GCD, LCM, and related theorems which are usually covered early in elementary number theory books. I've seen a few different styles for dealing with these things.
1. One style involves introducing a ton of variables. If you've got A divides B somewhere, introduce C=B/A. If you've got an A that does not divide B, introduce q = floor(B/A), r = B%A. You start with some theorem you want to prove about A and B, and soon you've got a dozen or two variables floating around and end with something like "we see that z = t and thus the theorem is proved" and the poor student has no idea what the heck just happened.
It's like A and B got smashed together in a Large Integer Collider and you are supposed to figure out things from the shower of divisors.
2. Another style is to do unique factorization as soon as possible. GCD and LCM can then be dealt with in terms of factorizations.
3. I believe I've even seen a textbook that took what in the other approaches is a theorem that the GCD of A and B is the minimum positive linear combination of A and B and defined that as the GCD.
I think that for a given student there is a good chance that one of these approaches (or others that I'm sure I've forgotten about) will work a lot better than the others and one will work a lot worse than the others. Finding an approach that works for everyone in a class could be difficult.
It focuses on factoring and primality testing, but it also covers a lot of introductory number theory. IIRC it also covers continued fractions as used for factoring and the quadratic sieve and MPQS. The pseudo-code given in the book is very easy to translate into python, which supports large integers and efficient exponentiation mod P.
I've read about it many years ago, possibly in some book about cryptography, maybe. AFAIR it's used in some algos in this field.
But its application to counting troops... well, this sounds like a really overdone method of doing this. Maybe it has been tried once or twice, but I guess it's probably more of an urban legend, than something that could be pragmatically used on a daily basis.
The legend could reasonably be true if you assume the generals just used the process for communication: "my troop strength is (3, 7, 2)." Actually lining up the troops seems unnecessary: it takes far less mathematical sophistication to calculate the moduli than to reverse engineer the total number.
The Chinese Remainder Theorem does come up in a very real Chinese context, the cycle of sixty, in which e.g. 甲寅 identifies 51 as the number which is simultaneously 1 (mod 10) and 3 (mod 12).
Assume there is a solution to the equation. Then if you take the mod n of both sides the new equality will also hold, for any n. Therefore, if you can prove there are no solution for the mod n equation, then the original equation is also not solvable. This of course also hold when n is prime.
This quote is specifically about Diophantine equations.
You can find a similar statement as "Proposition 3.2.2" in Chapter 3 "Modular Arithmetic" [1] of this introductory course [2] to Number Theory. Here is a picture of the statement [3].
Basically, if there exists a number n such that there is no solution modulo n, then you know there are no solutions. Here is a simple application [4] of the proposition with n = 2 and 3.
"Clever use of the Chinese Remainder Theorem allows for splitting the computation into 9 independent parts, each computing L19 modulo 2^64 minus some small number, contributing 64 bits of the 566 bit result."
[1] https://tromp.github.io/go/legal.html
Well, this is the kind of result you get if you insist on referring to people by the combination of a common last name and a standard courtesy title. Imagine if we referred to the author of The Wealth of Nations as "Mr. Smith" instead of "Adam Smith".
https://en.m.wikipedia.org/wiki/Adam_Smith_(disambiguation)
They should all use use a unique hanzi name or an ORCID or a UUID or something.
> the economist Adam Smith (not to be confused with Adam Smith who wrote the book Wealth of Nations almost 200 years earlier).
It's not going to help much in general, because Chinese family names just aren't that diverse.
Consider divisibility, GCD, LCM, and related theorems which are usually covered early in elementary number theory books. I've seen a few different styles for dealing with these things.
1. One style involves introducing a ton of variables. If you've got A divides B somewhere, introduce C=B/A. If you've got an A that does not divide B, introduce q = floor(B/A), r = B%A. You start with some theorem you want to prove about A and B, and soon you've got a dozen or two variables floating around and end with something like "we see that z = t and thus the theorem is proved" and the poor student has no idea what the heck just happened.
It's like A and B got smashed together in a Large Integer Collider and you are supposed to figure out things from the shower of divisors.
2. Another style is to do unique factorization as soon as possible. GCD and LCM can then be dealt with in terms of factorizations.
3. I believe I've even seen a textbook that took what in the other approaches is a theorem that the GCD of A and B is the minimum positive linear combination of A and B and defined that as the GCD.
I think that for a given student there is a good chance that one of these approaches (or others that I'm sure I've forgotten about) will work a lot better than the others and one will work a lot worse than the others. Finding an approach that works for everyone in a class could be difficult.
It focuses on factoring and primality testing, but it also covers a lot of introductory number theory. IIRC it also covers continued fractions as used for factoring and the quadratic sieve and MPQS. The pseudo-code given in the book is very easy to translate into python, which supports large integers and efficient exponentiation mod P.
But its application to counting troops... well, this sounds like a really overdone method of doing this. Maybe it has been tried once or twice, but I guess it's probably more of an urban legend, than something that could be pragmatically used on a daily basis.
Can anyone point me towards a proof of this?
You can find a similar statement as "Proposition 3.2.2" in Chapter 3 "Modular Arithmetic" [1] of this introductory course [2] to Number Theory. Here is a picture of the statement [3].
Basically, if there exists a number n such that there is no solution modulo n, then you know there are no solutions. Here is a simple application [4] of the proposition with n = 2 and 3.
[1] <http://www2.math.ou.edu/~kmartin/intro-nt/ch3.pdf> [2] <http://www2.math.ou.edu/~kmartin/intro-nt/>
[3] <https://i.ibb.co/8mNHW0Q/2021-09-20-10-34-25.png> [4] <https://i.ibb.co/Qffr9k2/2021-09-20-10-56-29.png>
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
It also covers the straightforward generalization of the theorem to principal ideal domains (e.g. polynomials over a field)