You are Here: Home >< Maths

# The Maths Problem You Will Never Solve (Probably)! watch

1. Sorry, to clear things up the method I was talking about was actually identical to Unbounded's proof in the first page.
2. Link for those interested in this problem

http://en.wikipedia.org/wiki/Divisibility_rule
3. (Original post by generalebriety)
Good thoughts. Few criticisms, then. What about 99 + 3? 999 + 3? Can you find some general way of explaining what happens when we have to take up a new 'column'? Also, as far as I can see, you've attempted to explain here that every multiple of 3 has digits that add up to a multiple of 3, but not conversely; can you prove that everything that has digits that add up to a multiple of 3 is a multiple of 3? (Equivalently, can you prove that if something isn't a multiple of 3 then its digits don't add up to a multiple of 3?)

Erm sorry i was a bit vague but the solution to the '9999' is consideredthe concept if we have a number with all digits 9, eg 9999. then it will make a transition into a number with 1 as the preceeding digit followed by 2 as the last digit, this will always results into sum of 3. I see what you mean about the converse. If i've proved that EVERY number which is a multiple of 3 has sum of digits which is a multiple of 3. Then that will mean every number which doesn't have a factor of 3 doesn't have sum of digits with a factor of 3.
4. (Original post by DeanK22)
213 = 200 + 10 + 2.
5. (Original post by tanakataku7)
If i've proved that EVERY number which is a multiple of 3 has sum of digits which is a multiple of 3. Then that will mean every number which doesn't have a factor of 3 doesn't have sum of digits with a factor of 3.
Not quite, actually. For example: every number which is a multiple of 6 has digit sum a multiple of 3, but this doesn't prove that every number which is not a multiple of 6 has digit sum which is not a multiple of 3.
6. (Original post by generalebriety)
Not quite, actually. For example: every number which is a multiple of 6 has digit sum a multiple of 3, but this doesn't prove that every number which is not a multiple of 6 has digit sum which is not a multiple of 3.
That's not what i said, I said every number which isn't a multiple of 3 will not have sum digits with a multiple of 3. 6 has different properties from 3. There are numbers which are multiples of 3 but not multiples of 6. So since there are multiples of 3 which are not multiples of 6, such as 9. Then it's obvious that not all numbers which aren't multiples of 6, eg 9, will not be divisible by 3. You can't consider 6, you can only consider the 3 times table, it was central in my proof. I'm pretty sure this is correct
7. I was expecting the Riemann Hypothesis to come up in this topic.

I am throughly disappointed.
8. (Original post by serrated_colon)
I was expecting the Riemann Hypothesis to come up in this topic.

I am throughly disappointed.
Yeah I thought that too before I clicked on it (or some other Millennium problem).
9. (Original post by tanakataku7)
That's not what i said, I said every number which isn't a multiple of 3 will not have sum digits with a multiple of 3.
I know, but you didn't prove it! You proved that every number which is a multiple of 3 will have digit sum a multiple of 3, you didn't prove the converse. It's not hard to prove (in fact, you might even think it's obvious from here - it kind of is!), but strictly speaking, you haven't proved it.
10. (Original post by generalebriety)
I know, but you didn't prove it! You proved that every number which is a multiple of 3 will have digit sum a multiple of 3, you didn't prove the converse. It's not hard to prove (in fact, you might even think it's obvious from here - it kind of is!), but strictly speaking, you haven't proved it.
Ok, i don't understand what i've done wrong, but i'm guessing you've attained a calibre of an experienced and capable mathematician. So i dismiss my prove is invalid. I don't understand why, but thnx......... can you explain plz? i'm dumb........
11. (Original post by generalebriety)
I know, but you didn't prove it! You proved that every number which is a multiple of 3 will have digit sum a multiple of 3, you didn't prove the converse. It's not hard to prove (in fact, you might even think it's obvious from here - it kind of is!), but strictly speaking, you haven't proved it.
Ok, i don't understand what i've done wrong, but i'm guessing you've attained a calibre of an experienced and capable mathematician. So i dismiss my proof is invalid. I don't understand why, but thnx......... can you explain plz? i'm dumb........
12. (Original post by tanakataku7)
Ok, i don't understand what i've done wrong, but i'm guessing you've attained a calibre of an experienced and capable mathematician. So i dismiss my proof is invalid. I don't understand why, but thnx......... can you explain plz? i'm dumb........
No, your proof was actually very good (and led to some interesting ideas, in particular where you stated that adding 9 was the same as adding 1 in the tens column and subtracting 1 in the units column - have you ever heard of "modular arithmetic"?) - probably not entirely watertight, but not far off.

