Proof of the Digital Root Theorem. By Cino hilliard Jan 10, 2003 The digital root of an integer x is 9 if 9 divides x or the remainder of x/9 if 9 does not divide x. Proof: Case 1. 9 does not divide x We write x as a polynomial in powers of 10 where d(i) are the digits of x. (1) x = 10^n*d(n) + 10^(n-1)*d(n-1) + ...+ d(0) Subtracting the sum of the digits d(n)+d(n-1)+...+d(0) from both sides (2) x - (d(n)+d(n-1)+...d(0)) = d(n)(10^n-1)+d(n-1)(10^(n-1)-1)+...d(1)(10-1) Since 9 divides 10^i-1 for i = 1 to n, (2) implies 9 divides (3) x - sum(d(i)) = 9z. This implies that if 9 does not divide x, then 9 does not divide sum(d(i)). Similarly, if 9 divides sum(d(i)) 9 divides x (casting out nines property). So we have (4) x = 9k+r (5) sum(d(i)) = 9l+s where r < 9,s < 9. Substituting (4) and (5) into (3), we get (6) 9k - 9l + r - s = 9z. This implies 9 divides r - s wich implies r-s = 0 and r=s other wise r >= 9 contradicting the condition r < 9. Thus far we have shown that the remainder of x/9 is the same as the remainder of sum(d(i))/9. Now we express sum(d(i)) in polynomial form as we did for x in (1). (1.1) sum(d(i)) = 10^m*d1(m) + 10^(m-1)*d1(m-1) + ...+ d1(0) Using the same argument as in (1) to (3) we get (2.1) sum(d(i))-(d1(m)+d1(m-1)+...d1(0)) = d1(m)(10^m-1)+d1(m-1)(10^(m-1)-1)+...d1(1)(10-1) Since 9 divides 10^i-1 for i = 1 to m, (2.1) implies 9 divides (3.1) sum(d(i)) - sum(d1(i)) = 9z This implies that if 9 does not divide sum(d(i)),then 9 does not divide sum(d1(i)). Similarly, if 9 divides sum(d(i)) then 9 divides sum(d1(i)). So we have (4.1) sum(d(i)) = 9l + s from (5) (5.1) sum(d1(i)) = 9z1 + s1 where s < 9,s1 < 9. Substituting (4.1) and (5.1) into (3.1), we get (6.1) 9l - 9z1 + s - s1 = 9z1. This implies 9 divides s - s1 which implies s-s1 = 0 and s=s1=r other wise s >= 9 contradicting the condition s < 9. Clearly, we can repeat this process 1.j to 6.j until sum(dj(i)) is a single digit. Then sum(dj(i)) = sj = r = remainder of x/9. This completes case 1. Case 2. 9 divides x. Using similar arguments as in case 1 we note that if the sum of the digits of x = 9k then after a finite number of steps the sum of the digits will reduce to a single digit = 9. Obviously this will never occur for prime numbers since a prime <> 9k.