elementary number theory: sum of digits

**robeuler** · Oct 17th 2009, 03:23 AM

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.

**Media_Man** · Oct 17th 2009, 08:30 AM

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 $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, $x=a_0+a_110^1+a_210^2+...+a_n10^n$ for some unique set of integers $a_i\in\mathbb{Z}_{10}$ . Since $10=1 (\bmod 3)$ , $10^k=1 (\bmod 3)$ for all k, so $x=a_0+a_110^1+a_210^2+...+a_n10^n=$ $a_0+a_1(1)+a_2(1)+...+a_n(1)=a_0+a_1+a_2+...+a_n (\bmod 3)$ . QED

**Bingk** · Oct 17th 2009, 10:40 AM

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

Thread: elementary number theory: sum of digits

LinkBack

Thread Tools

Display

elementary number theory: sum of digits

Similar Math Help Forum Discussions

elementary number theory question

two elementary number theory problem:

Elementary Number Theory - when to use converse?

Elementary Number Theory

elementary Number Theory

Search Tags