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

英文解析

32. [ 17 ] Let f ( x ) = x − 2, and let f denote the function f applied n times. Compute the remainderwhen f (18) is divided by 89.24
    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
    Note that L − 2 = L when n is even (one can show this by induction, or explicitly using L =2
    2 n nn
    √ √
    1+ 5 1 − 5
    n n 24
    ( ) + ( ) ). So, f ( L ) = L 25 .
    3 · 26
    2 2
    √ √
    p − 1
    1+ 5 p 1 − 5 p
    Now note that since 89 ≡ 4 (mod 5), we have 5 ≡ 1 (mod 89) so L = ( ) + ( ) ≡ L2
    89 1
    2 2
    (mod 89) and similarly L ≡ L , so the sequence L (mod 89) is periodic with period 88. (Alter-
    90 2 nnatively, 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.