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

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$?

• Did you do it the hard way first? Jun 5 '16 at 3:44
• This question has nothing to do with factorials. Please use tags accordingly
– Emre
Jun 5 '16 at 3:46
• 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. Jun 5 '16 at 4:56

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

• @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$. Jun 5 '16 at 4:31

HINT:

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

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

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}$$