WordGPT

gcd(F₁₂, Fβ‚β‚ˆ) = F₆

Exercise Β· Level 4 (Hard)

Find the greatest common divisor of the Fibonacci numbers F₁₂ = 144 and Fβ‚β‚ˆ = 2584.

gcd⁑(F12,F18)=Fgcd⁑(12,18)\gcd(F_{12},F_{18})=F_{\gcd(12,18)}

wordgptpro.com

Solution

  1. The Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … so F12=144F_{12}=144 and F18=2584F_{18}=2584.

  2. Euclid's algorithm on the numbers: 2584=17β‹…144+1362584=17\cdot144+136, 144=1β‹…136+8144=1\cdot136+8, 136=17β‹…8+0136=17\cdot8+0, so the gcd is 8, which is F6F_6.

    gcd⁑(144,2584)=8=F6=Fgcd⁑(12,18)\begin{aligned}&\gcd(144,2584)\\&=8=F_6\\&=F_{\gcd(12,18)}\end{aligned}
    (1)
  3. The general reason: Fm+n=Fm+1Fn+FmFnβˆ’1F_{m+n}=F_{m+1}F_n+F_mF_{n-1} lets Euclid's algorithm on the numbers follow Euclid's algorithm on the indices.

Answer8=F68=F_6

wordgptpro.com

Need a hint?

The gcd of two Fibonacci numbers is the Fibonacci number whose index is the gcd of the indices.

gcd(F₁₂, Fβ‚β‚ˆ) = gcd(144, 2584) = 8 = F₆, because gcd(12, 18) = 6.

How to work it out

  1. The Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … so F12=144F_{12}=144 and F18=2584F_{18}=2584.

  2. Euclid's algorithm on the numbers: 2584=17β‹…144+1362584=17\cdot144+136, 144=1β‹…136+8144=1\cdot136+8, 136=17β‹…8+0136=17\cdot8+0, so the gcd is 8, which is F6F_6.

    gcd⁑(144,2584)=8=F6=Fgcd⁑(12,18)\begin{aligned}&\gcd(144,2584)\\&=8=F_6\\&=F_{\gcd(12,18)}\end{aligned}
    (1)
  3. The general reason: Fm+n=Fm+1Fn+FmFnβˆ’1F_{m+n}=F_{m+1}F_n+F_mF_{n-1} lets Euclid's algorithm on the numbers follow Euclid's algorithm on the indices.

LaTeX source of the formulas on this page
\[ 8=F_6 \]
\[ \gcd(144,2584)=8=F_6=F_{\gcd(12,18)} \]

Questions

What is the answer to: gcd(F₁₂, Fβ‚β‚ˆ) = F₆?

gcd(F₁₂, Fβ‚β‚ˆ) = gcd(144, 2584) = 8 = F₆, because gcd(12, 18) = 6.

What is the key idea?

Fibonacci numbers inherit the divisibility structure of their indices.

Is there a hint?

The gcd of two Fibonacci numbers is the Fibonacci number whose index is the gcd of the indices.

Related problems

More number theory problems

    gcd(F₁₂, Fβ‚β‚ˆ) = F₆: answer and solution | WordGPT