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

HMMT November 2012 — Guts Round — Problem 32

[ 17 ] Define f ( n ) to be the remainder when n is divided by 23 for each positive integer n . Find the smallest positive integer k such that f ( n + k ) = f ( n ) for all positive integers n .

解析

[ 17 ] Answer: 2530 Note that φ (23) = 22 and φ (22) = 10, so if lcm(23 , 22 , 10) = 2530 | k then f ( n + k ) ≡ f ( n ) (mod 23) is always true. We show that this is necessary as well. Choosing n ≡ 0 (mod 23), we see that k ≡ 0 (mod 23). Thus n + k ≡ n (mod 23) always, and we can move to the exponent by choosing n to be a generator modulo 23: n + k n ( n + k ) ≡ n (mod 22) The choice of n here is independent of the choice (mod 23) since 22 and 23 are coprime. Thus we must have again that 22 | k , by choosing n ≡ 0 (mod 22). But then n + k ≡ n (mod 11) always, and we can go to the exponent modulo φ (11) = 10 by choosing n a generator modulo 11: n + k ≡ n (mod 10) From here it follows that 10 | k as well. Thus 2530 | k and 2530 is the minimum positive integer desired.