I love complex analysis, and that's the branch of calculus that is most associated with number theory. For example, it was critical in the original proof of the prime number theorem and Dirichlet's theorem on primes in arithmetic progressions. Today, all kinds of number theoretic functions are studied using complex analysis, like the famous Riemann zeta function, Dirichlet L-functions, theta functions, and so on.
So that's what I expected this to be about. And it was super fun to see that it was actually not! Definitely learned something today.
I had to think about the following sentence for a bit:
"We know that any integer x obeying f(x)≡0 (mod 125) must obey x≡2(mod 5)."
My explanation (it's basically all in the article, but here I spell it out):
If f(x) = 0 (mod 125), then 125 divides f(x). Since 125 = 5^3, it must be that 5 also divides f(x). The only way for 5 to divide f(x) is for x = 2 (mod 5), by brute-forcing all solutions to f(x) = 0 (mod 5). Therefore for f(x) = 0 (mod 125), x = 2 (mod 5).
It's also worth saying why we only need to check all integers between 0 and n-1 when solving an equation mod n:
Suppose that for some integer y, f(y) = 0 (mod n) but y >= n or y < 0. Then for some x between 0 and n-1 (inclusive),
x = y (mod n).
Since the function f is a polynomial with integer coefficients, evaluating f on an integer involves only multiplication and addition by integers. Some crucial facts about congruences:
If x = y (mod n) then a + x = a + y (mod n) for any integer a.
If x = y (mod n) then ax = ay (mod n) for any integer a.
If x = y (mod n) then x^2 = y^2 (mod n), and similarly other integer powers.
From these we conclude that if x = y (mod n), then f(x) = f(y) (mod n) for any polynomial f.
So, for any y >= n with f(y) = 0 (mod n), there's some x between 0 and n-1 (inclusive) that also satisfies f(x) = 0 (mod n); in fact it's whatever integer in that range that y is congruent to. So we need only check integers in that range to find all possible solutions to f(x) = 0 (mod n).
Forgive me for the long explanation for what are of course elementary facts in number theory! I'm rusty on number theory so I had to explicitly work them out, so I figured maybe someone else might also benefit.
In some sense the title is a bit misleading (one is led to think of Analytic Number Theory). I'd rather use the title "Using differentials to...", which is more precise, as there is not exactly any "calculus" going on but there is indeed differential algebra and differential "number theory", so to speak.
Analytic number theory exists and involves calculus, but it's not what the linked post is about. The article talks about Hensel's lemma, which is a purely algebraic statement with a purely algebraic proof, which, however, is inspired by techniques from calculus. This is typically still categorized as algebraic number theory.
author was so excited to point at calculus, that he forgot to derive actual mod3000 answer from chinese remainders...
and it seems much more intuitive for me to see this technique as "find x mod p^n, then apply x->ans+p*x transformation and do everything at mod p^n+1" - and to derive that it results in derivatives from that
I love complex analysis, and that's the branch of calculus that is most associated with number theory. For example, it was critical in the original proof of the prime number theorem and Dirichlet's theorem on primes in arithmetic progressions. Today, all kinds of number theoretic functions are studied using complex analysis, like the famous Riemann zeta function, Dirichlet L-functions, theta functions, and so on.
So that's what I expected this to be about. And it was super fun to see that it was actually not! Definitely learned something today.
I had to think about the following sentence for a bit: "We know that any integer x obeying f(x)≡0 (mod 125) must obey x≡2(mod 5)."
My explanation (it's basically all in the article, but here I spell it out): If f(x) = 0 (mod 125), then 125 divides f(x). Since 125 = 5^3, it must be that 5 also divides f(x). The only way for 5 to divide f(x) is for x = 2 (mod 5), by brute-forcing all solutions to f(x) = 0 (mod 5). Therefore for f(x) = 0 (mod 125), x = 2 (mod 5).
It's also worth saying why we only need to check all integers between 0 and n-1 when solving an equation mod n:
Suppose that for some integer y, f(y) = 0 (mod n) but y >= n or y < 0. Then for some x between 0 and n-1 (inclusive),
x = y (mod n).
Since the function f is a polynomial with integer coefficients, evaluating f on an integer involves only multiplication and addition by integers. Some crucial facts about congruences:
If x = y (mod n) then a + x = a + y (mod n) for any integer a. If x = y (mod n) then ax = ay (mod n) for any integer a. If x = y (mod n) then x^2 = y^2 (mod n), and similarly other integer powers.
From these we conclude that if x = y (mod n), then f(x) = f(y) (mod n) for any polynomial f.
So, for any y >= n with f(y) = 0 (mod n), there's some x between 0 and n-1 (inclusive) that also satisfies f(x) = 0 (mod n); in fact it's whatever integer in that range that y is congruent to. So we need only check integers in that range to find all possible solutions to f(x) = 0 (mod n).
Forgive me for the long explanation for what are of course elementary facts in number theory! I'm rusty on number theory so I had to explicitly work them out, so I figured maybe someone else might also benefit.
In some sense the title is a bit misleading (one is led to think of Analytic Number Theory). I'd rather use the title "Using differentials to...", which is more precise, as there is not exactly any "calculus" going on but there is indeed differential algebra and differential "number theory", so to speak.
But great and elegant article. Thanks.
The mathematical field of tackling number theory problems in this way is called analytic number theory.
https://en.wikipedia.org/wiki/Analytic_number_theory
The prime number theorem, on how prime numbers are distributed amongst the integers, was first proved using analytic techniques.
Analytic number theory exists and involves calculus, but it's not what the linked post is about. The article talks about Hensel's lemma, which is a purely algebraic statement with a purely algebraic proof, which, however, is inspired by techniques from calculus. This is typically still categorized as algebraic number theory.
Get a load of number theorists in a room and there will always be a fight between the analytic and algebraic.
author was so excited to point at calculus, that he forgot to derive actual mod3000 answer from chinese remainders...
and it seems much more intuitive for me to see this technique as "find x mod p^n, then apply x->ans+p*x transformation and do everything at mod p^n+1" - and to derive that it results in derivatives from that
If author is following this: minor typo in "we use the seem approximation trick again": seem -> same
"Appendix: The Langlands program"
no offense but this doesn't even come close to describing it at all
It's delightful (and unsurprising) that Newton's method shows up as the main bridge.