The Student Room Group

Scroll to see replies

Reply 1
love2learn7
prove that 801, 279, 386, 104 (thats one number) cant be written as the sum of 3 cubes

any ideas?


Write it out as a product of prime factors?
(Eurgh, that so far gives me 23 x 100159923263.... anyone got a better idea?)


love danniella
Reply 2
Cube numbers (modulo 9) can only be 1,8,0 and follow this pattern:

1 cubed is 1
2 cubed is 8
3 cubed is 0
4 cubed is 1
5 cubed is 8
6 cubed is 0

(and so it goes on)

Therefore the sum of 3 cube numbers must be (modulo 9) 0,1,2,3,6,7,8

801,279,386,104 (mod 9)=4 so it can't be the sum of 3 cubes
Reply 3
I'm probably being very stupid, but how do you work out numbers of that sort of size in mod 9 (or mod whatever)? I know you can just type it into a caluator and divide by nine (giving a result with a recurring 4 on the end), but is there any way you can do it without using a calculator?
Well its difficult but for mod 9 you could use the divisibilty rule for 9, which is, if the sum of the digits of a number is divisible by 9 then so is the number itself. In this case 801,279,386,104 gives 8+0+1+2+7+9+3+8+6+1+0+4=49 so this number isnt divisible by 9 but 801,279,386,100 is divisible by 9 (as the digits sum up to 45 which is divisible by 9). If you split the number 801,279,386,104 into 801,279,386,100 + 4 u can clearly see that 801,279,386,104 leaves remainder 4 when divided by 9. Hope that helps
Reply 5
I'm probably being very stupid, but how do you work out numbers of that sort of size in mod 9 (or mod whatever)? I know you can just type it into a caluator and divide by nine (giving a result with a recurring 4 on the end), but is there any way you can do it without using a calculator?


mod 2 - obvious

mod 3 - sum digits (e.g. 1,231 -> 1+2+3+1 = 7), the result is the same mod 3 as the original number -- do this multiple times for really big numbers

mod 4 - last two digits same mod 4 as whole number (e.g. 3249723476 -> 76 = 0 mod 4 so whole number = 0 mod 4)

mod 5 - obvious

mod 6 - work out mod 2 and mod 3, then find the number between 0-5 with the same two values

mod 7 - ?

mod 8 - last three digits same mod 8 as whole number (the pattern with 4 and 8 continues, so take the last 4 digits for mod 16, 5 for mod 32, n for mod 2^n etc.)

mod 9 - sum digits like in mod 3 test, result is same mod 9 as whole number, repeat if necessary

mod 10 - obvious

mod 11 - sum alternate sets of digits (e.g. -> 31234 -> 3+2+4 and 1+3 = 9 and 4) then take the one NOT containing the last digit from the one containing the last digit ('units' digit), (e.g. 9-4 = 5 mod 11). This is the same mod 11 as the whole number.
Speleo: what about the good old process of long division? :rolleyes:

What I do with stupidly long numbers is just knock out obvious factors. Say if I wanted to check that 436243521563 was divisible by 7 I'd just pick multiples of 7 that I spotted and knock them out:
436243521563 (35 divides by 7)
436240021563 (21 divides by 7)
436240000563 (43 = 1 mod 7)
016240000563 (62 = 6 mod 7)
010640000563 (64 = 1 mod 7)
010010000563 (10 = 3 mod 7)
003003000563 (56 divides by 7)
003003000003 (30 = 2 mod 7)
000200200003 (20 = 6 mod 7)
000060060003 (60 = 4 mod 7)
000004004003 (40 = 5 mod 7)
000000500503 (and so on...)
000000010013
000000003013
000000000213
000000000003

So 436243521563 = 3 mod 7.

Looks really long written down but can be really fast and done in one or two lines with a bit of practice, and works for any divisor. Saves the hassle of "how many times does 108 go into 19?" and all that when all you're interested in is the remainder.

(This method works because you're always removing multiples of 7, which are equivalent to 0 mod 7. For example, in the first line, I subtracted 3500000.)

This can also be very nice for something like 11. Working entirely from left to right (bad practice, but it's easier to show :p:):
290573486
070573486
004573486
000173486
000063486
000008486
000000786
000000016
000000005

290573486 = 5 mod 11.
Reply 7
Nice method :yy:


Speleo: what about the good old process of long division?

I can't remember how to do long division :redface:
Speleo
I can't remember how to do long division :redface:

Not a huge problem. I must admit, my arithmetic has got worse at about the same rate my maths has got better over the last 5 years. :biggrin: I know how to do division (and multiplication), I just generally can't. :p:
Reply 9
Thanks. I haven't actually got onto modular arithmetic yet at school (or even A level maths), but I like to learn this sort of stuff anyway (even if I can have trouble understanding concepts fully because I haven't done all the work you are expected to have done first).
Speleo
I can't remember how to do long division

I don't think I was ever taught it. I tried learning algebraic long division a couple of months back though, so I have a rough idea of the procedure (though no understanding unfortunately) after reading the wikipedia article on algebraic long division.
sebbie
Cube numbers (modulo 9) can only be 1,8,0 and follow this pattern:

1 cubed is 1
2 cubed is 8
3 cubed is 0
4 cubed is 1
5 cubed is 8
6 cubed is 0

(and so it goes on)

Therefore the sum of 3 cube numbers must be (modulo 9) 0,1,2,3,6,7,8

801,279,386,104 (mod 9)=4 so it can't be the sum of 3 cubes

Nice method. Was trying modulo arithmetic myself before but I thought there must be a more elegant solution than that... still, it's short. :smile:
Reply 11
Not a huge problem. I must admit, my arithmetic has got worse at about the same rate my maths has got better over the last 5 years. I know how to do division (and multiplication), I just generally can't.

I found that I couldn't do subtraction (1.0000000 - 0.9684735 or something) a couple of months back O_O.


I don't think I was ever taught it. I tried learning algebraic long division a couple of months back though, so I have a rough idea of the procedure (though no understanding unfortunately) after reading the wikipedia article on algebraic long division.

I can't do that either >_<. The method I use is:
x2+5x+9x2+3x+5=x2+3x+2x+5+4x2+3x+5=1+2x+4x2+3x+5\frac{x^2 + 5x + 9}{x^2 + 3x + 5} = \frac{x^2 + 3x + 2x + 5 + 4}{x^2 + 3x + 5} = 1 + \frac{2x + 4}{x^2 + 3x + 5}
etc. etc. which may or may not be easier :/

Woo, first time I've ever used tex :biggrin:
harr
Thanks. I haven't actually got onto modular arithmetic yet at school (or even A level maths), but I like to learn this sort of stuff anyway (even if I can have trouble understanding concepts fully because I haven't done all the work you are expected to have done first).

