math fun weeee

[wfbberzerker]

I'm working on a project for trig, and i have to solve a problem. its taken from this calender, and i have to solve the problem and explain it to my class. basically, im stumped. could help to explain how to solve this?

Compute the sum of the prime factors of 2^16 - 1

thanks for any help you can give!
-wfbberzerker

 

[GoingUp]

if its prime than the only numbers are 1 and the number

since 2^16 -1 +1 is the sum the answer is compute 2^16

 

[GoingUp]

66536

 

[wfbberzerker]

Originally posted by: Gobadgrs
if its prime than the only numbers are 1 and the number

since 2^16 -1 +1 is the sum the answer is compute 2^16

are you sure that 2^16 - 1 is prime? it said the prime factors.

 

[wfbberzerker]

meh, no one has any ideas?

 

[crypticlogin]

This is one of those problems that's simple if you catch the trick. Afterwards, the answer just jumps at you. Look at the number:
2^16 - 1
Ask yourself why didn't they just say 65535? Does that look special to you in any way?

There's my hint.

 

[wfbberzerker]

so i just find the sum of the factors of 65535?

 

[wfbberzerker]

damn you all and your cryptic clues!

 

[crypticlogin]

so i just find the sum of the factors of 65535?

Well, I guess you could but where's the fun in that? Math "contest" problems almost always have some elegant solution. No elegant solution != fun.

damn you all and your cryptic clues!

I'm evil, yes.


Final Hint:
(a+b)(a-b) = a^2 - b^2

 

[wfbberzerker]

so... really the factors are just 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2 - 1, right? if i just add up all the 2's, i get 32, but how does the 1 figure into the equation?

 

[BA]

so i just find the sum of the factors of 65535?

No, the sum of the PRIME factors.
prime numbers: 2 3 5 7 13 17 19 23 29 31.....

 

[wfbberzerker]

WHY CANT I FIGURE THIS OUT?!

 

[wfbberzerker]

alright i give up, can someone just tell me what to do?

 

[Moonbeam]

You said the factors of 2 to the 16th minus 1 were 2 to the 8th plus one and 2 to the eighth minus 1. Those are two factors, right, so what are they? Does that get you there?

 

[wfbberzerker]

i'm really just not understanding this...

 

Here's what Moonbeam is trying to tell ya: Use the familiar algebraic factoring of a^2 - b^2 = (a+b)(a-b)

So, 2^16 - 1 = (2^8 + 1)(2^8 - 1) = (2^8 + 1)(2^4 + 1) (2^4 - 1) = (2^8 + 1)(2^4 + 1)(2^2 + 1) (2^2 - 1)

You get the gist: You factor it until it can no longer be factored. Then you calculate each factor. You pick out the prime numbers from the factors and then sum up the prime numbers (well, they're all prime numbers, but basically the sum of the distinct numbers). Your answer should be 282.

 

[Moonbeam]

2 to the 8th plus one is 257 a prime number and 2 to the eighth minus 1 is 255 which you can factor yourself. Trust luvly on the sum.

 

[wfbberzerker]

is there any way to prove that 2^8+1 is prime?

EDIT: and 2^4+1 for that matter

 

[wfbberzerker]

i got 282, same as you luvly, but how do i prove that 2^8+1 is prime? in case my teacher asks.

 

[Moonbeam]

It's prime because there's nothing else you can divide into it but 257 and 1. If you don't believe me check out first '2500 primes' on google and you will see it there as the 55th prime not counting 1.

 

[wfbberzerker]

well, thanks everyone for all your help, i think i understand it now.