Expand This?

Let x = 1 + 5 2 x=\displaystyle \frac{1+\sqrt{5}}{2} and

x 6006 = a 1 x + b 1 x^{6006}=a_1x+b_1

x 12355 = a 2 x + b 2 x^{12355}=a_2x+b_2

What is the highest common factor of ( a 1 , b 2 ) (a_1,b_2) ?


The answer is 8.

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

Christopher Boo
Mar 20, 2014

Since x x is the Golden Ratio ,

a 1 = F 6006 a_1=F_{6006}

b 2 = F 12354 b_2=F_{12354}

Then,

gcd ( a 1 , b 2 ) \gcd(a_1,b_2)

= gcd ( F 6006 , F 12354 ) =\gcd(F_{6006},F_{12354})

= F g c d ( 6006 , 12354 ) =F_{gcd(6006,12354)}

= F 6 =F_6

= 8 =8

Wow!... good question.....

Aniket Khaire - 6 years, 5 months ago

Did the same! But I was wondering about the proof of g c d ( F 6006 , F 12354 ) = F g c d ( 6006 , 12354 ) gcd({F}_{6006}, {F}_{12354}) = {F}_{gcd(6006,12354)} because I didn't know that formula until now. So, I formulated one -

F n = x n ( x 5 ) n 5 {F}_{n} = \frac{{x}^{n} - {(x - \sqrt{5})}^{n}}{\sqrt{5}}

Now, we have to find g c d ( F n , F k ) gcd({F}_{n}, {F}_{k}) .

Let x 5 = b , x = a x - \sqrt{5} = b, x = a .

We know that ( a k b k ) ( a n b n ) ({a}^{k} - {b}^{k})|({a}^{n} - {b}^{n}) iff k n k|n .

Hence, proved as now writing the formalities is just trivial.

Kartik Sharma - 6 years, 5 months ago

Log in to reply

A more elementary proof is given here: http://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml

Jared Low - 6 years, 5 months ago
Gandoff Tan
Dec 4, 2019

x = 1 + 5 2 2 x = 1 + 5 2 x 1 = 5 4 x 2 4 x + 1 = 5 4 x 2 4 x = 4 x 2 = x + 1 \begin{aligned} x&=\frac{1+\sqrt5}{2}\\ 2x&=1+\sqrt5\\ 2x-1&=\sqrt5\\ 4x^2-4x+1&=5\\ 4x^2-4x&=4\\ x^2&=x+1 \end{aligned}

x 3 = x 2 x = ( x + 1 ) x = x 2 + x = ( x + 1 ) + x = 2 x + 1 \begin{aligned} x^3&=x^2x\\ &=(x+1)x\\ &=x^2+x\\ &=(x+1)+x\\ &=2x+1 \end{aligned}

x 1 = 1 x + 0 x 2 = 1 x + 1 x 3 = 2 x + 1 x n = F n x + F n 1 \begin{aligned} x^1&=1x+0\\ x^2&=1x+1\\ x^3&=2x+1\\ &\,\,\,\vdots\\ x^n&=F_nx+F_{n-1} \end{aligned}

x 6006 = F 6006 x + F 6005 = a 1 x + b 1 x^{6006}=F_{6006}x+F_{6005}=a_1x+b_1

( a 1 , b 1 ) = ( F 6006 , F 6005 ) \Rightarrow\left(a_1,b_1\right)=(F_{6006},F_{6005})

x 12355 = F 12355 x + F 12354 = a 2 x + b 2 x^{12355}=F_{12355}x+F_{12354}=a_2x+b_2

( a 2 , b 2 ) = ( F 12355 , F 12354 ) \Rightarrow\left(a_2,b_2\right)=(F_{12355},F_{12354})

{ 6006 = 2 × 3 × 7 × 11 × 13 12354 = 2 × 3 × 29 × 71 \begin{cases} 6006&=2\times3\times7\times11\times13\\ 12354&=2\times3\times29\times71 \end{cases}

gcd ( a 1 , b 2 ) = gcd ( F 6006 , F 12354 ) = F gcd ( 6006 , 12354 ) = F 2 × 3 = F 6 = 8 \begin{aligned} \gcd(a_1,b_2)&=\gcd(F_{6006},F_{12354})\\ &=F_{\gcd(6006,12354)}\\ &=F_{2\times3}\\ &=F_6\\ &=\boxed{8} \end{aligned}

Ramiel To-ong
Jun 5, 2015

for the highest common factor for x is the golden mean = 8

Fox To-ong
Feb 2, 2015

for the highest common factor for x is the golden mean = 8

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...