FRESH

Hacker News

Home

Using calculus to do number theory

132 points by cpp_frog

by pfortuny

2 subcomments

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.

by joshuaissac

1 subcomments

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.

by articulatepang

1 subcomments

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.

by NooneAtAll3

0 subcomment

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

by obastani

0 subcomment

This idea leads to the p-adic numbers:
https://en.wikipedia.org/wiki/P-adic_number

by jjgreen

0 subcomment

If author is following this: minor typo in "we use the seem approximation trick again": seem -> same

by nomemory

0 subcomment

Blog looks promising. Is there a RSS feed associated with it?

by scrubs

0 subcomment

Loved this. Thanks.

by adampunk

0 subcomment

It's delightful (and unsurprising) that Newton's method shows up as the main bridge.

by paulpauper

0 subcomment

"Appendix: The Langlands program"
no offense but this doesn't even come close to describing it at all

by Heer_J

0 subcomment

[dead]