PUMaC 2023 · 数论（A 组） · 第 7 题
PUMaC 2023 — Number Theory (Division A) — Problem 7
题目详情
- Define f ( n ) to be the smallest integer such that for every positive divisor d | n , either n | d or d f ( n ) d | n . How many positive integers b < 1000 which are not squarefree satisfy the equation f (2023) · f ( b ) = f (2023 b )?
解析
- Define f ( n ) to be the smallest integer such that for every positive divisor d | n , either n | d or d f ( n ) d | n . How many positive integers b < 1000 which are not squarefree satisfy the equation f (2023) · f ( b ) = f (2023 b )? Austen Mazenko Answer: 5 The crux of the problem is the following claim: Q e n i Lemma 1 : Let n = p be the prime factorization of n . Then f ( n ) = e . i i i min p i i n Proof : To prove it, we first show that this value is necessary. Let d = | n . Denoting e i min p i i e n i d d k := arg min p , trivially p | n but d = = ⇒ p ∤ d = ⇒ p ∤ d , so n ∤ d . e i k k k k i p k n n d f ( n ) d f ( n ) Because d | n , ν ( d ) ≤ ν ( n ) which, for i ̸ = k , is e · e ≤ e · f ( n ), so e ≤ f ( n ) p p i i k i i i min p p i i k as claimed. n e i d d min p i i To see that it’s sufficient, we split into cases to show that d | n implies n | d or d | n . n First, suppose there exists some prime p | n that doesn’t divide d . Denote d := e . Then, j j j p j n e i d d j j d min p i i d | d = ⇒ d | d , and d | n because for any ℓ ̸ = j , j j j n e n i d j min p i i ν ( d ) = e · d ≤ e · = ν n . p ℓ j ℓ p ℓ j e ℓ i min p i i Q a i It remains to address the case where d possesses the same prime factors as n . Write d = p i i d with 1 ≤ a ≤ e for each i , and consider when n | d . It holds whenever for each ℓ we have i i Q Q a a i d i ν ( n ) = e ≤ a · p = ν ( d ). Next, suppose there exists some k such that e > a · p . p ℓ ℓ p k k ℓ i ℓ i i i n e i d min p i i It suffices to show that in this case we have d | n , which by looking at valuations Q Q a a n e i i i is the same as a · p ≤ e · e for each ℓ . By assumption, p < max , so ℓ ℓ i i i i i i a min p i i i Q a a a e n i ℓ ℓ k · p < · ≤ e which implies the result. To see why this last inequality holds, i i i e e a min p ℓ ℓ k i i note that if n is a prime power then we have equality as ℓ = k . Otherwise, Y √ n e a e / 2 k ℓ i 1 / 2 e / 2 k ≥ n = p ≥ 2 · 2 ≥ e ≥ · , k e i i min p a e i k ℓ i i 4 which is precisely the claimed bound. □ n To finish the problem, for simplicity denote g ( n ) := , so g ( n ) is the smallest prime power f ( n ) m n appearing in the prime factorization of n . Notice f ( m ) · f ( n ) = f ( mn ) ⇐⇒ · = g ( m ) g ( n ) mn ⇐⇒ g ( mn ) = g ( m ) · g ( n ), so it suffices to solve g (2023 b ) = g (2023) · g ( b ) = 7 g ( b ). g ( mn ) Now, g ( b ) and g (2023 b ) are both prime powers, and thus must both be powers of 7. If 49 | g ( b ), then either g ( b ) = 49 or 343 because otherwise g ( b ) must have some other prime power factor, 2 but this would have to exceed 49, so b > 49 > 1000. However, if b ≥ 49 is a power of 7 then g (2023 b ) is not, contradiction. Thus, g ( b ) = 7, forcing g (2023 b ) = 49. Writing b = 7 a for some 7 ∤ a , we see that any prime power dividing a other than 17 must be at least 49. If 17 | a , 2 then either 17 | a = ⇒ b > 1000 or a is 7 · 17 · some prime power greater than 49, which again forces b > 1000. Thus, the only possibilities are a is a prime power greater than 49 (and with exponent greater than 1) such that 7 a < 1000. Tabulating, we see the only possibilities are b = 7 · 64 , 7 · 81 , 7 · 121 , 7 · 125 , 7 · 128, giving a final answer of 5.