Number theory problem 2

[Obelix]

The following holds: If from any integer we subtract the sum of its digits, then the result is divisible by 9. E.g. take 1456. The sum of its digits is:

1 + 4 + 5 + 6 = 16. Then: 1456 - 16 = 1440 = 160 x 9.

 

Give a rigorous proof of the above statement! How does it generalize?

Edited May 21, 2011 by Obelix

[rktpro]

I doubt a generalized result might be available. It would have been tested on a certain quantity of numbers and been observed.

[DJBruce]

The following holds: If from any integer we subtract the sum of its digits, then the result is divisible by 9. E.g. take 1456. The sum of its digits is:

1 + 4 + 5 + 6 = 16. Then: 1456 - 16 = 1440 = 160 x 9.

 

Give a rigorous proof of the above statement! How does it generalize?

 

 

This does generalize to any desired base, and the proof is relatively straightforward. Have you made any attempts at it? I feel like this is a homework question so I won't give you all the work -especially if you haven't shown any work towards the problem- but I'll give you a few tips.

 

-What do we really mean when we write a number in base-10?

-What does it mean that something is divisible by 9?

 

Answer these and the proof should be fairly straight forward. However, if you still need help post your work so we can see what you might be stuck on.

 

 

[DrRocket]

The following holds: If from any integer we subtract the sum of its digits, then the result is divisible by 9. E.g. take 1456. The sum of its digits is:

1 + 4 + 5 + 6 = 16. Then: 1456 - 16 = 1440 = 160 x 9.

 

Give a rigorous proof of the above statement! How does it generalize?

 

This your second post in multiple forums of a straightforward and elementary algebra problem (this one has literally a one line proof). It is rather obvious that this is a class assignment. You have not posted under "Homework Help" and are asking, not for help, but for a solution.

 

This is called cheating.

 

If anyone other than Obelix desires to see the simple proof, send me a PM.

Edited May 22, 2011 by DrRocket

[rktpro]

I would also like to know the answer. This problem is above my syllabus,though. Thanks.

[DrRocket]

I would also like to know the answer. This problem is above my syllabus,though. Thanks.

 

Check your PM box. If you have questions reply to the PM.

[Obelix]

This is called cheating.

 

I call it chatting!

 

Have you made any attempts at it?

 

Well then: Any integer [math]\pm a_n a_{n-1} \dots a_1 a_0,[/math] where: [math]0 \leq a_i \leq 9, \ \ \forall i = 0, 1, 2, ..., n, n:[/math] Natural, is actually of the form: [math] \pm (a_n 10^n + a_{n-1} 10^{n-1} + \dots + a_10 + a_0)[/math]. We can proceed by induction on [math]n[/math]:

 

For [math]n = 0[/math] the integer is a one - digit number [math]\large 0 \leq a \leq 9[/math], whence the sum of its digits is [math]a[/math], whereas [math]a - a = 0[/math] clearly divisible by 9.

 

Suppose the statement holds for [math]n = m[/math], i.e. for any number of the form: [math]a_m 10^m + \dots + a_1 10 + a_0[/math] we have: [math]a_m 10^m + \dots + a_1 10 + a_0 - (a_m + a_{m-1} + \dots + a_1 +a_0 = 9k), k:[/math] integer.

 

Then, for [math]n = m + 1: a_{m+1} 10^{m+1} + a_m 10^m + \dots + a_1 10 + a_0 = [/math] [math]a_{m+1} 10^{m+1} + (a_m 10^m + \dots + a_1 10 + a_0)[/math]. The quantity in parenthsis fullfils the required property, according to the assumption of the induction, whence: [math]a_{m+1} 10^{m+1} + a_m 10^m + \dots + a_1 10 + a_0 - (a_{m+1} + a_m + \dots + a_1[/math] [math]+ \, a_0) = (a_{m+1} 10^{m+1} - a_{m+1})+[/math] [math][a_m 10^m + \dots + a_1 10 + a_0 - (a_{m+1} + a_m + \dots + a_1 + a_0)][/math] [math]= a_{m+1} (10^{m+1} - 1) + 9k = [/math] [math]a_{m+1} (10 - 1) (10^m + 10^{m-1} + \dots + 10 + 1) + 9k =[/math] [math]9a_{m+1} (10^m + 10^{m-1} + \dots + 10 + 1) + 9k [/math] [math]= 9[a_{m+1} (10^m + 10^{m-1} + \dots + 10 + 1) + k][/math], Q.E.D.

 

