Results 1 to 7 of 7

Math Help - Prove the following (how to tell if a number is divisible by 3)

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    4

    Prove the following (how to tell if a number is divisible by 3)

    This thread has 2 parts.

    The first part consists of a problem I'm going to ask brains more intelligent than mine to help me solve.

    The second part consists of my wanting to know whether a person who has a BA in math who is this helpless when it comes to proofs should bother with grad school.


    The first part.

    Prove that if

    (x1 + x2 + ... + xn) % 3 = 0

    where xi is an integer such that 0 <= xi <= 9

    then the number whose digits equal those xi's, in that particular order, is also divisible by 3.


    This relates to that shorthand way most of us learned in school to tell if a number is divisible by 3. For example, how do we tell if the number 23520 is divisible by 3? We add up its digits and if the sum is divisible by 3, then so is the number. In this case 2 + 3 + 5 + 2 + 0 = 12, which means that 23520 is also divisible by 3.

    ****
    And now back to the second part of this post: given that I have a BA in math, and given that I spent almost 2 hours while I was driving on the highway trying to mentally solve this problem and couldn't do it, does it mean that I am not grad school material? Or am I trying to solve a problem that the average BA in math probably wouldn't be able to solve?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Clarksville, ARk
    Posts
    398

    Re: Prove the following (how to tell if a number is divisible by 3)

    Part 1)

    Let N be a number represented (in decimal) by the digits x_1\,x_2\,x_3\,x_4\dots\,x_{n-2}\,x_{n-1}\,x_n\ .

    What is the numerical value of this number?

    What is 10^k mod 3 ?

    Part 2) It will be difficult to be successful as a grad. student in math without being able to do proofs. With that said: If you continue to work on proofs & get the right help, you can still get the hang of doing proofs.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    4

    Re: Prove the following (how to tell if a number is divisible by 3)

    Quote Originally Posted by SammyS View Post
    Part 1)

    Let N be a number represented (in decimal) by the digits x_1\,x_2\,x_3\,x_4\dots\,x_{n-2}\,x_{n-1}\,x_n\ .

    What is the numerical value of this number?
    10000x1 + 1000x2 + blah blah blah

    What is 10^k mod 3 ?
    1

    So we end up with a summation with xi's times 10^n-i (or whatever). And then we have to prove that that summation mod 3 is going to give us zero given that mod 3 of the sum of the xi's is zero. That's the part I can't do.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,831
    Thanks
    1602

    Re: Prove the following (how to tell if a number is divisible by 3)

    Ok, we want to see if the number \displaystyle x_nx_{n-1}x_{n-2}\dots x_3x_2x_1 is divisible by 3.

    Since \displaystyle x_1 is in the units column, its value is \displaystyle x_1 = 10^0x_1.

    Since \displaystyle x_2 is in the 10s column, its value is \displaystyle 10x_2 = 10^1x_2.

    Since \displaystyle x_3 is in the 100s column, its value is \displaystyle 100x_3 = 10^2x_3.

    \displaystyle \vdots

    Continuing in this fashion we find that \displaystyle x_n is in the \displaystyle 10^{n-1}s column, so its value is \displaystyle 10^{n-1}x_n.

    Also note that every power of 10 will have one remainder when divided by 3 (since they can be written as 9 + 1, 99 + 1, 999 + 1, etc.

    So the value of \displaystyle x_nx_{n-1}x_{n-2}\dots x_3x_2x_1 is

    \displaystyle \begin{align*}&\phantom{=}10^{n-1}x_n + 10^{n-2}x_{n-1} + 10^{n-3}x_{n-2} + \dots + 10^2x_3 + 10x_2 + x_1 \\ &= \left(10^{n-1} - 1\right)x_n + \left(10^{n-2}-1\right)x_{n-1} + \left(10^{n-3}-1\right)x_{n-2} + \dots + \left(10^2 - 1\right)x_3 + \left(10^1 - 1\right)x_2 + x_n + x_{n - 1} + x_{n-2} + \dots + x_3 + x_2 + x_1 \end{align*}

    Each of the \displaystyle 10^k-1 terms is divisible by 3, so the number will only be divisible by 3 if the sum of the remaining terms is divisible by 3.

    So the number \displaystyle x_nx_{n-1}x_{n-2}\dots x_3x_2x_1 is divisible by 3 if \displaystyle x_n + x_{n-1} + x_{n-2} + \dots + x_3 + x_2 + x_1 is divisible by 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2010
    From
    Clarksville, ARk
    Posts
    398

    Re: Prove the following (how to tell if a number is divisible by 3)

    Quote Originally Posted by mathem View Post
    10000x1 + 1000x2 + blah blah blah



    1

    So we end up with a summation with xi's times 10^n-i (or whatever). And then we have to prove that that summation mod 3 is going to give us zero given that mod 3 of the sum of the xi's is zero. That's the part I can't do.
    So, N = 10000x_1 + 1000x_2 + blah blah blah.

    And 10000x_1 + 1000x_2 + blah blah blah ≡ x_1 + x_2 + ... x_n (mod 3)

    Therefore, N ≡ x_1 + x_2 + ... x_n (mod 3).

    ...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2010
    Posts
    4

    Re: Prove the following (how to tell if a number is divisible by 3)

    Quote Originally Posted by Prove It View Post
    Ok, we want to see if the number \displaystyle x_nx_{n-1}x_{n-2}\dots x_3x_2x_1 is divisible by 3.

    Since \displaystyle x_1 is in the units column, its value is \displaystyle x_1 = 10^0x_1.

    Since \displaystyle x_2 is in the 10s column, its value is \displaystyle 10x_2 = 10^1x_2.

    Since \displaystyle x_3 is in the 100s column, its value is \displaystyle 100x_3 = 10^2x_3.

    \displaystyle \vdots

    Continuing in this fashion we find that \displaystyle x_n is in the \displaystyle 10^{n-1}s column, so its value is \displaystyle 10^{n-1}x_n.

    Also note that every power of 10 will have one remainder when divided by 3 (since they can be written as 9 + 1, 99 + 1, 999 + 1, etc.

    So the value of \displaystyle x_nx_{n-1}x_{n-2}\dots x_3x_2x_1 is

    \displaystyle \begin{align*}&\phantom{=}10^{n-1}x_n + 10^{n-2}x_{n-1} + 10^{n-3}x_{n-2} + \dots + 10^2x_3 + 10x_2 + x_1 \\ &= \left(10^{n-1} - 1\right)x_n + \left(10^{n-2}-1\right)x_{n-1} + \left(10^{n-3}-1\right)x_{n-2} + \dots + \left(10^2 - 1\right)x_3 + \left(10^1 - 1\right)x_2 + x_n + x_{n - 1} + x_{n-2} + \dots + x_3 + x_2 + x_1 \end{align*}

    Each of the \displaystyle 10^k-1 terms is divisible by 3, so the number will only be divisible by 3 if the sum of the remaining terms is divisible by 3.

    So the number \displaystyle x_nx_{n-1}x_{n-2}\dots x_3x_2x_1 is divisible by 3 if \displaystyle x_n + x_{n-1} + x_{n-2} + \dots + x_3 + x_2 + x_1 is divisible by 3.
    That makes sense. I just couldn't think of the (10^k - 1) trick.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2010
    Posts
    4

    Re: Prove the following (how to tell if a number is divisible by 3)

    and just to quickly address the second part of my post,

    The proof is clearly very simple but if you can't think of the trick used to get from A to B (ie: throw in -xi + xi) then you are pretty much ****ed.

    This is the reason why I never bothered with grad school.

    If these things don't jump at me, and become obvious only if I see them explained somewhere, then it probably means I would struggle in grad school not so much grasping the material per se but doing the out of the box thinking necessary to get the work done.

    Just saying.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 8th 2010, 12:49 AM
  2. A number divisible by 13,17 or 19
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 21st 2010, 01:47 AM
  3. number divisible
    Posted in the Algebra Forum
    Replies: 3
    Last Post: August 5th 2008, 08:25 PM
  4. Prove n is divisible by 2^m
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 24th 2008, 04:54 AM
  5. Prove n is divisible by 3
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2008, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum