如何證明一個數的數根(digital root)就是它對9的餘數？

01-16

我已經通過二項式定理證明了一個數和它的各數位之和的模9相同，但是為什麼一個數的數根就是它對9的餘數呢？

假設有一個n位的10進位數，我們寫成 $x = sum_{i=0}^{n-1}{a_i}{10^i}$ ，其中 $a_i$ 表示從低到高的每一位

因為 $10^n equiv 1^n equiv 1 mod 9$

那麼 $x equiv sum_{i=0}^{n-1}a_i mod 9$

也就是一個數和它的各數位之和的模9相同。

不如我們把這個操作記為f即 $f(x) = sum_{i=0}^{n-1}a_i$

也就是 $f(x) equiv x mod 9$

所以

$f(f(x)) equiv f(x) equiv x mod 9$

也就是說每做一次這樣的操作，它對於9的模始終是不變的

所以最終求出的數根和原數對9的模相同。

題目中命題錯誤！

重要的事情說三遍。

一個數 $x$ 的數根為 $mod(x-1,9)+1$ .因為正整數對9取模的結果取值為 $[0,8]$ ,,而數根的取值為 $[1,9]$ 。

之所以強調，是因為曾經參加比賽按照題目中的命題寫的錯了一次。

share一下理解公式的過程，ps我也是從leetcode上的題過來的

首先是公式，引用自維基百科Digital root

嗯一下子沒看懂，然後在網上搜到了樓上說的那篇好文章

感覺豁然開朗

需要利用構造法證明，

令1+2+3+4+5 = y

則dr(12345) = dr(y) = dr(9n+y)

也就是說dr(y) = dr(9n+y)

令9n+y=X，則

dr(X) = dr(X%9)

X%9為個位數，所以dr(X%9) = X%9

所以dr(X) = X%9

也有特殊情況，如果X為9的倍數，那麼在dr(12345) = dr(y) = dr(9n+y)中，y為9的倍數，則由dr(y) = dr(9n+y)得到dr(X) = dr(X%9)是不成立的。所以最後的結果也不成立，所以n為9的倍數的時候是特殊情況。至於為什麼dr(9n)=9，可以利用上面類似的思路證明。

久違的構造法啊，想了我好久

今天寫演算法碰到這個問題

http://www.flyingcoloursmaths.co.uk/a-neat-number-trick-digital-roots-and-modulo-9-arithmetic/

這個文章說的很好。

看這個應該就懂了：

12,345 = 1 × (9,999 + 1) + 2 × (999 + 1) + 3 × (99 + 1) + 4 × (9 + 1) + 5.

12,345 = (1 × 9,999 + 2 × 999 + 3 × 99 + 4 × 9) + (1 + 2 + 3 + 4 + 5).

上面的答案都寫的很好，也是LeetCode上看到這個問題，還是小白，就結合著上面的答案，舉個形象的例子：

首先：

12345 = 1 * 9999 + 2 * 999 + 3 * 99 + 4 * 9
+ 5 + (1+ 2+ 3 + 4 + 5)

只要證明：12345 % 9 = (1 + 2 + 3 + 4 +5 ) % 9 就能往下遞推了。

那麼，我們已知：

m % 9 = a; n % 9 = b 即 m = 9 * x +
a; n = 9 * y + b；可推出
(m + n) % 9 = a + b = m % 9 + n % 9；

[1 * 9999 + 2 * 999 + 3 * 99 + 4 * 9 + (1+
2+ 3 + 4 + 5)] % 9 = (1 * 9999) % 9 + (2 * 999) % 9 + (3 * 99) % 9 + (4 * 9) %
9 + (1+ 2+ 3 + 4 + 5) % 9 = 0 + 0 + 0 + 0 + (1 + 2 + 3 + 4 + 5) % 9 = (1 + 2 +
3 + 4 + 5) % 9。

證明完成：12345 % 9 = (1 + 2 + 3 + 4 + 5) % 9 ;

因為題中最後一個數恰好是小於10，與取mod 9結束也一致，所以：

(12345) % 9 = (1 + 2 + 3 + 4 + 5) % 9 = 12
% 9 = (1 +2) % 9 = 3 % 9 = 3。

DTStor – Data Storage / 【leetcode解題報告】258-Add Digits

請參考下這個博文~

啊廢話，數根就是不斷地求這個數的各位數之和，直到求到個位數為止。所以數根一定和該數模9同餘，但是數根又是大於零小於10的，所以數根模9的餘數就是它本身，也就是說該數模9之後餘數就是數根。

阿西吧！