3
$\begingroup$

I know $2^{10}=1024$ and $2^6=64$, but it seems they are not very helpful in solving this problem. There must be a trick to solve the problem in an easy way.

What is the sum of the prime factors of $2^{16}-1$?

$\endgroup$
3
  • 3
    $\begingroup$ Did you do it the hard way first? $\endgroup$
    – pjs36
    Jun 5 '16 at 3:44
  • $\begingroup$ This question has nothing to do with factorials. Please use tags accordingly $\endgroup$
    – Emre
    Jun 5 '16 at 3:46
  • $\begingroup$ The trick is you can factor. $2^{16}-1=(2^8+1)(2^8-1)=...=(2^8+1)(2^4+1)(2^2+1)(2+1)(2-1)=257*17*5*3$ So it's a matter of factoring any of those that aren't prime. Thus are all prime so the answer is 257+17+5+3=282. It's a question where the process and logic is more interesting than the result. $\endgroup$
    – fleablood
    Jun 5 '16 at 4:56
7
$\begingroup$

Using $a^2-1=(a-1)(a+1)$ we have:

$$2^{16}-1=(2^8-1)(2^8+1)=(2^4-1)(2^4+1)(2^8+1)=15\cdot 17\cdot 257=3\cdot 5\cdot 17\cdot 257$$

So, the answer is $3+5+17+257=282$.

$\endgroup$
1
  • $\begingroup$ @learning To see that $257$ is prime (and hence can be factored further) note that for a number to end in a $7$ it would need to have factors ending in $1$ and $7$ or ending in $3$ and $9$. So you only need to check $11\times17\neq257$ and $13\times19\neq257$. $\endgroup$
    – Ian Miller
    Jun 5 '16 at 4:31
3
$\begingroup$

HINT:

$$a^{2^{n+1}}-1=(a^{2^n}+1)(a^{2^n}-1)$$

as $$(b^m)^n=b^{mn}$$

See Power of Power

$\endgroup$
-3
$\begingroup$

Every student should know the powers of two up to $2^{20}$ like the back of his/her hand, or in the case of a student with no hands, like some other familiar body part that would serve my rhetorical purpose.

Therefore we have $$2^{16}-1=65536-1 = 65535$$

Now any schoolchild can tell you that the semiprime $771$ is a factor: $$65535= 771\cdot 85$$

The rest is trivial:

$$65535=771\cdot 85 = 3 \cdot 5 \cdot 17 \cdot 257$$

Get a stray toddler to do the addition for you, to arrive at the final answer of

$$\boxed{282}$$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.