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

HMMT November 2014 — Guts Round — Problem 19

[ 11 ] Let a sequence { a } be defined by a = 2 , a = 2 , and a = a a for n ≥ 1. The n 0 1 n +1 n n =0 n − 1 sequence of remainders when a , a , a , · · · are divided by 2014 is eventually periodic with some minimal 0 1 2 period p (meaning that a = a for all sufficiently large integers m , and p is the smallest such m m + p positive integer). Find p .

解析

[ 11 ] Let a sequence { a } be defined by a = 2 , a = 2 , and a = a a for n ≥ 1. The n 0 1 n +1 n n =0 n − 1 sequence of remainders when a , a , a , · · · are divided by 2014 is eventually periodic with some minimal 0 1 2 period p (meaning that a = a for all sufficiently large integers m , and p is the smallest such m m + p positive integer). Find p . b n Answer: 12 Let a = 2 , so notice b = 1 , b = 2 , and b = b + 2 b for n ≥ 1, so by n 1 2 n +1 n n − 1 n − 1 n − 1 2 inspection b = 2 for all n ; thus a = 2 . 2014 = 2 · 19 · 53 so we just want to find the lcm of n n n the eventual periods of 2 mod ord (2) and ord (2). These orders divide 18 and 52 respectively, and 19 53 we can manually check ord (2) = 6 and ord (2) = 12. The lcm of these is 12, so to show the answer 9 13 4 is 12, it suffices to show that 13 | ord (2). This is true since 2 6 ≡ 1 (mod 53). So, the answer is 12 . 53