5 ms·

Ancient war trickery is alive in math today

130 points by nsoonhui 5y ago

surfsvammel 5y ago
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.
- pishpash 5y ago
  Most courses in abstract algebra would cover this.
- justToAddLink 5y ago
  in Tunisia, this is covered by highschool seniors in the math section.
- oefrha 5y ago
  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.
  - tzs 5y ago
    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.
  - phkahler 5y ago
    I found the following book to be great introduction: https://www.amazon.com/Factorization-Primality-Testing-Undergraduate-Mathematics/dp/0387970401 https://www.amazon.com/Factorization-Primality-Testing-Under... 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.
hoten 5y ago
> “If there are no solutions modulo a prime, then you know there are no solutions,” Can anyone point me towards a proof of this?
- mkbosmans 5y ago
  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.
  - deleted 5y ago
    [deleted]
- SamReidHughes 5y ago
  If there are solutions, they work modulo any prime.
- deleted 5y ago
  [deleted]
- qsort 5y ago
  The wikipedia page is rather comprehensive: https://en.wikipedia.org/wiki/Chinese_remainder_theorem 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)
- woko 5y ago
  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. [1] <http://www2.math.ou.edu/~kmartin/intro-nt/ch3.pdf http://www2.math.ou.edu/~kmartin/intro-nt/ch3.pdf> [2] <http://www2.math.ou.edu/~kmartin/intro-nt/ http://www2.math.ou.edu/~kmartin/intro-nt/> [3] <https://i.ibb.co/8mNHW0Q/2021-09-20-10-34-25.png 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://i.ibb.co/Qffr9k2/2021-09-20-10-56-29.png>
jagrsw 5y ago
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.
- dmurray 5y ago
  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.
- thaumasiotes 5y ago
  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).
thaumasiotes 5y ago
> 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".
- Y_Y 5y ago
  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. https://en.m.wikipedia.org/wiki/Adam_Smith_(disambiguation) 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.
  - thaumasiotes 5y ago
    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.
- gjvnq 5y ago
  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.
  - thaumasiotes 5y ago
    It doesn't help here, the characters are 孫子 in both cases. Their names are just as identical as George Washington and Denzel Washington. It's not going to help much in general, because Chinese family names just aren't that diverse.
- Aditya_Garg 5y ago
nvmletsdoit 5y ago
And nowadays we use it just for make sure that buffer won't overflow xD
tromp 5y ago
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." [1] https://tromp.github.io/go/legal.html https://tromp.github.io/go/legal.html
partizanos 5y ago
Very nice relevant problem solved using congruent numbers which digit is not included in 2^29 calculation: https://youtu.be/MW3Hy9r6x-k https://youtu.be/MW3Hy9r6x-k

130 points by nsoonhui 5y ago

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.

pishpash 5y ago
Most courses in abstract algebra would cover this.
justToAddLink 5y ago
in Tunisia, this is covered by highschool seniors in the math section.
oefrha 5y ago
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.
- tzs 5y ago
  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.
- phkahler 5y ago
  I found the following book to be great introduction: https://www.amazon.com/Factorization-Primality-Testing-Undergraduate-Mathematics/dp/0387970401 https://www.amazon.com/Factorization-Primality-Testing-Under... 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.

hoten 5y ago

> “If there are no solutions modulo a prime, then you know there are no solutions,” Can anyone point me towards a proof of this?

mkbosmans 5y ago
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.
- deleted 5y ago
  [deleted]
SamReidHughes 5y ago
If there are solutions, they work modulo any prime.
deleted 5y ago
[deleted]
qsort 5y ago
The wikipedia page is rather comprehensive: https://en.wikipedia.org/wiki/Chinese_remainder_theorem 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)
woko 5y ago
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. [1] <http://www2.math.ou.edu/~kmartin/intro-nt/ch3.pdf http://www2.math.ou.edu/~kmartin/intro-nt/ch3.pdf> [2] <http://www2.math.ou.edu/~kmartin/intro-nt/ http://www2.math.ou.edu/~kmartin/intro-nt/> [3] <https://i.ibb.co/8mNHW0Q/2021-09-20-10-34-25.png 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://i.ibb.co/Qffr9k2/2021-09-20-10-56-29.png>

jagrsw 5y ago

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.

dmurray 5y ago
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.
thaumasiotes 5y ago
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).

thaumasiotes 5y ago

> 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".

Y_Y 5y ago
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. https://en.m.wikipedia.org/wiki/Adam_Smith_(disambiguation) 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.
- thaumasiotes 5y ago
  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.
gjvnq 5y ago
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.
- thaumasiotes 5y ago
  It doesn't help here, the characters are 孫子 in both cases. Their names are just as identical as George Washington and Denzel Washington. It's not going to help much in general, because Chinese family names just aren't that diverse.
Aditya_Garg 5y ago

nvmletsdoit 5y ago

And nowadays we use it just for make sure that buffer won't overflow xD

tromp 5y ago

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." [1] https://tromp.github.io/go/legal.html https://tromp.github.io/go/legal.html

partizanos 5y ago

Very nice relevant problem solved using congruent numbers which digit is not included in 2^29 calculation: https://youtu.be/MW3Hy9r6x-k https://youtu.be/MW3Hy9r6x-k