WordGPT

Why the digit sum tells you divisibility by 9

Exercise · Level 2 (Easy)

Prove that a number leaves the same remainder as its digit sum when divided by 9.

n≡(digit sum of n)(mod9)n\equiv\text{(digit sum of }n)\pmod 9

wordgptpro.com

Solution

  1. Since 10≡1(mod9)10\equiv1\pmod9, every power 10k≡110^k\equiv1. Write n=dk10k+⋯+d110+d0n=d_k10^k+\cdots+d_110+d_0 with digits did_i:

    n≡dk+⋯+d1+d0(mod9)n\equiv d_k+\cdots+d_1+d_0\pmod9
    (1)
  2. Example: 1234512345 has digit sum 15, and 15 leaves remainder 6; 12345=1371⋅9+612345=1371\cdot9+6, so the remainder of 12345 is 6. (The same works for 3, since 3 divides 9.)

Answern≡digit sum(mod9)n\equiv\text{digit sum}\pmod 9

wordgptpro.com

Need a hint?

Powers of 10 all leave remainder 1 modulo 9.

A number and its digit sum leave the same remainder on division by 9 (and by 3): 12345 has digit sum 15 and remainder 6.

How to work it out

  1. Since 10≡1(mod9)10\equiv1\pmod9, every power 10k≡110^k\equiv1. Write n=dk10k+⋯+d110+d0n=d_k10^k+\cdots+d_110+d_0 with digits did_i:

    n≡dk+⋯+d1+d0(mod9)n\equiv d_k+\cdots+d_1+d_0\pmod9
    (1)
  2. Example: 1234512345 has digit sum 15, and 15 leaves remainder 6; 12345=1371⋅9+612345=1371\cdot9+6, so the remainder of 12345 is 6. (The same works for 3, since 3 divides 9.)

LaTeX source of the formulas on this page
\[ n\equiv\text{digit sum}\pmod 9 \]
\[ n\equiv d_k+\cdots+d_1+d_0\pmod9 \]

Questions

What is the answer to: Why the digit sum tells you divisibility by 9?

A number and its digit sum leave the same remainder on division by 9 (and by 3): 12345 has digit sum 15 and remainder 6.

What is the key idea?

10 ≡ 1 (mod 9), so each digit counts only once.

Is there a hint?

Powers of 10 all leave remainder 1 modulo 9.

Related problems

More number theory problems

    Why the digit sum tells you divisibility by 9: answer and solution | WordGPT