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 74, 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 74. 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 = 74. 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 74. 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 2352 is indeed congruent to 2 modulo 74.

Example 3

Or another example would be the Newton-Raphson method: to find a zero of the function f(x), start with a point x0, 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) = x3x + 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 74, 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 x0 = 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 pm (m integer) such that pmr is of the form a/b where a and b are both not divisible by p. E.g. if p = 5, then |250|5 = 1/125, |17/198|5 = 1 and |12/25|5 = 25.
  • Recall that our good-old |xy| determines how close x and y are on the number line. For |rs|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 pr, 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.

This entry was posted in Extra and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s