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$?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ Did you do it the hard way first? $\endgroup$– pjs36Jun 5, 2016 at 3:44
-
$\begingroup$ This question has nothing to do with factorials. Please use tags accordingly $\endgroup$– EmreJun 5, 2016 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$– fleabloodJun 5, 2016 at 4:56
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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$.
-
$\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$ Jun 5, 2016 at 4:31
$\begingroup$
$\endgroup$
answered Jun 5, 2016 at 3:44
$\begingroup$
$\endgroup$
0
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}$$
