HMMT 二月 2007 · 冲刺赛 · 第 22 题

HMMT February 2007 — Guts Round — Problem 22

[ 12 ] The sequence { a } is defined by a = 7 a − a for positive integers n with initial values n n ≥ 1 n +2 n +1 n a = 1 and a = 8. Another sequence, { b } , is defined by the rule b = 3 b − b for positive 1 2 n n +2 n +1 n integers n together with the values b = 1 and b = 2. Find gcd( a , b ) . 1 2 5000 501

解析

[ 12 ] The sequence { a } is defined by a = 7 a − a for positive integers n with initial values n n ≥ 1 n +2 n +1 n a = 1 and a = 8. Another sequence, { b } , is defined by the rule b = 3 b − b for positive 1 2 n n +2 n +1 n integers n together with the values b = 1 and b = 2. Find gcd( a , b ) . 1 2 5000 501 Answer: 89 . We show by induction that a = F and b = F , where F is the k th Fibonacci n 4 n − 2 n 2 n − 1 k number. The base cases are clear. As for the inductive steps, note that F = F + F = 2 F + F = 3 F − F k +2 k +1 k k k − 1 k k − 2 and F = 3 F − F = 8 F + 3 F = 7 F − F . k +4 k +2 k k k − 2 k k − 4 We wish to compute the greatest common denominator of F and F . The Fibonacci numbers 19998 1001 satisfy the property that gcd( F , F ) = F , which can be proven by noting that they are periodic m n gcd( m,n ) modulo any positive integer. So since gcd(19998 , 1001) = 11, the answer is F = 89. 11 6