Ancient war trickery is alive in math today
quantamagazine.org
quantamagazine.org
"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."
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.
It's not going to help much in general, because Chinese family names just aren't that diverse.
> the economist Adam Smith (not to be confused with Adam Smith who wrote the book Wealth of Nations almost 200 years earlier).
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?
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)
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>