Following is the proof that Cast9(a) = mod9 (a-1) + 1. Let's start with a few definitions that the proof will use:
- Let a = source number.
- Let's refer to the rightmost digit of a as a0 and to the leftmost digit of a as an.
- Let a' = ∑ n i=0ai, i.e., sum of digits of a.
- Let a" = recursive sum of digits of a until one digit is left—i.e., Cast9(a).
Let's prove that a" = mod9 (a-1) + 1. You can represent the number a as the sum of its digits multiplied by 10 to the power of the digit's position: a = 10nan + 10n-1an-1 +...+101a1 +100a0. For example, you can represent the number 947 as 102 * 9 + 101 * 4 +100 * 7.
You can represent the number as a number composed of i instances of 9 plus 1 (999... + 1) or as 9 multiplied by i digits of 1 plus 1 (9 x 111... + 1). For example, you can represent 103 as 999
+ 1 or as 9 * 111 + 1. Let's refer to a number composed of i digits of 1 as xi. Applying this rule to the previous equation, you can write:
a = (9xn + 1)an + (9xn-1 + 1)an-1 +...+ (9x1 + 1)a1 + (9x0 + 1)a0 =
9xnan + an + 9xn-1an-1 +...+ 9x1a1 + 9x0a0
You can separate the parts that are multiplied by xi (where i ranges from 0 to n) from the
parts that aren't, then rewrite the equation in the summarized notation a = 9∑ni=0xiai + ∑ni=0ai. Performing a modulo 9 operation on both sides of the equation, you get mod9 (a) = mod9 (9∑ni=0xiai + ∑ni=0ai). From the rules of modulo, it follows that modb (bc + d) = modb (d). Applying this rule to the previous equation gives you mod9 (a) = mod9 (∑ni=0ai). Notice that the sigma inside the parentheses on the right side of the equation is the sum of all the digits of a. You can rewrite the equation as mod9 (a) = mod9 (a').
Thus, modulo 9 of a number is equal to modulo 9 of the sum of that number's digits. Applying that conclusion to the sum of the source number's digits, you can say that modulo 9 of the sum of a number's digits is equal to modulo 9 of the sum of the digits of the result number. You can continue in this manner until one digit remains, but let's simply conclude that the equation is recursive. You can, therefore, write mod9 (a) = mod9 (a') = ... = mod9 (a").
Remember that we defined a" as the recursive sum of the digits of the number a. From the rules of modulo, it follows that if modb (c) = modb (d), then modb (c + e) = modb (d+ e). Applying this rule to the previous equation, you get mod9 (a 1) = mod9 (a" 1).
For any a > 0, a" is a digit in the range of 1 to 9, so (a" 1) is in the range of 0 to 8. Modulo 9 of any number in the range of 0 to 8 is the number itself; hence, mod9 (a" 1) = a" 1. Applying this rule to the previous equation, you get mod9 (a 1) = a" 1. And by adding 1 to both sides of the equation to simplify it, you get mod9 (a 1) + 1 = a"
