It's still 2014!

Algebra Level 5

Let α \alpha and β \beta be the roots of x 2 6 x 2 = 0 x^2-6x-2=0 , with α > β \alpha >\beta . If a n = α n β n a_n=\alpha^n-\beta^n for n 1 n\geq 1 , then k = a 10 2 a 8 2 a 9 k=\dfrac{a_{10}-2a_8}{2a_9} Then find the remainder when k 942 k^{942} is divided by 2014 2014 .


Note

  • Something amazing happens when you add 1000 to the answer


The answer is 729.

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.

5 solutions

U Z
Nov 6, 2014

Let α = c , β = d \alpha = c , \beta = d

c 2 6 c 2 = 0 c^{2} - 6c - 2 =0

c 10 6 c 9 2 c 8 = 0 c^{10} - 6c^{9} - 2c^{8} = 0

similarly,

d 10 6 d 9 2 d 8 = 0 d^{10} - 6d^{9} - 2d^{8} = 0

Subtracting,

c 10 d 10 6 ( c 9 b 9 ) 2 ( c 8 d 8 ) = 0 c^{10} - d^{10} - 6( c^{9} - b^{9}) - 2(c^{8} - d^{8}) = 0

a 10 2 a 8 = 6 a 9 a_{10} - 2a_{8} = 6a_{9}

a 10 2 a 8 2 a 9 = 3 \frac{a_{10} - 2a_{8}}{2a_{9}} = 3

3 942 = 2014 k + 729 3^{942} = 2014k + 729

hence remainder is 729

