HMMT 十一月 2025 · 冲刺赛 · 第 27 题

HMMT November 2025 — Guts Round — Problem 27

[13] Let a , a , a , . . . be a sequence of integers such that a = 2 and a = a − a + 1 for all n ≥ 1. 1 2 3 1 n +1 n n 3 Compute the remainder when a is divided by 7 . 500 © 2025 HMMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2025, November 08, 2025 — GUTS ROUND Organization Team Team ID#

解析

[13] Let a , a , a , . . . be a sequence of integers such that a = 2 and a = a − a + 1 for all n ≥ 1. 1 2 3 1 n +1 n n 3 Compute the remainder when a is divided by 7 . 500 Proposed by: Pitchayut Saengrungkongka Answer: 274 Solution: Let p = 7. Notice that for all n ≥ 1, p a ≡ a − a + 1 ≡ a − a + 1 ≡ 1 (mod p ) . n +1 n n n n Therefore, there exists a sequence of integers x , x , . . . such that we can write a = 1 + px for 2 3 n +1 n +1 all n ≥ 1. Plugging this into the recurrence, we have 1 + px = a n +1 n +1 7 = a − a + 1 n n p = (1 + px ) − (1 + px ) + 1 n n p p p 2 = · · · + ( px ) + ( px ) + − px n n n 2 1 0 2 3 ≡ p x − px + 1 (mod p ) n n 3 ≡ 1 + p (( p − 1) x ) (mod p ) . n By repeatedly applying this fact, we get n − 2 3 1 + px ≡ 1 + p (( p − 1) x ) (mod p ) n 2 © 2025 HMMT for all n ≥ 2. We have a = 127 = 1 + 7 · 18, so x = 18. Now, using the above identity, 2 2 a = 1 + px 500 500 498 ≡ 1 + p (( p − 1) x ) 2 498 ≡ 1 + p · 18 · ( p − 1) ≡ 1 + p · 18 · (1 − 498 p + · · · ) ≡ 1 + p · 18 · (1 − 498 p ) 2 ≡ 1 + 7 · 18 − 7 · 18 · 498 2 ≡ 1 + 7 · 18 − 7 · 4 · 1 3 ≡ 127 − 196 ≡ − 69 ≡ 274 (mod p ) .