PUMaC 2021 · 数论（A 组） · 第 4 题

PUMaC 2021 — Number Theory (Division A) — Problem 4

Let f ( n ) = k . If the prime factorization of f (2020) can be written as p p . . . p , 1 2 k gcd( k,n )=1 , 1 ≤ k ≤ n k P find p e . i i i =1

解析

Let f ( n ) = k . If the prime factorization of f (2020) can be written as p p . . . p , 1 2 k gcd( k,n )=1 , 1 ≤ k ≤ n k P find p e . i i i =1 Proposed by: Frank Lu Answer: 818 n P P P P P P 3 3 3 3 3 First, note that we can write i = i = d i = d f ( n/d ) . i =1 d | n gcd( i,n )= d d | n gcd( i/d,n/d )=1 d | n P 2 n + n 2 3 But then we have that ( ) = d f ( n/d ) . Now, note that, for a constant k dividing d | n 2 1 2 P P ( n/k ) +( n/k ) 3 ′ 3 3 2 n, we have that d f ( n/d ) = ( kd ) f ( n/d ) = k ( ) . Then, we can use a 2 k | d,d | n k | d,d | n PIE-esque argument based on divisibility by each of the prime factors (and products of these 2 2 n n k prime factors), yielding us, after simplifying, ( p − 1) . . . ( p − 1)( +( − 1) ) . We thus find 1 k 4 p ...p 1 k 2 6 4 2 6 4 2 that f (2020) = 2020 / 4 ∗ 4 ∗ 100 ∗ 4039 , which equals 2 ∗ 5 ∗ 101 ∗ 4039 = 2 ∗ 5 ∗ 7 ∗ 101 ∗ 577 , yielding us the answer of 12 + 20 + 7 + 202 + 577 = 32 + 786 = 818 .