Results 1 to 3 of 3

Math Help - Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0).

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    1

    Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0).

    let n be contained in natural numbers and n=amam-1...a2a1a0 where each ai is a digit of n. Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0). Hint: write n as a base 10 expression in terms of sum of its digits and use number 4.

    This is a homework problem for my discrete math class but it is not graded so we are allowed to work with others on it.

    I do not even know where to start so could someone help me I do not understand at all.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,928
    Thanks
    333
    Awards
    1
    Quote Originally Posted by marielange View Post
    let n be contained in natural numbers and n=amam-1...a2a1a0 where each ai is a digit of n. Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0). Hint: write n as a base 10 expression in terms of sum of its digits and use number 4.

    This is a homework problem for my discrete math class but it is not graded so we are allowed to work with others on it.

    I do not even know where to start so could someone help me I do not understand at all.
    Hint: n = a_n10^n + a_{n - 1}10^{n - 1} +_{\dots} + 10a^1 + a^0

    What is 10 mod 3? So what is 10^k mod 3 for any k?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    757
    you can look at it this way. if n is just one digit long, then of course, 3 has to divide n.

    now, suppose n is two digits long, let's say n = ab, that is n = 10a + b. suppose 3 divides a + b.

    that means a+b = 3k. we can write this as: a = 3k - b. so then n becomes 10(3k - b) + b = 30k - 10b + b = 30k - 9b = 3(10k - 3b).

    on the other hand, if 3 divides 10a + b, so that 10a + b = 3m, then a + b = 10a + b - 9a = 3m - 9a = 3(m - 3a).

    let's look at 3-digits strings: n = abc = 100a + 10b + c. then if 3 divides a + b + c, a = 3k - b - c.

    so n = 100(3k - b - c) + 10b + c = 300k - 90b - 99c = 3(100k - 30b - 33c). if we have 100a + 10b + c = 3m,

    then a + b + c = 100a + 10b + c - 90a - 9b = 3m - 90a - 9b = 3(m - 30a - 3b). do you see the pattern?

    the difference between an10^n + a(n-1)10^(n-1) +...+ 10a1 + a0 and an + a(n-1) +...+ a1 + a0 is always going to be a multiple of 3.

    this tells us that n and the sum of its digits are the same number modulo 3.

    in fact, you can sharpen this even further. the difference is always going to be a multiple of 9, so the exact same logic tells us

    that n is divisible by 9 if and only if the sum of its digits is divisible by 9.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. if p divides x then is xy(mod p) = 0 ?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 11th 2011, 11:52 AM
  2. Replies: 3
    Last Post: October 8th 2011, 04:16 PM
  3. In Z[i], show that 1+i divides...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 21st 2010, 02:37 PM
  4. Replies: 1
    Last Post: February 23rd 2010, 12:36 PM
  5. Replies: 7
    Last Post: November 7th 2009, 04:05 AM

Search Tags


/mathhelpforum @mathhelpforum