Modular arithmetic isn't on the A-level syllabus, I don't think.

harr
I don't think I was ever taught it. I tried learning algebraic long division a couple of months back though, so I have a rough idea of the procedure (though no understanding unfortunately) after reading the wikipedia article on algebraic long division.

Long division, and polynomial long division, use exactly the same method as the one I used to reduce that long number by multiples of 11 in a previous post. You just keep a note of the numbers you've multiplied 11 by, and add them all up at the end. :p:
Reply 13
generalebriety
Nice method. Was trying modulo arithmetic myself before but I thought there must be a more elegant solution than that... still, it's short. :smile:


well i haven't proved that cube numbers only take the form 0,1,8 (mod 9)... If we assume that's true then what I've written is right, however I'm not sure how to prove that all cube numbers are of the form 0,1,8 mod 9 but im sure someone will be able to prove that....
Speleo
I found that I couldn't do subtraction (1.0000000 - 0.9684735 or something) a couple of months back O_O.

0.0315265. :smile:

I have a very strange method of subtracting things from powers of 10. It helps me, but it's extraordinarily illogical because it just involves subtracting things from 9 instead. :confused: So I won't go into the details... I'll just confuse myself.
sebbie
well i haven't proved that cube numbers only take the form 0,1,8 (mod 9)... If we assume that's true then what I've written is right, however I'm not sure how to prove that all cube numbers are of the form 0,1,8 mod 9 but im sure someone will be able to prove that....

Let n^3 = 1 (mod 9), that is n = 9p + 1. (This is true for n = 1.) Assume true for n = k. Proceeding by induction,

k^3 = 9p+1
(k+3)^3 = k^3 + 3k^2*3 + 3k*3^2 + 27 = k^3 + 9(k^2 + 3k + 3) = 9(p + k^2 + 3k + 3) + 1, which is in the form 9p+1. So if n=1 is true, then the cases where n=4, n=7, n=10, n=13 etc. are also true.

Exactly the same for 8 and 0, with n = 9p+8 and n = 9p respectively. The constant just 'comes off at the end' as in this one. Then show true for n=2 and n=3 respectively.
Reply 16
generalebriety
Modular arithmetic isn't on the A-level syllabus, I don't think.

I'll have to wait until university then.
Long division, and polynomial long division, use exactly the same method as the one I used to reduce that long number by multiples of 11 in a previous post. You just keep a note of the numbers you've multiplied 11 by, and add them all up at the end. :p:

Thanks. I always thought that long division is presented in an awkward way, the way you do it looks simpler (even if it is the same process).
harr
I'll have to wait until university then.

I don't think it really gets taught, you know. You're just kind of expected to understand it. It might be formally defined at university (in fact, probably will), but it's better to learn its uses now. It's not difficult, follows most of the same rules as standard arithmetic.

harr
Thanks. I always thought that long division is presented in an awkward way, the way you do it looks simpler (even if it is the same process).

Yeah, the only difference between my process and the standard process is that mine takes up more space. The other process has the disadvantage of being bloody complicated.
generalebriety
Let n^3 = 1 (mod 9), that is n = 9p + 1. (This is true for n = 1.) Assume true for n = k. Proceeding by induction,

k^3 = 9p+1
(k+3)^3 = k^3 + 3k^2*3 + 3k*3^2 + 27 = k^3 + 9(k^2 + 3k + 3) = 9(p + k^2 + 3k + 3) + 1, which is in the form 9p+1. So if n=1 is true, then the cases where n=4, n=7, n=10, n=13 etc. are also true.

Exactly the same for 8 and 0, with n = 9p+8 and n = 9p respectively. The constant just 'comes off at the end' as in this one. Then show true for n=2 and n=3 respectively.

... or don't bother with induction. Just notice that all numbers are of the form 3k, 3k+1 or 3k-1, and then work out their cubes mod 9. Voila.
FWoodhouse
... or don't bother with induction. Just notice that all numbers are of the form 3k, 3k+1 or 3k-1, and then work out their cubes mod 9. Voila.

...or you can be clever and do it FWoodhouse's way. :p: