Results 1 to 11 of 11

Math Help - divisibility

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    96

    divisibility

    For a positive integer n, Let S(n) denote the sum of its decimal digits.

    Then S(n)-n is always divisible by?

    A)9
    B)10
    C)11
    D)None of these is always true.


    The only problem is i did not get what is meant by decimal digits of the integer?


    Follow Math Help Forum on Facebook and Google+

  2. #2
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    29
    If n is an integer then decimal digits must imply we are talking about numbers in the decimal system, I.e normal counting numbers as you know them.

    Now pick any number n = 205 so S(n) = 2+0+5 = 9

    Now S(n)-n = 205 - 9 = 196

    196 is not divisble by 9, 10 or 11. Therefore we have found 1 example that contracdicts each of these sases therefore I think D is the answer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    unfortunately 2 + 0 + 5 = 7\not = 9 so this will not work. But I have an answer for you, the answer is A and I will explain below. I hope you know modular arithmetic if you were asked this question. I just wanted to catch you before you thought the answer was D.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    let n be a positive integer.

    then n=a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0
    So then S(n)=a_n + a_{n-1} + ... + a_1 + a_0

    but consider the fact that
    10\equiv 1 (mod 9)

    induction if you want to be formal shows this means

    10^k \equiv 1 (mod 9) for all k\in \mathbb{N}


    So if we consider
    S(n)-n = (a_n + a_{n-1} + ... + a_1 + a_0) - a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0


    But reduce this mod 9
    S(n)-n \equiv (a_n + a_{n-1} + ... + a_1 + a_0) - a_n1^n + a_{n-1}1^{n-1} + ... + a_11^1+a_0 \equiv 0 (mod 9)

    But if two things are congruent to 0 mod 9, this means 9 divides this number.

    So 9 divides S(n)-n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2008
    Posts
    96
    Quote Originally Posted by Gamma View Post
    let n be a positive integer.

    then n=a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0
    So then S(n)=a_n + a_{n-1} + ... + a_1 + a_0

    but consider the fact that
    10\equiv 1 (mod 9)

    induction if you want to be formal shows this means

    10^k \equiv 1 (mod 9) for all k\in \mathbb{N}


    So if we consider
    S(n)-n = (a_n + a_{n-1} + ... + a_1 + a_0) - a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0


    But reduce this mod 9
    S(n)-n \equiv (a_n + a_{n-1} + ... + a_1 + a_0) - a_n1^n + a_{n-1}1^{n-1} + ... + a_11^1+a_0 \equiv 0 (mod 9)

    But if two things are congruent to 0 mod 9, this means 9 divides this number.

    So 9 divides S(n)-n
    thanks! but i believe they expect me to do it without modular arithmetic(as that is not in my course-i wish i knew that, sorry.) ill try to study that online.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    Alternate Proof without modular arithmetic :(

    Definitely worth learning, however, there is in fact an alternative method that I think you can do with out modular arithmetic. Let's hope you at least know induction.

    Lemma:
    9|10^k-1 for all  k\in \mathbb{N}
    k=1
    9|10-1=9 This is clearly true.

    (Induction Hypothesis) Suppose up to n,
    9|10^n-1

    Now we must show 9|10^{n+1}-1
    10^{n+1}-1=10^{n+1}-1-9+9=10^{n+1}-10+9=10(10^n-1)+9
    But by induction hypothesis 9 divides the first term and clearly 9|9, so 9 divides the sum and the induction is complete.



    Okay, so now pick up my old proof up at the point where I wrote out
    S(n) - n = a_n + a_{n-1} + ... + a_1 + a_0 - a_n10^n + a_{n-1}10^n + ... + a_110^1 + a_010^0
    Now instead of the modular argument, we will group nicely by coefficient.
    S(n) - n = a_n(1-10^n) + a_{n-1}(1-10^n) + ... + a_1(1-10^1) + a_0(1-10^0)

    So by our lemma 9|10^k-1 \Rightarrow 9|-(10^k-1)=1-10^k but this means 9 divides every term so 9 must divide the whole thing which is S(n)-n as desired. QED (again)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jun 2008
    Posts
    96
    Quote Originally Posted by Gamma View Post
    Definitely worth learning, however, there is in fact an alternative method that I think you can do with out modular arithmetic. Let's hope you at least know induction.

    Lemma:
    9|10^k-1 for all  k\in \mathbb{N}
    k=1
    9|10-1=9 This is clearly true.

    (Induction Hypothesis) Suppose up to n,
    9|10^n-1

    Now we must show 9|10^{n+1}-1
    10^{n+1}-1=10^{n+1}-1-9+9=10^{n+1}-10+9=10(10^n-1)+9
    But by induction hypothesis 9 divides the first term and clearly 9|9, so 9 divides the sum and the induction is complete.



    Okay, so now pick up my old proof up at the point where I wrote out
    S(n) - n = a_n + a_{n-1} + ... + a_1 + a_0 - a_n10^n + a_{n-1}10^n + ... + a_110^1 + a_010^0
    Now instead of the modular argument, we will group nicely by coefficient.
    S(n) - n = a_n(1-10^n) + a_{n-1}(1-10^n) + ... + a_1(1-10^1) + a_0(1-10^0)

    So by our lemma 9|10^k-1 \Rightarrow 9|-(10^k-1)=1-10^k but this means 9 divides every term so 9 must divide the whole thing which is S(n)-n as desired. QED (again)
    yes. i do know some stuff :P
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    Oh man, I didn't mean it to be a slight at all. I can see how that could have sounded pretty disrespectful, I just meant it more in the sense of I have no idea how to prove it without induction! It is always a difficult thing to judge what type of proof to present on here since I have no idea what kind of mathematical background any of the askers have. It is a struggle to find a common ground of risking using a fact or something the reader may be unfamiliar with and being able to present a concise elegant proof.

    Well, if you find this problem interesting and are curious about doing another really fun problem like this you should consider the following. Also it would be a great practice for you if you decide to learn modular arithmetic (which you will have to if you continue in number theory, algebra, or discrete mathematics). Consider the test for divisibility by 11.

    A number is divisible by 11 if and only if the alternating sum of its digits is divisible by 11.

    Here is what I mean.
    Is 72237 divisible by 11?
    7 -3 +2 -2 +7 = 11 which is divisible by 11 clearly, so 72237 number is divisible by 11.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    29
    Quote Originally Posted by Gamma View Post
    unfortunately 2 + 0 + 5 = 7\not = 9
    Opps!


    Gamma,

    I can recall a similar pattern that if the digits of an integer add to a multiple of 9 then it will be divisible by 9.

    For example 2412, 2+4+1+2 = 9 and 2412/9 = 268

    and 98172, 9+8+1+7+2 = 27 and 98172/9 = 10908

    Apart from this one and the sum of alternating digits for divisibilty by 11, do you know any others?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    The other ones are really unsatisfying that I know compared to these two, lol.

    For 2, if it ends in 0,2,4,6,8 it is divisible by two... duh it is even

    For 3, if you sum the digits and it is divisible by 3 the number is divisible by 3.

    For 4, if you look at the last two digits if they are divisible by 4 then the whole thing is 4|100 is why.

    For 5, again, look at whether the last digit is 5 or 0, then it is divisible by 5, otherwise it is not.

    For 6, check divisibility by 2 and 3 if it is divisible by both then it is divisible by 6.

    For 7 I am honestly not sure of a good test for this divisibility

    For 8 you just gotta check the last 3 digits because 8|1000

    For 9, yeah we got that one on lock down

    For 10 if it ends in 0 yeah, otherwise not.

    For 11 the one i mentioned is the only test i know.

    Of course you can generalize the one for 6. If it is a product of distinct primes you can just check it for divisibility by each of the distinct primes that make up the number.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    29
    Thanks mate!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 03:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 02:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum