# elementary number theory: sum of digits

• Oct 17th 2009, 03:23 AM
robeuler
elementary number theory: sum of digits
let x be an integer and let j be the sum of the digits of x. Subtract j from x and get x-j=y. Let k be the sum of the digits of y. Show that y-77,778j cannot equal 7,777,777.

I have tried to do this with divisibility criteria. For instance 77,778j must be even and 77,778 is divisible by 3 while 7,777,777 is not but the arbitrariness of x and y leave me stuck.
• Oct 17th 2009, 08:30 AM
Media_Man
Actually, y must be divisible by three by the following theorem: Let x be an integer and j be the sum of its digits in base 10. Then $\displaystyle x=j (\bmod 3)$ no matter what. Therefore 3|y=x-j, so 3|y-77778j and 7777777 does not.

Pf: Let x be an integer. Expressed in base 10, $\displaystyle x=a_0+a_110^1+a_210^2+...+a_n10^n$ for some unique set of integers $\displaystyle a_i\in\mathbb{Z}_{10}$. Since $\displaystyle 10=1 (\bmod 3)$, $\displaystyle 10^k=1 (\bmod 3)$ for all k, so $\displaystyle x=a_0+a_110^1+a_210^2+...+a_n10^n=$ $\displaystyle a_0+a_1(1)+a_2(1)+...+a_n(1)=a_0+a_1+a_2+...+a_n (\bmod 3)$. QED
• Oct 17th 2009, 10:40 AM
Bingk
Media_Man, you said that y must be divisible by 3, in other words, 3 divides y, which is correct ... but later on, you write that y divides 3 :)