3 ms·

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 ye

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.

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.