Adding 1000 1000 in the answer will give 1729 1729 called Ramanujan Number. It is the smallest natural number which can be written as the sum of cubes of two distinct un-ordered pairs. 1729 = 1729= { 1 2 3 + 1 3 1 0 3 + 9 3 \begin{cases} \\ 12^3+1^3 \\ 10^3+9^3 \end{cases}

Sandeep Bhardwaj - 6 years, 7 months ago

Log in to reply

Really good , thank you

U Z - 6 years, 7 months ago

To find the remainder, we can apply Euler's theorem. Since 2014 = 2 × 19 × 53 2014=2\times 19\times 53 we have ϕ ( 2014 ) = 936 \phi(2014)=936 . Hence 3 942 3 6 = 729 ( m o d 2014 ) 3^{942}\equiv 3^6=729\pmod{2014} .

Jubayer Nirjhor - 6 years, 7 months ago

Log in to reply

Yeah did the same!

Kartik Sharma - 6 years, 7 months ago

Thanks @Jubayer Nirjhor. Actually I did not know the factors of 1007.

souvik paul - 6 years, 7 months ago

Can you please write a solution for calculating the remainder.

souvik paul - 6 years, 7 months ago

Log in to reply

I asked @Aneesh kundu the same and he replied the remainder would be 1 . No problem i was able to get but was unable to find remainder so its okay.

Gautam Sharma - 6 years, 7 months ago

Log in to reply

Bro don't lose the spirit , i know your are a genius.

Try this one , you also @souvik paul

Find the remainder when 169 0 2608 + 260 8 1690 1690^{2608} + 2608^{1690} is divided by 7

U Z - 6 years, 7 months ago

Log in to reply

@U Z @megh choksi is your question's answer 0????

A Former Brilliant Member - 6 years, 7 months ago

Log in to reply

@A Former Brilliant Member Good try ,the answer is 1

U Z - 6 years, 7 months ago

Sorry but I actually mistook ϕ ( 2014 ) \phi(2014) to be 942 instead of 936. I've edited it now. Sorry if u lost any points because of me.

Aneesh Kundu - 6 years, 7 months ago

Log in to reply

@Aneesh Kundu No problem because i was unable to get the remainder. Its okay .Dont be sorry.

Gautam Sharma - 6 years, 7 months ago

Truly amazing! You're Awesome, I'm awestruck, I bashed it all.

Satvik Golechha - 6 years, 7 months ago

Use Newton's sum for simplifying a 10 2 a 8 2 a 9 \frac{{a}_{10} - 2{a}_{8}}{2{a}_{9}} into

a 9 ( a ) + 2 a 8 2 a 8 2 a 9 \frac{{a}_{9}(a) + 2{a}_{8} - 2{a}_{8}}{2{a}_{9}}

= a ( a 9 2 a 9 \frac{a({a}_{9}}{2{a}_{9}}

= 3

Kartik Sharma - 6 years, 7 months ago

Log in to reply

What is newton sums? @Kartik Sharma

U Z - 6 years, 7 months ago

Log in to reply

a n + b n = ( a + b ) ( a n 1 + b n 1 ) a b ( a n 2 + b n 2 ) {a}^{n} + {b}^{n} = (a+b)({a}^{n-1} + {b}^{n-1}) - ab({a}^{n-2} + {b}^{n-2})

Kartik Sharma - 6 years, 7 months ago

Crap, forgot the coefficient of 2 in the denominator and got 334. D:

Finn Hulse - 6 years, 7 months ago

Just saying, the 'note' is a pure spoiler to the question. One may simply guess the answer. I suggest you to remove it.

Akshat Jain - 6 years ago

I solved it using newton sum and using identities. Your solution is awesome.

Dev Sharma - 5 years, 7 months ago

Awesome!!! Best solution.

Anupam Nayak - 5 years, 5 months ago
Dhruva Patil
Nov 8, 2014

Since α \alpha and β \beta are roots of the equation: α β = 2 α + β = 6 \alpha \beta =-2\\ \alpha +\beta =6

Now, multiplying and dividing by 3 and substituting the above values in the given expression, we get: k = ( ( α 10 β 10 ) 2 ( α 8 β 8 ) ) 2 ( α 9 β 9 ) × 3 3 = 3 ( α 10 β 10 + α β ( α 8 β 8 ) ) ( α + β ) ( α 9 β 9 ) = 3 ( α 10 β 10 + α 9 β α β 9 ) ( α 10 β 10 + α 9 β α β 9 ) = 3 k=\frac { ({ (\alpha }^{ 10 }-{ \beta }^{ 10 })-2({ \alpha }^{ 8 }{ -\beta }^{ 8 })) }{ 2({ \alpha }^{ 9 }{ -\beta }^{ 9 }) } \times \frac { 3 }{ 3 } =\frac { 3({ \alpha }^{ 10 }-{ \beta }^{ 10 }+\alpha \beta ({ \alpha }^{ 8 }{ -\beta }^{ 8 })) }{ (\alpha +\beta )({ \alpha }^{ 9 }{ -\beta }^{ 9 }) } =\frac { 3({ \alpha }^{ 10 }-{ \beta }^{ 10 }+{ \alpha }^{ 9 }\beta { -\alpha \beta }^{ 9 }) }{ ({ \alpha }^{ 10 }-{ \beta }^{ 10 }+{ \alpha }^{ 9 }\beta { -\alpha \beta }^{ 9 }) } =3

Now, we can find the remainder of [ 3 942 2014 ] \left[ \frac { { 3 }^{ 942 } }{ 2014 } \right] (Which I guessed using the note.)

Answer: 729 \boxed{729}

George Darroch
Nov 23, 2014

The fact that a(n)=alpha^n-beta^n implies that a difference equation can be formed.

The following difference equation is formed a(n+2)=6a(n+1)-2a(n).

Clearly a(0)=0.

As alpha=3+sqrt(11) and beta=3-sqrt(11), a(1)=2sqrt(11).

Therefore a(10) and a(8) and a(9) can be generated iteratively.

Giving a(10)=30489792sqrt(11), a(8)=19152sqrt(11), a(9)=4826912sqrt(11).

Therefore, cancelling the sqrt(11)'s, k=(30489792-2 19152)/(2 4826912)=3.

As 3 and 2014 and coprime, Euler's totient theorem can be used. phi(2014)=936.

Therefore k=3^6 mod(11). i.e. The remainder is 3^6=729.

Lu Chee Ket
Jan 6, 2015

(x – 3)^2 = 11

x = 3 +/- Sqrt (11)

p = 3 + Sqrt (11) and q = 3 - Sqrt (11)

a (n) = [3 + Sqrt (11)]^n – [3 - Sqrt (11)]^n for n >= 1

k = [a (10) – 2 a (8)]/ [2 a (9)] = 3

k^ 942 MOD 2014 = ?

3^942 MOD (2 x 19 x 53) = 729? {Calculator}

With 3^67 = 92709463147897837085761925410587

3^ [14 (67) + 4] MOD 2014

= (92709463147897837085761925410587^14 x 81)/ (2 x 19 x 53)

= (92709463147897837085761925410587 x

92709463147897837085761925410587^13 x 81)/ 2014

= (46032504045629511959166795139+641/ 2014) x 92709463147897837085761925410587^13 x 81

--> (641/ 2014) x 92709463147897837085761925410587^13 x 81

--> (641^14/ 2014) x 81

= (410881^7)/ 2014 x 81

--> (25^7)/ 2014 x 81

= 6103515625/ 2014 X 81

= 494384765625/ 2014

--> 729/ 2014

Remainder = 729

Ritvik Arya
Nov 22, 2014

got 3 but stuck to find remainder for a while.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...