Talk:Casting out nines

From Wikipedia, the free encyclopedia

"which is necessarily equal to the original number" doesn't this mean if x is the original number and r the last number (or the remainder) then: x \equiv r \pmod 9. If so it shoud be rewritten to reflect that because \equiv is different form = .

[edit] More formal proof that method works?

The article's section on how it works very loosely brushes over why this method works. A more formal mathematical proof of why this works would be helpful, if one can be found in published material somewhere. (The proof would need to be something in an external source that the article can cite.)

In particular, the article glosses over proving that the sum of the digits of a given integer mod 9 is equal to that integer mod 9. In mathematical notation, this would be:

Given an n-digit integer x = anan − 1...a2a1, it follows that xmod9 = (an + an − 1 + ... + a2 + a1)mod9. An example would be that we're proving 507 mod 9 = (5+0+7) mod 9. The proof doesn't appear to be difficult, but neither is it a trivial off-hand observation. Dugwiki 18:54, 5 January 2007 (UTC)

I don't feel like working this out into clear prose that can be inserted in the article, but the proof is easy enough. Instead of using the equivalence relation of having the same remainder modulo 9, I use the equivalent property of having a difference that is an integral multiple of 9. I further use induction on the length of the number's decimal representation. Here is the proof:
Let n be the number, and s(n) the sum of the digits of n. We need to prove that there exists some number k such that n − s(n) = 9k.
Base case: n has 1 digit. Then s(n) = n, so n − s(n) = 0, which equals 9 times 0.
Step. Assume n has 2 or more digits. Let d be the last digit of the decimal representation of n. Then n can be written in the form 10m + d, where m is the number obtained by deleting the last digit. For example, 237 = 10×23 + 7. Then s(n) = s(m) + d. By the induction hypothesis, m − s(m) = 9j for some integer j. Then n − s(n) = 10m + d − (s(m) + d) = 10m - s(m) = 9m + m − s(m) = 9m + 9j = 9(m+j).
 --LambiamTalk 21:19, 5 January 2007 (UTC)
It may take some digging to find this mentioned in a peer-reviewed source, since this is so old and so trivial a result. A web search finds some mentions in "Earliest Known Uses of Some of the Words of Mathematics (C)".
CASTING OUT NINES.
  • Fibonacci called the excess of nines the pensa or portio of the number (Smith vol. 1, page 153).
  • Liber Abaci (1202, revised 1228) has:
    Uerum si prescriptam diuisionem per pensam nouenarii probare uoluerit accipiat pensam de 13976 que sunt 8 et seruet eam ex parte. Et iterum accipiat pensam exeuntis numeri, scilicet de 607, que sunt 4 et multiplicet eam per pensam de 23, que sunt 5, erunt 20; de quibus accipiat pensam, que sunt 2 et addat eam cum 15 que sunt super uirgulam de 23, erunt 17, quorum pensa sunt 8, sicuti superius ex parte seruauimus.
    —This quotation was provided by Michel Ballieu in an Internet posting. He provides the translation: "In fact if you want to verify the preceding division by casting out nines take pensa(m) of 13976 which are 8 and keep them aside. And again take pensa(m) of the outgoing number, i.e. of 607, which are 4 and multiply them by pensa(m) of 23, which are 5, they will be 20; take pensa(m) of these 20 which are 2 and add to them 15 which are upon the bar of 23, they will be 17, whose pensa are 8, as higher in what we kept aside."
  • A phrase from the Treviso Arithmetic (1478) is translated "If you wish to check the sum by casting out nines...."
  • Pacioli (1494) spoke of it as "corrente mercatoria e presta" (Smith vol. 1, page 153).
  • Christopher Clavius used the term "Probatio additiones per 9" in Epitome Arithmeticae Practicae (1607, Köln, p. 16–17), according to Albrecht Heeffer.
  • "Casting out the nines" is found in the first edition of the Encyclopaedia Britannica (1768–1771) in the article, "Arithmetick."
Also, David Singmaster's Queries on Sources in Recreational Mathematics apparently said
  • Casting Out Nines. This is mentioned by St. Hippolytus, Philosphumena, c200, NYS. A special case is in Iamblichus. Al-Khowarizmi, c820, describes it. A fairly general use of 9s is in Aryabhata II's Mahasiddhanta, c950, and Narayana's Ganita-kaumudi, c1356, allows any modulus. Have either of these ever been translated into a western language?? There are also Arabic references from 952/953, c1000 and c1020 (Avicenna, who attributes it to the Hindus).
Knuth (TAOCP, Vol.2) mentions that casting out nines is only about 89% reliable since the probability that two random integers will differ by a multiple of nine is 1:9.
As I recall Jakow Trachtenberg's ideas, found in Cutler and McShane, The Trachtenberg Speed System of Basic Mathematics (ISBN 978-0-313-23200-8), include casting out nines (and elevens) as a recommended check on large computations, and the book includes a proof of its correctness.
The relevant page at MathWorld cites more recent sources.
With Carl Friedrich Gauss' introduction of modular arithmetic, a broad explanation is simple. First we prove that casting out nines is equivalent to finding the residue of the integer modulo 9. We also use the homomorphism from the ring of integers, Z, to the ring of integers modulo 9, Z 9, to show that all arithmetic operations (addition, subtraction, multiplication) must be preserved.
\begin{align} h(a)+h(b) &{}\equiv h(a+b) \pmod 9 \\ h(a)-h(b) &{}\equiv h(a-b) \pmod 9 \\ h(a)\times h(b) &{}\equiv h(a\times b) \pmod 9 \end{align}
When a number N is written in decimal form, ak…a2a1a0, we know that its numeric value is a weighted sum of powers of 10,
N = a_k 10^k + \cdots + a_2 10^2 + a_1 10 + a_0 . \,\!
But since 10 is 9+1, we find that
10^n \equiv 1 \pmod 9 \,\!
for all n. Therefore
N \equiv a_k + \cdots + a_2 + a_1 + a_0 \pmod 9 . \,\!
A similar idea applies to casting out elevens, except that 10 is congruent to −1 modulo 11, so we alternately add and subtract digits.
One advanced book regards the correctness of casting out nines as so easy to prove that it is given as an exercise. I do find an explicit short proof on page 385 of Fundamentals of Mathematics (ISBN 978-0-262-52093-5), but it draws on more sophisticated material that precedes it. It is essentially the proof I give above.
Which brings us back to what might be a helpful discussion in the article. As Ask Dr. Math notes, "Casting out nines is not high-school math if all you want to do is use it; but it can take some effort to explain why it works without getting into hard stuff." --KSmrqT 14:25, 7 January 2007 (UTC)

[edit] Example's legibility

It is hard to discern from the example images for Addition, Subtraction etc. what exactly is happening. Italicizing is unclear as most of the numerals are italicized, so one cannot tell which is normal and which is stylized. I suggest using color to better illustrate the point.--74.192.214.241 06:31, 29 May 2007 (UTC)