PUMaC 2016 · 数论（A 组） · 第 3 题

PUMaC 2016 — Number Theory (Division A) — Problem 3

For odd positive integers n , define f ( n ) to be the smallest odd integer greater than n that is not relatively prime to n . Compute the smallest n such that f ( f ( n )) is not divisible by 3.

解析

Observe that if n is divisible by 3 then so is f ( n ). Thus, n and f ( n ) must not be divisible by
(As a consequence, n cannot be prime, since then f ( n ) = 3 n .) Let g ( n ) be the smallest prime factor of n . Then f ( n ) = n + 2 g ( n ). If g ( f ( n )) = g ( n ), then f ( n ) = n + 2 g ( n ) and f ( f ( n )) = n + 4 g ( n ), and it is impossible for all of n , n + 2 g ( n ), and n + 4 g ( n ) to not be divisible by 3. Thus, g ( f ( n )) 6 = g ( n ). But observe that g ( n ) | f ( n ), so g ( f ( n )) < g ( n ). Thus, if g ( n ) = 7, then for f ( f ( n )) to not be divisible by 3, g ( f ( n )) must be 5. This means n that n + 2 g ( n ) must be divisible by 5, which means that + 2 must be divisible by 5. g ( n ) Clearly n cannot be 7 · 3. n cannot be 7 · 13 because then f ( n ) = 7 · 15 is divisible by 3. If n = 7 · 23 = 161 then f ( n ) = 7 · 25 = 5 · 35, so f ( f ( n )) = 5 · 37, which is not divisible by 3. If g ( n ) = 11 and n < 161 then n is one of 11 · 11 or 11 · 13, and in both cases f ( f ( n )) is divisible by 3. If g ( n ) > 11 then it is clear that n must be greater than 161 if f ( f ( n )) is to not be divisible by 3. Therefore, the smallest n is 161 . Problem written by Eric Neyman.