My complaint is more general. Take this as an example. It is quite easy to prove the following statement:

1. "If a number is prime (with a and b integers greater than 1), then b is prime and a = 2."

What this doesn't prove is the converse statement (a kind of opposite), which can be expressed in two equivalent ways:

2a. "If is not prime, then it is not true that b is prime and a = 2."
2b. "If b is prime and a = 2, then is prime."

In fact, the converse isn't true! Indeed, if we set a = 2 and b = 11 (which is prime), then 2^11 - 1 = 2047 isn't prime (it's 23 * 89). So a statement and its converse are not always necessarily related (though of course sometimes they are). Now, how does this relate to your problem? You proved the statement:

3. "If a number x is divisible by 3, then the digit sum of x is divisible by 3."

but you did not prove:

4a. "If x is not divisible by 3, then the digit sum of x is not divisible by 3."
4b. "If the digit sum of x is divisible by 3, then x is divisible by 3."

In this case, the statement and its converse are both true (but certainly not in my example when I swapped "3" for "6"), but as you can hopefully gather from my primes example, they both need separate proof. (Incidentally, primes of the form a^b - 1, or equivalently 2^(prime) - 1, are called Mersenne primes.)
13. (Original post by generalebriety)
...
Cracking explanation Grommit!
14. (Original post by ibysaiyan)
Great.. and for once i wanted to plant in my mathematica seed.....
is that an innuendo?
15. (Original post by Blu3j4yw4y)
I get why it works, but I don't get how you would prove it with proper mathematical formula.

Essentially each digit is a measure of how far it is above a multiple of 3.

E.G. 10 is one unit away from a multiple of three (9).
20 is two units away from a multiple of three (18).
30 is three units away from a multiple of three (27).
40 is four units away from a multiple of three (36).
50 is five units away from a multiple of three (45).
60 is six units away from a multiple of three (54).

etc...

This works as you go up by tens too

100 is one unit away from a multiple of three (99).
200 is two units away from a multiple of three (198).
300 is three units away from a multiple of three (297).
etc..

1000 is one unit away from a multiple of three (999).
2000 is two units away from a multiple of three (1998).
3000 is three units away from a multiple of three (2997).

So, essentially. Each digital can be taken as a measure of how far the whole number is away from a multiple of three.

E.g. take 4285

(4 units away from a multiple of three) + (2 units away from a multiple of three) + (8 units away from a multiple of three) + (5 units away from a multiple of three)

=19

Therefore we can deduce that 4285 is 19 digits away from a multiple of three (4266, of course) therefore, as this 19 unit difference is not divisible by three, 4285 itself cannot be a multiple of three

Another example: 4575

(4 units away from a multiple of three) + (5 units away from a multiple of three) + (7 units away from a multiple of three) + (5 units away from a multiple of three)

= 21

This means 4575 is 21 units away from a multiple of three (4554) and as the difference itself is also dividible by three we know 4575 must be a multiple of three. (Adding two multiples of any given number will always give you another multiple).

I don't know how to write a mathematical proof, but that's why.
Honestly, why did you take the time out of your life to write this?
16. (Original post by Blu3j4yw4y)
Prelims in a couple of days. It means I can pretend that I'm doing something math-y and preparational
Fair enough
17. (Original post by generalebriety)
No, your proof was actually very good (and led to some interesting ideas, in particular where you stated that adding 9 was the same as adding 1 in the tens column and subtracting 1 in the units column - have you ever heard of "modular arithmetic"?) - probably not entirely watertight, but not far off.

My complaint is more general. Take this as an example. It is quite easy to prove the following statement:

1. "If a number is prime (with a and b integers greater than 1), then b is prime and a = 2."

What this doesn't prove is the converse statement (a kind of opposite), which can be expressed in two equivalent ways:

2a. "If is not prime, then it is not true that b is prime and a = 2."
2b. "If b is prime and a = 2, then is prime."

In fact, the converse isn't true! Indeed, if we set a = 2 and b = 11 (which is prime), then 2^11 - 1 = 2047 isn't prime (it's 23 * 89). So a statement and its converse are not always necessarily related (though of course sometimes they are). Now, how does this relate to your problem? You proved the statement:

3. "If a number x is divisible by 3, then the digit sum of x is divisible by 3."

but you did not prove:

4a. "If x is not divisible by 3, then the digit sum of x is not divisible by 3."
4b. "If the digit sum of x is divisible by 3, then x is divisible by 3."

In this case, the statement and its converse are both true (but certainly not in my example when I swapped "3" for "6"), but as you can hopefully gather from my primes example, they both need separate proof. (Incidentally, primes of the form a^b - 1, or equivalently 2^(prime) - 1, are called Mersenne primes.)
Ah, thank you, i now understand. I must prove the converse for the conjecture to be proved. erm, i'm not yet familiar with odular arithmetic as i'm a year 10 gcse student, but i think i get the jist of what you've said. I must say, you're a very concise and coherent mathematician, thanks mate.
18. (Original post by tanakataku7)
Ah, thank you, i now understand. I must prove the converse for the conjecture to be proved.
Yep. Actually, from what you've done, it doesn't take long to prove the converse. (Any number m that isn't divisible by 3 is either 3n+1 or 3n-1 for some n - check a few cases and notice that, if 3n has digit sum a multiple of 3, then 3n+1 or 3n-1 will not have digit sum a multiple of 3. Fiddly, but not "hard".)

(Original post by tanakataku7)
erm, i'm not yet familiar with odular arithmetic as i'm a year 10 gcse student
The GCSE/A-level syllabus won't teach you it, I'm afraid. It's a very interesting (and very accessible) part of number theory - you might want to look into it at some point if you're interested. Here's a couple of links, the first rather simplistic and the second rather advanced, that eventually lead up to solving this problem using modular ("clock") arithmetic: [1], [2] - and of course, although it might take you an hour or two to get your head round this solution, you should see it from the point of view of someone who already knows a bit about modular arithmetic. Once you're armed with modular arithmetic, the problem becomes really easy - in fact, I solved it myself in half a line earlier in this thread.

(Original post by tanakataku7)
but i think i get the jist of what you've said. I must say, you're a very concise and coherent mathematician, thanks mate.
No problem.
19. (Original post by Mr M)
Cracking explanation Grommit!
20. (Original post by generalebriety)
The GCSE/A-level syllabus won't teach you it, I'm afraid. It's a very interesting (and very accessible) part of number theory - you might want to look into it at some point if you're interested. Here's a couple of links, the first rather simplistic and the second rather advanced, that eventually lead up to solving this problem using modular [strike]("clock")[/strike] arithmetic: [1], [2] - and of course, although it might take you an hour or two to get your head round this solution, you should see it from the point of view of someone who already knows a bit about modular arithmetic. Once you're armed with modular arithmetic, the problem becomes really easy - in fact, I solved it myself in half a line earlier in this thread.
Sorry, but modular arithmetic is not a clock. The clock analogy is at best weak. Also, lol modular is not a hard word, so why even mention clock. Sorry, but lol I read through a book called music of the primes and yeah had to read clock arithmetic and quantum drum a thousand times.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 14, 2010
Today on TSR

### Took GCSEs this summer?

Fill in our short survey for Amazon vouchers!

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams