Background required: modular arithmetic, calculus.
Once in a while, I’ll post something which offers a glimpse into more advanced mathematics. Here’s one.
For starters, we know from basic algebra that . Let’s see if there’s a corresponding result for modular arithmetic: letting r = 14 and taking modulo 74, we get:
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 since . 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. 🙂
Next, we know from calculus that binomial expansion gives:
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 , i.e. x is the square root of 2 modulo 2401 = 74. Then the above binomial expansion gives us:
Again, the remaining terms may be ignored since they’re all divisible by 74. Since , we write , we then obtain the following:
Dividing by 2, we thus get . You can easily check that 2352 is indeed congruent to 2 modulo 74.
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:
where f’ is the derivative of x. Let’s see if we can apply this method to find the solution to, say:
So f(x) = x3 – x + 1 and the recurrence is given by . 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 so let’s start from there:
This turns out to be the right answer! Indeed, , so and one easily checks that this is a valid solution to .
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 |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 . In fact, we have the strong triangular inequality . 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 when x = 0.99.
- E.g. in example 1, we get 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.