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

Printable View

August 13th 2011, 06:28 PM
mathem

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?
August 13th 2011, 06:48 PM
SammyS

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.
August 13th 2011, 07:17 PM
mathem

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

Quote:

Originally Posted by SammyS

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

Quote:

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.
August 13th 2011, 07:41 PM
Prove It

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.
August 13th 2011, 08:05 PM
SammyS

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

Quote:

Originally Posted by mathem

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).

...
August 14th 2011, 03:40 AM
mathem

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

Quote:

Originally Posted by Prove It

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.
August 14th 2011, 03:55 AM
mathem

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.