HMMT 二月 2005 · 冲刺赛 · 第 32 题

HMMT February 2005 — Guts Round — Problem 32

[10] Let a = 3, and for n ≥ 1, let a = ( n + 1) a − n . Find the smallest m ≥ 2005 1 n +1 n 2 such that a − 1 | a − 1. m +1 m

解析

Let a = 3, and for n ≥ 1, let a = ( n + 1) a − n . Find the smallest m ≥ 2005 such 1 n +1 n 2 that a − 1 | a − 1. m +1 m Solution: 2010 We will show that a = 2 · n ! + 1 by induction. Indeed, the claim is obvious for n = 1, n and ( n + 1)(2 · n ! + 1) − n = 2 · ( n + 1)! + 1. Then we wish to find m ≥ 2005 such that 2 2( m + 1)! | 4( m !) + 4 m !, or dividing by 2 · m !, we want m + 1 | 2( m ! + 1). Suppose m + 1 is composite. Then it has a proper divisor d > 2, and since d | m !, we must have d | 2, which is impossible. Therefore, m + 1 must be prime, and if this is the case, then m + 1 | m ! + 1 by Wilson’s Theorem. Therefore, since the smallest prime greater than 2005 is 2011, the smallest possible value of m is 2010.