Find the smallest n such that 2 n + 1 ∤ 1 0 2 5 1 0 2 4 − 1 .
Notation : ' ∤ ' means "does not divide."
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.
Nice alternative solution! <3
Nice solution, Grant. I upvoted your solution (+1)
Note that 1 0 2 5 = 1 0 2 4 + 1 , then the expression becomes
( 1 0 2 4 + 1 ) 1 0 2 4 − 1 = = ∑ k = 0 1 0 2 3 ( 1 0 2 4 k ) 1 0 2 4 1 0 2 4 − k = = 1 0 2 4 1 0 2 4 + ( 1 0 2 4 1 ) 1 0 2 4 1 0 2 3 + . . . + ( 1 0 2 4 1 0 2 2 ) 1 0 2 4 2 + ( 1 0 2 4 1 0 2 3 ) 1 0 2 4
Note that every term, except the last one, is divisible by 2 2 1 , as the powers of 1 0 2 4 = 2 1 0 are increasing from right to left. Thus, the smallest n such that 2 n + 1 ∤ 1 0 2 5 1 0 2 4 − 1 is 2 0 , because 2 2 1 ∤ 1 0 2 4 2 , which is the last term.
Perfect solution+1!
Dont you think its overrated
Log in to reply
Haan bhai sahi keh rha hai.
The problem? Of course, I think that it is a level 4, at most...
Let V 2 ( x ) denote the largest power of 2 which divides x .
Since g cd ( 1 0 2 5 , 2 ) = 1 and g cd ( 1 , 2 ) = 1 , we can use Lifting the Exponent Lemma here.
By lifting the exponent lemma,
V 2 ( 1 0 2 5 1 0 2 4 − 1 ) = V 2 ( 1 0 2 5 1 0 2 4 − 1 1 0 2 4 ) = V 2 ( 1 0 2 5 − 1 ) + V 2 ( 1 0 2 5 + 1 ) + V 2 ( 1 0 2 4 ) − 1
Since V 2 ( 1 0 2 4 ) = 1 0 , V 2 ( 1 0 2 6 ) = 1 , V 2 ( 1 0 2 5 − 1 ) + V 2 ( 1 0 2 5 + 1 ) + V 2 ( 1 0 2 4 ) − 1 = 2 0
Therefore, 2 2 0 ∣ 1 0 2 5 1 0 2 4 − 1 , 2 2 1 ∤ 1 0 2 5 1 0 2 4 − 1
So, n + 1 = 2 1 , n = 2 0
Did the exact same
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 is 2 1 ?
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
Log in to reply
Okay. I see the pattern. But it's better if you can prove that one. :)
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
Log in to reply
@Md Hasib – You don't need to prove all of them one by one. Proving the general case would do.
Problem Loading...
Note Loading...
Set Loading...
It would be equivalent to find the largest n such that 2 n ∣ 1 0 2 5 1 0 2 4 − 1 .
We factor the expression as
1 0 2 5 1 0 2 4 − 1 = ( 1 0 2 5 − 1 ) ( 1 0 2 5 + 1 ) ( 1 0 2 5 2 + 1 ) ( 1 0 2 5 4 + 1 ) ( 1 0 2 5 8 + 1 ) . . . ( 1 0 2 5 5 1 2 + 1 )
The greatest power of 2 which divides the first factor is 2 1 0 . Since 1 0 2 5 = 2 1 0 + 1 , the terms of the expansions within each of the remaining ten factors only contain powers of two, the smallest being 2 itself. Thus, the largest power of two which divides 1 0 2 5 1 0 2 4 − 1 is 2 1 0 + 1 0 = 2 2 0 .
n = 2 0
I would have written a solution using the Exponent Lifting Lemma, but somebody else has already done so. 😏