PUMaC 2017 · 数论（A 组） · 第 8 题
PUMaC 2017 — Number Theory (Division A) — Problem 8
题目详情
- Find the minimum value attained by gcd ( M − m, 400) for M an integer in the range m =1 [1746 , 2017]. 1
解析
- Algebraic manipulation reduces this to minimizing gcd( x, 400) for a ∈ N (by playing with x = a the variables and noting periodicity and symmetry of gcd about 0). We claim this occurs at a = 1. Set k = 100 and n = 400. We now solve this problem in generality. Lemma : Let n be a positive integer and let S be a finite multiset of factors of n . For each d | n , let m ( S ) be the number of multiples of d in S . Then d ∑ ∑ k = m ( S ) φ ( d ) . d k ∈ S d | n Proof : This is a simple induction on the number of elements of S . The theorem is clear for | S | = 0; suppose it holds for | S | = r . Now let S have r + 1 elements and choose k ∈ S . Let ′ ′ ′ S be S with one fewer copy of k ; the theorem holds for S . Adding k to S increments the ∑ ′ left-hand sum by k and the right-hand sum by φ ( d ), since m ( S ) = m ( S ) + 1 for d | k d d d | k ∑ ′ and m ( S ) = m ( S ) for all other d . But φ ( d ) = k , so the theorem holds for S . This d d d | k completes our induction. For n implicit, define the multiset S = { gcd( x, n ) | x ∈ { a, a + 1 , . . . , a + k − 1 }} . Observe a,k that for all d | n , holding k constant, m ( S ) is minimal for a = 1. It follows from the Lemma d a,k a + k − 1 ∑ that gcd( x, n ) is minimized for a = 1, as desired. x = a Going back to the problem, we thus find that the minimum value occurs at M = 101; a consequence is that 0 is also a minimum; and thus 2000 too is a minimum. Computation gives that the sum there is equal to 680 . Problem written by Eric Neyman and Zack Stier 3 If you believe that any of these answers is incorrect, or that a problem had multiple reasonable interpretations or was incorrectly stated, you may appeal at http://tinyurl.com/PUMaCappeal2017. All appeals must be in by 1 PM to be considered. 4