This confuses me!

Find the smallest n n such that 2 n + 1 2^{n+1} \nmid 102 5 1024 1 1025^{1024}-1 .

Notation : ' \nmid ' means "does not divide."


The answer is 20.

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.

4 solutions

Grant Bulaong
May 22, 2016

It would be equivalent to find the largest n n such that 2 n 102 5 1024 1 2^n|1025^{1024}-1 .

We factor the expression as

102 5 1024 1 = ( 1025 1 ) ( 1025 + 1 ) ( 102 5 2 + 1 ) ( 102 5 4 + 1 ) ( 102 5 8 + 1 ) . . . ( 102 5 512 + 1 ) 1025^{1024}-1=(1025-1)(1025+1)(1025^2+1)(1025^4+1)(1025^8+1)...(1025^{512}+1)

The greatest power of 2 2 which divides the first factor is 2 10 2^{10} . Since 1025 = 2 10 + 1 1025=2^{10}+1 , the terms of the expansions within each of the remaining ten factors only contain powers of two, the smallest being 2 2 itself. Thus, the largest power of two which divides 102 5 1024 1 1025^{1024}-1 is 2 10 + 10 = 2 20 . 2^{10+10}=2^{20}.

n = 20 \boxed{n=20}

I would have written a solution using the Exponent Lifting Lemma, but somebody else has already done so. 😏

Nice alternative solution! <3

Manuel Kahayon - 5 years ago

Nice solution, Grant. I upvoted your solution (+1)

Pranshu Gaba - 5 years ago

Note that 1025 = 1024 + 1 1025=1024+1 , then the expression becomes

( 1024 + 1 ) 1024 1 = = k = 0 1023 ( 1024 k ) 1024 1024 k = = 1024 1024 + ( 1024 1 ) 1024 1023 + . . . + ( 1024 1022 ) 1024 2 + ( 1024 1023 ) 1024 { (1024+1) }^{ 1024 }-1=\\= \sum _{ k=0 }^{ 1023 }{ \left( \begin{matrix} 1024 \\ k \end{matrix} \right) { 1024 }^{ 1024-k } } =\\ ={ 1024 }^{ 1024 }+\left( \begin{matrix} 1024 \\ 1 \end{matrix} \right) { 1024 }^{ 1023 }+...+\left( \begin{matrix} 1024 \\ 1022 \end{matrix} \right) { 1024 }^{ 2 }+\left( \begin{matrix} 1024 \\ 1023 \end{matrix} \right) 1024

Note that every term, except the last one, is divisible by 2 21 { 2 }^{ 21 } , as the powers of 1024 = 2 10 1024={ 2 }^{ 10} are increasing from right to left. Thus, the smallest n n such that 2 n + 1 102 5 1024 1 2^{n+1}\nmid 1025^{1024}-1 is 20 20 , because 2 21 1024 2 { 2 }^{ 21 }\nmid { 1024 }^{ 2 } , which is the last term.

Perfect solution+1!

Rishabh Tiwari - 5 years ago

Dont you think its overrated

Kaustubh Miglani - 5 years ago

Log in to reply

Haan bhai sahi keh rha hai.

Kushagra Sahni - 5 years ago

The problem? Of course, I think that it is a level 4, at most...

Mateo Matijasevick - 5 years ago
Manuel Kahayon
May 22, 2016

Let V 2 ( x ) V_2(x) denote the largest power of 2 which divides x x .

Since gcd ( 1025 , 2 ) = 1 \gcd(1025,2) =1 and gcd ( 1 , 2 ) = 1 \gcd(1,2) = 1 , we can use Lifting the Exponent Lemma here.

By lifting the exponent lemma,

V 2 ( 102 5 1024 1 ) = V 2 ( 102 5 1024 1 1024 ) = V 2 ( 1025 1 ) + V 2 ( 1025 + 1 ) + V 2 ( 1024 ) 1 V_2(1025^{1024}-1) = V_2(1025^{1024}-1^{1024}) = V_2(1025-1)+V_2(1025+1)+V_2(1024)-1

Since V 2 ( 1024 ) = 10 V_2(1024) = 10 , V 2 ( 1026 ) = 1 V_2(1026) = 1 , V 2 ( 1025 1 ) + V 2 ( 1025 + 1 ) + V 2 ( 1024 ) 1 = 20 V_2(1025-1)+V_2(1025+1)+V_2(1024)-1 = 20

Therefore, 2 20 102 5 1024 1 2^{20} \mid 1025^{1024}-1 , 2 21 102 5 1024 1 2^{21} \nmid 1025^{1024}-1

So, n + 1 = 21 n+1 = 21 , n = 20 n = \boxed{20}

Did the exact same

Aditya Kumar - 5 years ago
Md Hasib
May 23, 2016

1025^1 = 1 (mod 2^10) , 1025^2 = 1 (mod 2^11) , 1025^4 = 1 (mod 2^12) , 1025^8 = 1 (mod 2^13) , .
There is a pattern look at the powers of 1025 and the powers of 2
The pattern is 2^0 = 2^10 , 2^1 = 2^11 , . 2^2 = 2^12 ,

1025^1024 =1 (mod 2^20) ,

that means (1025^1024)-1 is divisible by 2^20
2^21 is our answer and so the value of n is 20

But how do you show that the minimum value of n + 1 n+1 is 21 21 ?

Ralph Macarasig - 5 years ago

Log in to reply

The value of (n+1) must be a positive integer , all the natural powers of 2 divide the above , the highest power of 2 which divides the above is 20 ,so the next natural number must be the desired one

Md Hasib - 5 years ago

Log in to reply

Okay. I see the pattern. But it's better if you can prove that one. :)

Ralph Macarasig - 5 years ago

Log in to reply

@Ralph Macarasig Thanks for the suggestion . At first, i thought no one would understand but now look at you and also conjectures help a lot .Do i need to prove all of them ? i am just a lazy bum :D

Md Hasib - 5 years ago

Log in to reply

@Md Hasib You don't need to prove all of them one by one. Proving the general case would do.

Ralph Macarasig - 5 years ago

Log in to reply

@Ralph Macarasig Thanks i will try to do so :)

Md Hasib - 5 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...