HMMT 二月 2021 · 团队赛 · 第 6 题

HMMT February 2021 — Team Round — Problem 6

[70] Let f ( x ) = x + x + 1. Determine, with proof, all positive integers n such that f ( k ) divides f ( n ) whenever k is a positive divisor of n .

解析

[70] Let f ( x ) = x + x + 1. Determine, with proof, all positive integers n such that f ( k ) divides f ( n ) whenever k is a positive divisor of n . Proposed by: Milan Haiman Answer: n can be 1, a prime that is 1 mod 3, or the square of any prime except 3. Solution: The answer is n can be 1, a prime that is 1 mod 3, or the square of any prime except 3. It is easy to verify that all of these work. First note that n must be 1 mod 3 since 1 divides n implies f (1) divides f ( n ). Next, suppose for sake of contradiction that n = ab , with a > b > 1. We are given that f ( a ) divides f ( n ), which means f ( a ) divides f ( n ) − f ( a ). We can write this as 2 2 2 a + a + 1 | n + n − a − a = ( n − a )( n + a + 1) . 2 2 Since we are working mod a + a + 1, we can replace a + 1 with − a , so we have 2 2 2 a + a + 1 | ( n − a )( n − a ) = a ( b − 1)( b − a ) . 2 2 However, a + a + 1 cannot share any factors with a , and 0 < | ( b − 1)( b − a ) | < a + a + 1, which is a contradiction.