Library / Harvard-MIT Mathematics Tournament /89 of 352

Harvard-MIT Mathematics Tournament

Algebra Difficulty 4.8 AIME Find the answer United States

Problem:

The sequence $\{a_n\}_{n \geq 1}$ is defined by $a_{n+2} = 7 a_{n+1} - a_n$ for positive integers $n$ with initial values $a_1 = 1$ and $a_2 = 8$ . Another sequence, $\{b_n\}$ , is defined by the rule $b_{n+2} = 3 b_{n+1} - b_n$ for positive integers $n$ together with the values $b_1 = 1$ and $b_2 = 2$ . Find $\operatorname{gcd}(a_{5000}, b_{501})$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: 89. We show by induction that $a_n = F_{4n-2}$ and $b_n = F_{2n-1}$ , where $F_k$ is the $k$ $\text{th}\$$ Fibonacci number. The base cases are clear. As for the inductive steps, note that
$F_{k+2} = F_{k+1} + F_k = 2 F_k + F_{k-1} = 3 F_k - F_{k-2}$
and
$F_{k+4} = 3 F_{k+2} - F_k = 8 F_k + 3 F_{k-2} = 7 F_k - F_{k-4}$
We wish to compute the greatest common denominator of $F_{19998}$ and $F_{1001}$ . The Fibonacci numbers satisfy the property that $\operatorname{gcd}(F_m, F_n) = F_{\operatorname{gcd}(m, n)}$ , which can be proven by noting that they are periodic modulo any positive integer. So since $\operatorname{gcd}(19998, 1001) = 11$ , the answer is $F_{11} = 89$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.