Set ANY base [math]b \geq 0[/math] in the place of 10, replace 9 by [math]b-1[/math], consider [math]0 \leq a_i \leq b, \ \ \forall i = 0, 1, 2, ..., n[/math] and the proof generalizes directly!

 

It is rather obvious that this is a class assignment. You have not posted under "Homework Help" and are asking, not for help, but for a solution.

 

For your information, I am a tutor of Mathematics. Why don't you take a slight trouble to check my profile?

 

And yes, it was an assignment - for YOU.

Edited May 22, 2011 by Obelix

[DJBruce]

Your proof looks correct, but its way to long and induction is completely unnecessary.

 

Take [math]x \in \mathbb{Z}[/math] [math]x[/math] can be written as:

[math]x=\sum_{i=0}^{n}a_{i}10^{i}, a_{i}\in\{0,1,2,3,4,5,6,7,8,9\}[/math]

Note [math]10\equiv 1mod(9)[/math]

Therefore, [math]\sum_{i=0}^{n}a_{i}10^{i}\equiv \sum_{i=0}^{n}a_{i} mod(9) \Rightarrow \sum_{i=0}^{n}a_{i}10^{i}-\sum_{i=0}^{n}a_{i} \equiv 0mod(9)[/math]

 

So like Dr.Rocket said this should be a one liner since really only the last line of mine is truly needed.

 

Also you have to realize that when you post a question with simply, "Give a rigorous proof of the above statement!" it makes it seem like you are a student asking for someone to do their homework. I mean if you frequent any forum you will see numerous posts like this that do come from people looking for answers. If you just want to post problems you find interesting make it clear that it is not homework because it will mean people will be more likely to respond to your challenge since they will be sure its not homework.

Edited May 22, 2011 by DJBruce

[DrRocket]

Your proof looks correct, but its way to long and induction is completely unnecessary.

 

Take [math]x \in \mathbb{Z}[/math] [math]x[/math] can be written as:

[math]x=\sum_{i=0}^{n}a_{i}10^{i}, a_{i}\in\{0,1,2,3,4,5,6,7,8,9\}[/math]

Note [math]10\equiv 1mod(9)[/math]

Therefore, [math]\sum_{i=0}^{n}a_{i}10^{i}\equiv \sum_{i=0}^{n}a_{i} mod(9) \Rightarrow \sum_{i=0}^{n}a_{i}10^{i}-\sum_{i=0}^{n}a_{i} \equiv 0mod(9)[/math]

 

So like Dr.Rocket said this should be a one liner since really only the last line of mine is truly needed.

 

Also you have to realize that when you post a question with simply, "Give a rigorous proof of the above statement!" it makes it seem like you are a student asking for someone to do their homework. I mean if you frequent any forum you will see numerous posts like this that do come from people looking for answers. If you just want to post problems you find interesting make it clear that it is not homework because it will mean people will be more likely to respond to your challenge since they will be sure its not homework.

 

[math]10\equiv 1mod(9)[/math] is the only observation needed. Everything else should be obvious to anyone who knows what a ring is.

 

I flat do not believe Obelix. He has made exactly the same post elsewhere. The questions are trivial, about what one would expect in an introductory class. The "proof" that he offers is clumsy and lacking in insight. If he is not looking for help in a mathematics class, then he should be.

 

I have had students lie before. My BS meter is fully functional.

[mooeypoo]

!

Moderator Note

Moved to homework help.