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.