HMMT 十一月 2014 · 冲刺赛 · 第 32 题

HMMT November 2014 — Guts Round — Problem 32

[ 17 ] Let f ( x ) = x − 2, and let f denote the function f applied n times. Compute the remainder 24 when f (18) is divided by 89.

解析

[ 17 ] Let f ( x ) = x − 2, and let f denote the function f applied n times. Compute the remainder 24 when f (18) is divided by 89. Answer: 47 Let L denote the Lucas numbers given by L = 2, L = 1, and L = L + L . n 0 1 n +2 n +1 n 2 Note that L − 2 = L when n is even (one can show this by induction, or explicitly using L = 2 n n n √ √ 1+ 5 1 − 5 n n 24 ( ) + ( ) ). So, f ( L ) = L 25 . 6 3 · 2 2 2 √ √ p − 1 1+ 5 p 1 − 5 p 2 Now note that since 89 ≡ 4 (mod 5), we have 5 ≡ 1 (mod 89) so L = ( ) + ( ) ≡ L 89 1 2 2 (mod 89) and similarly L ≡ L , so the sequence L (mod 89) is periodic with period 88. (Alter- 90 2 n natively, reason by analog of Fermat’s little theorem, since we can substitute an integer residue for √ 5.) 25 5 We have 3 · 2 ≡ 3 · 2 ≡ 8 (mod 11) and ≡ 0 (mod 8), so L 25 ≡ L (mod 89). Computing L = 47 8 8 3 · 2 gives the answer.