Minimum value 1

Find the minimum positive integer value of n n such that 2 2014 { 2 }^{ 2014 } divides 2013 n 1. { 2013 }^{ n }-1.

2 2012 { 2 }^{ 2012 } 2 2013 { 2 }^{ 2013 } 3 2012 { 3 }^{ 2012 } 3 2014 { 3 }^{ 2014 }

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.

2 solutions

Linkin Duck
Apr 2, 2017

Let n = 2 k × t n={ 2 }^{ k }\times t , k , t k,t are whole numbers, and t t is odd.

We have 2013 n 1 = ( 2013 2 k ) t 1 = ( 2013 2 k 1 ) [ ( 2013 2 k ) t 1 + . . . + 2013 2 k + 1 ] { 2013 }^{ n }-1={ { \left( { 2013 }^{ 2^{ k } } \right) }^{ t }-1=\left( { 2013 }^{ 2^{ k } }-1 \right) }\left[ { \left( { 2013 }^{ 2^{ k } } \right) }^{ t-1 }+...+{ 2013 }^{ 2^{ k } }+1 \right]

Since t t is odd, 2013 n 1 2 2014 2013 2 k 1 2 2014 { 2013 }^{ n }-1\vdots { 2 }^{ 2014 }\Longleftrightarrow { { 2013 }^{ 2 } }^{ k }-1\vdots { 2 }^{ 2014 }

Also, 2013 2 k 1 = ( 2013 2 1 ) ( 2013 2 + 1 ) ( 2013 4 + 1 ) . . . ( 2013 2 k 1 + 1 ) { { 2013 }^{ 2 } }^{ k }-1=\left( { 2013 }^{ 2 }-1 \right) \left( { 2013 }^{ 2 }+1 \right) \left( { 2013 }^{ 4 }+1 \right) ...\left( { { 2013 }^{ 2 } }^{ k-1 }+1 \right)

Since 2013 1 ( m o d 4 ) 2013 2 i + 1 2 ( m o d 4 ) 2013\equiv 1\left( mod4 \right) \Longrightarrow { { 2013 }^{ 2 } }^{ i }+1\equiv 2\left( mod4 \right)

Hence 2013 n 2 2014 ( k 1 ) + 3 2014 { { 2013 }^{ n } }\vdots { 2 }^{ 2014 }\Longleftrightarrow \left( k-1 \right) +3\ge 2014

Therefore, the minimum value of n n is 2 2012 \boxed { { 2 }^{ 2012 } }

Calvin Lin Staff
Apr 1, 2017

This problem looks scary, but it's almost immediate once we write it out. Let 2013 = 4 k + 1 2013 = 4k+1 , where k k is odd. We want

2 2014 ( 4 k + 1 ) n 1 2^{2014} \mid ( 4k+1) ^ n - 1

By considering the binomial expansion, we have:

2 2014 ( 4 k ) n + ( n n 1 ) ( 4 k ) n 1 + + ( n 2 ) ( 4 k ) 2 + ( n 1 ) ( 4 k ) 1 2 ^ { 2014 } \mid (4k)^n + {n \choose n-1 } (4k)^{n-1} + \ldots + {n\choose 2} (4k)^2 + { n \choose 1} (4k)^1

Observe that since k k is odd, if n n is odd, then the last term is divisible by 4 not 8, while all of the other terms are divisible by 16. Hence, we must have n = 2 n 1 n = 2n_1 .
Again, if n 1 n_1 is odd, then the last term is divisible by 8 not 16, while all of the other terms are divisible by 32. Hence, n 1 = 2 n 2 n_1 = 2 n_2 .
Again, if n 2 n_2 is odd, then the last term is divisible by 16 not 32, while all of the other terms are divisible by 64. Hence n 2 = 2 n 3 n_2 = 2 n_3 .
We can continually repeat this process, until we get "If n 2012 n_{2012} is odd, then the last term is divisible by 2 2014 2 ^ {2014} (but not 2 2015 2^{2015} ). Thus tells us that we must have n = 2 2012 × n 2012 n = 2 ^ { 2012 } \times n_{2012} .


Hence, the smallest positive integer is n = 2 2012 n = 2 ^ { 2012 } .


Note: I decided to present a basic approach to this problem. Yes there are shorter approaches which use higher-power theorems like lifting the exponent .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...