Notices
Results 1 to 14 of 14

Thread: Number theory problem 2

  1. #1 Number theory problem 2 
    Forum Freshman
    Join Date
    Aug 2008
    Posts
    18
    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?


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    Well, I know how my proof would look. How would yours look?


    373 13231-mbm-13231 373
    Reply With Quote  
     

  4. #3  
    Veracity Vigilante inow's Avatar
    Join Date
    Oct 2009
    Location
    Austin, TX
    Posts
    3,499
    Quote Originally Posted by thyristor
    Well, I know how my proof would look. How would yours look?
    I'm guessing it would use an annoyingly large font. [/rimshot]
    Reply With Quote  
     

  5. #4 Re: Number theory problem 2 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by 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?
    This is your second post of a relatively straightforward problem (this example is a one-liner) in number theory (both are straightforward applications of ring theory). It is pretty clear that these ae class assignments for a class.

    Nobody is going to do your assignments for you.

    You are sttempting to cheat.
    Reply With Quote  
     

  6. #5  
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    Quote Originally Posted by inow
    Quote Originally Posted by thyristor
    Well, I know how my proof would look. How would yours look?
    I'm guessing it would use an annoyingly large font. [/rimshot]
    Indeed
    373 13231-mbm-13231 373
    Reply With Quote  
     

  7. #6 A proof. 
    Forum Freshman
    Join Date
    Aug 2008
    Posts
    18
    Well then: Any integer where: Natural, is actually of the form: . We can proceed by induction on :

    For the integer is a one - digit number , whence the sum of its digits is , whereas clearly divisible by 9.

    Suppose the statement holds for , i.e. for any number of the form: we have: integer.

    Then, for . The quantity in parenthsis fullfils the required property, according to the assumption of the induction, whence: , Q.E.D.

    Set ANY base in the place of 10, replace 9 by , consider and the proof generalizes directly!
    Reply With Quote  
     

  8. #7  
    Forum Bachelors Degree x(x-y)'s Avatar
    Join Date
    Jul 2010
    Location
    UK
    Posts
    462
    You do realise that by using that size font, it doesn't make people want to read your posts- it has the opposite effect infact. Just use the normal font size!
    "Nature doesn't care what we call it, she just does it anyway" - R. Feynman
    Reply With Quote  
     

  9. #8 Re: A proof. 
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    Quote Originally Posted by Obelix
    Well then: Any integer where: Natural, is actually of the form: . We can proceed by induction on :

    For the integer is a one - digit number , whence the sum of its digits is , whereas clearly divisible by 9.

    Suppose the statement holds for , i.e. for any number of the form: we have: integer.

    Then, for . The quantity in parenthsis fullfils the required property, according to the assumption of the induction, whence: , Q.E.D.

    Set ANY base in the place of 9, consider and the proof generalizes directly!
    Your proof of the special case (that is to say that the number minus the sum of its digits in base 10 is divisible by 9) looks right. However, you needn't use induction. Can you think of an easier way? It's sort of in your proof, you use it in one of the steps.

    As someone has already pointed out, it's much nicer to read your posts if you write in normal-sized font.

    Concerning the general case, I think you have misunderstood it and don't quite understand what you mean by "set any base in the place of 9". Here's a hint: the proof of the special case deals with numbers in base 10 and states that any such number minus the sum of its digits is divisible by 9. How is 9 related to 10. What number would be interesting to check division for if it were say base 3?
    373 13231-mbm-13231 373
    Reply With Quote  
     

  10. #9 Re: A proof. 
    Forum Freshman
    Join Date
    Aug 2008
    Posts
    18
    Quote Originally Posted by thyristor
    What number would be interesting to check division for if it were say base 3?
    Number 2.

    You are right, I ought to have added: "Replace 9 by for an arbitrary base ."
    Reply With Quote  
     

  11. #10 Re: A proof. 
    Forum Masters Degree thyristor's Avatar
    Join Date
    Feb 2008
    Location
    Sweden
    Posts
    542
    Quote Originally Posted by Obelix
    Quote Originally Posted by thyristor
    What number would be interesting to check division for if it were say base 3?
    Number 2.

    You are right, I ought to have added: "Replace 9 by for an arbitrary base ."
    You got it.
    373 13231-mbm-13231 373
    Reply With Quote  
     

  12. #11 Re: Number theory problem 2 
    Forum Freshman
    Join Date
    Aug 2008
    Posts
    18
    Quote Originally Posted by DrRocket
    Nobody is going to do your assignments for you.

    You are sttempting to cheat.
    I'm just attempting to chat!

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

    The assignment was for YOU.
    Reply With Quote  
     

  13. #12 Re: A proof. 
    Forum Freshman
    Join Date
    Aug 2008
    Posts
    18
    Quote Originally Posted by thyristor
    However, you needn't use induction. Can you think of an easier way? It's sort of in your proof, you use it in one of the steps.
    Surely one could simply write: = etc. The induction just feels more rigorous!
    Reply With Quote  
     

  14. #13 Re: Number theory problem 2 
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,620
    Quote Originally Posted by Obelix
    For your information, I am a tutor of Mathematics.
    And yet you seem never to have encountered modulo arithmetic. Tut, tut!
    The assignment was for YOU.
    As none here are your tutees and never asked for an "assignment", this is a slightly presumptuous comment. There are many here who can see exactly how the proof is a lot simpler (and more correct) than yours.

    As DrRocket says, the proof is very short using modulo arithmetic (though I think "one liner" is a slight exaggeration)
    Reply With Quote  
     

  15. #14 Re: Number theory problem 2 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Obelix
    Quote Originally Posted by DrRocket
    Nobody is going to do your assignments for you.

    You are sttempting to cheat.
    I'm just attempting to chat!

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

    The assignment was for YOU.
    I don't need silly assignments.

    The proof of this one is simply mod 9. All else is obvious to anyone who knows what a ring is.

    Your "proof" is clumsy and lacks insight. Your posts and use of large font are annoying.

    If you are not a student looking for help outside of a class, then you should be.
    If you are a tutor, I pity the students.

    If you want to discuss mathematics ditch the obnoxious font and say something non-trivial.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •