Guessing Won't Work-2

Given a number x = 2 48 1 x=2^{48}-1 Let the sum of the factors of x strictly between 5 and 10 be m. Let the remainder when 9999 9 99 , 984 i s d i v i d e d b y m + 1 b e n 99999^{99,984}\:\:is\:\:divided\:\:by\:\:m+1\:\:be\:\:n Then find m+n


The answer is 17.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Jaiveer Shekhawat
Oct 28, 2014

We will be using a simple yet useful identity throughout the problem which is

a 2 a^{2} - b 2 b^{2} = (a+b)(a-b)

2 48 2^{48} - 1

= ( 2 24 2^{24} - 1)( 2 48 2^{48} +1)

=( 2 12 2^{12} - 1)( 2 12 2^{12} +1)( 2 12 2^{12} - 1)( 2 12 2^{12} +1)

=( 2 6 2^{6} - 1)( 2 6 2^{6} +1)( 2 6 2^{6} - 1)( 2 6 2^{6} +1)( 2 6 2^{6} - 1)( 2 6 2^{6} +1)( 2 6 2^{6} - 1)( 2 6 2^{6} +1)

= d d

Therefore, the factors between 5 and 10 are 7 and 9.

⇒ m =16

( 99999 ) 99984 (99999)^{99984} ? \equiv ? (mod 17)

99999 5 \equiv 5 (mod 17)

but according to fermat's little remainder theorem

a p 1 a^{p-1} 1 \equiv 1 (mod p) where p is prime and a is any positive integer...

( 99999 ) 16 (99999)^{16} 1 \equiv 1 (mod 17)

( ( 99999 ) 16 ) 6249 ((99999)^{16})^{6249} 1 \equiv 1 (mod 17)

⇒ n =1

Therefore m+n = 16+1

= 17 \huge{17}

I've reported the problem, and I'll copy the reason here:

2 48 1 = ( 2 24 1 ) ( 2 24 + 1 ) = ( 2 8 1 ) ( 2 16 + 2 8 + 1 ) ( 2 24 + 1 ) = ( 2 2 1 ) ( 2 2 + 1 ) ( 2 4 + 1 ) ( 2 16 + 2 8 + 1 ) ( 2 24 + 1 ) \begin{array}{cl} &2^{48}-1\\ =&(2^{24}-1)(2^{24}+1)\\ =&(2^8-1)(2^{16}+2^8+1)(2^{24}+1)\\ =&(2^2-1)(2^2+1)(2^4+1)(2^{16}+2^8+1)(2^{24}+1) \end{array}

Therefore 5 is also a factor of x, and the answer would be 25. (m=22, n=3)

Kenny Lau - 6 years, 6 months ago

Log in to reply

Thanks, I have updated the question to say "strictly between".

Those who previously answered 25 have been marked correct.

Calvin Lin Staff - 6 years, 6 months ago

An easy but good question!!

jaiveer shekhawat - 6 years, 7 months ago

Log in to reply

For completeness, you should explain why there are no other factors if x between 5 and 10. So far, you have only shown that 7 and 9 are factors.

Calvin Lin Staff - 6 years, 6 months ago

Log in to reply

I thought it is trivial: x is odd.

Kenny Lau - 6 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...