Number Theory and Calculus/Analysis

Background required: modular arithmetic, calculus.

Once in a while, I’ll post something which offers a glimpse into more advanced mathematics. Here’s one.

Example 1

For starters, we know from basic algebra that $(1-r)^{-1} = 1 + r + r^2 + \dots$ . Let’s see if there’s a corresponding result for modular arithmetic: letting r = 14 and taking modulo 7⁴, we get:

$-\frac 1 {13} = (1-14)^{-1} = 1 + 14 + 14^2 + 14^3 + ...$

where the remaining terms are chopped off since they’re divisible by 7⁴. Now, the right-hand-side simplifies to 2955 mod 2401 = 554, and indeed we have $-\frac 1 {13} \equiv 554 \pmod {7^4}$ since $13\times 554 \equiv -1 \pmod {7^4}$ . Hence, we have simplified the computation of inverse modulo a prime power by converting it to multiplication. Purists would no doubt complain that we shouldn’t substitute r = 14 since the infinite geometric series only holds for |r| < 1, but as you can see we still got the right answer. 🙂

Example 2

Next, we know from calculus that binomial expansion gives:

$(1 + x)^r = 1 + r x + \frac {r(r-1)} {2!} x^2 + \frac {r(r-1)(r-2)} {3!} x^3 + \dots$

which converges when |x| < 1 and r is any number (even irrational). Let’s see if we can’t apply this to modular arithmetic. Say, for example, we wish to find an x such that $x^2 \equiv 2 \pmod {7^4}$ , i.e. x is the square root of 2 modulo 2401 = 7⁴. Then the above binomial expansion gives us:

$2\sqrt 2 = \sqrt 8 = (1 + 7)^{\frac 1 2} = 1 + \frac 1 2 \cdot 7 + \frac {\frac 1 2 \cdot \left(-\frac 1 2\right)} 2 \cdot 7^2 + \frac {\frac 1 2 \cdot \left(-\frac 1 2\right) \cdot \left(-\frac 3 2\right)} 6 \cdot 7^3 + \dots$

Again, the remaining terms may be ignored since they’re all divisible by 7⁴. Since $2 \times 1201 \equiv 1 \pmod {7^4}$ , we write $\frac 1 2 \equiv 1201 \pmod {7^4}$ , we then obtain the following:

$\sqrt 8 \equiv 470 \pmod {7^4}.$

Dividing by 2, we thus get $\sqrt 2 \equiv 235 \pmod {7^4}$ . You can easily check that 235² is indeed congruent to 2 modulo 7⁴.

Example 3

Or another example would be the Newton-Raphson method: to find a zero of the function f(x), start with a point x₀, and iterate:

$x_{n+1} = x_n - \frac {f(x_n)} {f'(x_n)},$

where f’ is the derivative of x. Let’s see if we can apply this method to find the solution to, say:

$x^3 - x + 1 \equiv 0\pmod {7^4}.$

So f(x) = x³ – x + 1 and the recurrence is given by $x_{n+1} = x_n - \frac {x_n^3 - x_n + 1} {3x_n^2 - 1} = \frac {2x_n^3 -1}{3x_n^2 - 1}$ . Since we have to perform division modulo 7⁴, the answer is not so easily computable. Instead, we shall leave our answer as a rational fraction a/b, where a and b are integers.

First, note that x₀ = 2 satisfies $f(x) \equiv 0 \pmod 7$ so let’s start from there:

$x_0 = 2, \quad x_1 = \frac {15} {11}, \quad x_2 = \frac {5419} {6094}.$

This turns out to be the right answer! Indeed, $\frac 1 {6094} \equiv 1745 \pmod {7^4}$ , so $x_2 \equiv 1745 \times 5419 \equiv 1017 \pmod {7^4}$ and one easily checks that this is a valid solution to $x^3 - x + 1 \equiv 0 \pmod {7^4}$ .

Explanation

What’s going on here? We carried out a bunch of computations which seemed utterly nonsensical but which yielded the right answer. For a proper understanding of the underlying theory, one needs to study p-adic analysis (where the p here refers to a prime). Indeed, one can go on to define logarithm and exponentiation and most of the usual relations among them still hold. On the one hand, it is possible to be led astray by one’s intuition from the real case; on the other hand, convergence in the p-adic case is extremely fast! For instance, the Newton-Raphson process gave us the correct answer by the 2nd iteration.

The gist of the theory is as follows. Let p be a prime.

We define a new “absolute value” on the set Q of rational numbers. If r is a non-zero rational, then |r|_p is defined to be the unique p^m (m integer) such that p^mr is of the form a/b where a and b are both not divisible by p. E.g. if p = 5, then |250|₅ = 1/125, |17/198|₅ = 1 and |12/25|₅ = 25.
Recall that our good-old |x–y| determines how close x and y are on the number line. For |r–s|_p, closeness means r and s are congruent to each other modulo a huge power of p.
We have the triangular inequality $|r+s|_p \le |r|_p + |s|_p$ . In fact, we have the strong triangular inequality $|r+s|_p \le \max(|r|_p, |s|_p)$ . If you unwind the definition, it just means that if r and s are divisible by p^r, then so is r+s. The triangular inequality ensures that we can define a theory of analysis (or even calculus) on it.
One consequence of the strong triangular inequality is that convergence occurs very quickly, as we have already seen from the above examples. Compare this to the case of real numbers, where convergence can be slow, e. g. in $\frac 1 {1-x} = \sum_n x^n$ when x = 0.99.
E.g. in example 1, we get $|14|_7 = \frac 1 7 < 1$ which ensures convergence.

Feel free to try out more computations of the above type. To carry out multi-precision integer computation (> 12 digits), download Python.

2 Responses to Number Theory and Calculus/Analysis

Kishore says:

December 29, 2019 at 4:27 pm

Could you please expand this post to include the construction of the p-adic integers and their construction is related to solving an infinite system of congruences?

- limsup says:
  
  December 31, 2019 at 9:50 am
  
  Hopefully in the near future. I’ve been planning a series on commutative algebra which includes completion (with p-adic numbers as a special case).