Recently, I borrowed a copy of Frank J. Swetz’s book, Capitalism & Arithmetic: The New Math of the 15th Century (sadly, there is no PDF on the Internet, to the best of my knowledge). It was really interesting! The book is a translation with commentary of the Treviso Arithmetic, published in 1478 in Treviso, Italy, by an unknown author. The title of Swetz’s book alludes to the historical context in which the book was published: it was one of the first mathematics texts in Europe published in a vernacular language, and aims at teaching applied arithmetic for the purposes of commerce.
Treviso is just 26 kilometers from Venice, which was at the time the commercial hub of the Mediterranean, and the development of mathematics in medieval Europe is linked to the influences and demands of early capitalism. Trade in the Mediterranean brought new ideas from the Middle East, as well as old ideas which by that time Europe had long forgotten. It also demanded more complex and more frequent calculations, requiring more efficient mathematical tools, such as Arabic numerals.
Indeed, the replacement of Roman numerals, favoured by the “abacists”, by Arabic numerals, favored by the “algorists” (whose name was derived from successive mis-transliterations of al-Khwārizmī), was a matter of some controversy, as featured in this 1508 woodcut, depicting an arithmetic contest.
There’s a lot of interesting material in the Treviso, including some quite intricate divisions done in triple-radix arithmetic, but something which is interesting for the purposes of this post is the method of “casting out nines”, a method for quickly checking errors in addition and multiplication, which I’d never learned about before.
In the Treviso, casting out nines to check correctness of an addition is described as follows:
Besides this proof [performing subtraction] there is another. If you wish to check the sum by casting out nines, add the units, paying no attention to 9 or 0, but always considering each as nothing. And whenever the sum exceeds 9, subtract 9, and consider the remainder as the sum. Then the number arising from the sum will equal the sum of the numbers arising from the addends.
In more modern language, one might say: add the digits of the summands, reducing \(\mod\; 9\) along the way, then redo the computation (either multiplication or addition) with the new numbers.
For example, if we computed \(21432 + 5836 = 27268\), we can check the answer as follows: on the left-hand side, cast nines out of \(21432\) and \(5836\), and add the results, and on the right-hand side, cast nines out of \(27268\).
On the left-hand side, start with \(21432\), and add the digits \(\mod\;9\): we can cast out \(4,3,2\) since \(4+3+2 = 9\), so \[2+1+4+3+2 \equiv 2+1 \equiv 3 \;\;(\mod\;9).\] For \(5836\), we cast out \(3,6\) since they sum to nine, so \[5+8+3+6 \equiv 5+8 \equiv 4 \;\;(\mod\;9).\] Adding the results gives \(7 = 3+4\).
On the right-hand side, cast nines out of \(27268\) as follows: cast out \(2,7\) since \(2+7=9\), and add the remaining digits, \(2+6+8 = 16\), which is \(7\;\;(\mod\;9)\). So, both sides agree. If, however, we had made a mistake and computed \(27265\) instead of \(27268\), casting out nines would give \(5\), which is not \(7\). However, if we had found \(27259\) instead of \(27268\) by mistake, casting out nines would give \(7\), so casting out nines does not guarantee detection of an error.
Why does this work? First, think about what it means to write a number in base \(10\): let \(n\) be a number and \(c_k,\ldots,c_0\) be its digits. Then \[ n = c_0 + c_1 10 + c_2 100 + \cdots + c_k 10^k. \] Now, consider the equation \[ 9 = 10 - 1. \] This tells us that \(10 \equiv 1 \;\;(\mod\; 9)\). Reducing the previous equation \(\mod\; 9\), we get \[ \begin{array}{rcl} n &=& c_0 + c_1 10 + c_2 100 + \cdots + c_k 10^k \\ &\equiv& c_0 + c_1 1 + c_2 1^2 + \cdots + c_k 1^k \;\;(\mod\;9)\\ &\equiv& c_0 + c_1 + c_2 + \cdots + c_k \;\;(\mod\;9). \\ \end{array} \] So, to reduce a number \(\mod\; 9\), we can just compute the digit sum \((\mod\; 9\). This makes computing the reduction of a base-\(10\) number \(\mod\; 9\) ludicrously efficient to do by hand. (As an aside, a more elegant proof of this statement can be found on page 68 of Carl E. Linderholm’s 1972 classic, Mathematics Made Difficult).
Casting out nines, therefore, amounts to reduction \(\mod\; 9\), and redoing the computation in \(\mathbb{Z}/9\mathbb{Z}\). Since the reduction is a ring homomorphism, it preserves addition and multiplication, so if we got a different answer after casting out nines, there must have been a mistake. However, if we compute a wrong answer that differs from the correct one by a multiple of \(9\), then the error will not be detected: in the example above, we have \[ 27259 = 21432 + 5836 - 9 \equiv 21432 + 5836 \;\;(\mod\; 9), \] and assuming that all errors are equally likely, this happens with probability \(1/9\), so we detect an error with probability \(8/9\), or \(88\%\).
To increase the error-detection probability, we can generalize the method, by reducing \(\mod\; 99\), \(\mod\; 999\), etc. For instance, to check \[ 197702369162 = 842987 \times 234526 \] by casting out 99, we group digits into pairs and take sums: \[ \begin{array}{rcl} (19+77)+(2+36)+(91+62) &=& 96 + 38 + (100 + 53) \\ &\equiv& (96 + 38) + 1 + 53 \;\;(\mod\; 99) \\ &\equiv& (1 + 34) + 1 + 53 \;\;(\mod\; 99) \\ &\equiv& 89 \;\;(\mod\; 99); \end{array} \] we have \(84+29+87=200 \equiv 2 \;\;(\mod\; 99)\), and \(23+45+26 = 94\), so the product is \(2\times 94 = 188 \equiv 89\), and the multiplication is correct with probability just under \(99\%\).
The point here is that, given a number in base \(10\), it’s easy to convert to a number in base \(10^k\) by grouping digits, and given a number in base \(10^k\), it’s easy to reduce \(\mod\; m = 10^k -1\), since \[ 10^k \equiv 1 \;\;(\mod\; m). \] And, in fact, although the \(1\) on the right-hand side is a particularly easy number to deal with, things are still easy if we pick \(m\) to be close to \(10^k\), so that the right-hand side becomes a small number. In this case we don’t quite get to take a digit sum, but it’s still fairly simple. For example, setting \(p = 997 = 10^3 - 3\), we have \(1000 \equiv 3 \mod\; p\), so to reduce \(987459324 \mod\; p\), we take \[ \begin{array}{rcl} 987(1000^2) + 459(1000) + 324 &\equiv& 987(9) + 459(3) + 324 \;\;(\mod\; p) \\ &\equiv& 8883 + 1377 + 324 \;\;(\mod\; p) \\ &\equiv& 8(3) + 883 + 1(3) + 377 + 324 \;\;(\mod\; p) \\ &\equiv& 1611 \equiv 614 \;\;(\mod\; p). \end{array} \]
Putting all this together, we see that it’s easy to reduce a number written in base \(10\) by any number which is close to a power of \(10\). But there’s nothing really special about base \(10\) – for exactly the same reasons, it’s easy to reduce a number written in base \(b\) modulo a number close to a power of \(b\).
For computers, which use binary, this means that reduction modulo numbers close to powers of \(2\) is very fast. In particular, if one seeks to do arithmetic \(\mod\; p\) on a computer, it’s good to choose a prime \(p\) which is close to a power of \(2\).
This (partially) explains the “25519” in “Curve25519”, one of the best choices of curve for elliptic-curve cryptography: the curve is defined modulo \(p =2^{255} - 19\), and, as discussed on page 13 of the paper, the prime \(p\) was chosen among primes near \(256\) bits as the one closest to a power of \(2\) (beating out \(2^{255} +95\), \(2^{255} - 31\), \(2^{254} + 79\), \(2^{253} + 51\), and \(2^{253} + 39\)).
Thanks to Peter Schwabe for lending me his copy of Capitalism & Arithmetic.
