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 thesmallest 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 canmove 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 wemust have again that 22 | k , by choosing n ≡ 0 (mod 22). But then n + k ≡ n (mod 11) always, andwe 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.