PUMaC 2012 · 数论（B 组） · 第 6 题

PUMaC 2012 — Number Theory (Division B) — Problem 6

[ 6 ] Let f ( x ) = n + x . Evaluate the product n gcd { f (2002) , f (2003) } × gcd { f (2012) , f (2013) } × gcd { f (2022) , f (2023) } , 2001 2001 2011 2011 2021 2021 where gcd { x, y } is the greatest common divisor of x and y .

解析

[ 6 ] Let f ( x ) = n + x . Evaluate the product n gcd { f (2002) , f (2003) } × gcd { f (2012) , f (2013) } × gcd { f (2022) , f (2023) } , 2001 2001 2011 2011 2021 2021 where gcd { x, y } is the greatest common divisor of x and y . Solution: We use the Euclidean Algorithm to solve this problem. 2 2 2 2 2 gcd { n + x , n + ( x + 1) } = gcd { n + x , n + x + 2 x + 1 } = gcd { n + x , 2 x + 1 } . 2 2 Note that 2 x + 1 is odd, so multiplying n + x by 4 will not change the greatest common divisor. Then we have 2 2 2 gcd { n + x , 2 x +1 } = gcd { 4 n +4 x , 2 x +1 } = gcd { 4 n +(2 x +1) − 4 x − 1 , 2 x +1 } = gcd { 4 n − 4 x − 1 , 2 x +1 } gcd { 4 n − 4 x − 1 , 2 x + 1 } = gcd { 4 n + 1 , 2 x + 1 } . Then the calculations are simple. gcd { 8005 , 4005 } = 5, gcd { 8045 , 2025 } = 5, and gcd { 8085 , 2045 } = 5, so the product is 5 × 5 × 5 = 125 .