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

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

For positive integers i and j , define d as follows: d = 1, d = 1 for all i and j , and ( i,j ) (1 ,j ) ( i, 1) for i, j > 1, d = d + d + d . Compute the remainder when d is ( i,j ) ( i − 1 ,j ) ( i,j − 1) ( i − 1 ,j − 1) (3 , 2016) divided by 1000.

解析

(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. 1