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

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

Given two positive integers a 6 = b , let f ( a, b ) be the smallest integer that divides exactly one of a, b , but not both. Determine the number of pairs of positive integers ( x, y ), where x 6 = y , 1 ≤ x, y, ≤ 100 and gcd( f ( x, y ) , gcd( x, y )) = 2.

解析

Given two positive integers a 6 = b , let f ( a, b ) be the smallest integer that divides exactly one of a, b , but not both. Determine the number of pairs of positive integers ( x, y ), where x 6 = y , 1 ≤ x, y, ≤ 100 and gcd( f ( x, y ) , gcd( x, y )) = 2. 1 Proposed by: Frank Lu Answer: 706 First, note that f ( x, y ) is a power of a prime; for any n that divides x but not y , if it has e ′ ′ 1 at least two distinct prime factors, then we can write n as p n , where p doesn’t divide n . 1 1 e 1 ′ ′ e Then, if p divides y , then n can’t divide into y , and n < n . Thus, we see that f ( x, y ) = 2 1 for some exponent e ≥ 1. Furthermore, we see that 2 | x, 2 | y by gcd. WLOG, suppose that f ( x, y ) divides x , but not y . Then, note that the largest power of 2 in y is e − 1; otherwise, e e − 1 either it is divisible by 2 or that 2 is not a divisor of y . Furthermore, the largest power of ′ ′ ′ 2 dividing x is larger than that of y , giving that e ≥ 2. Hence, y = 2 y , y odd, and x = 4 x , ′ x a positive integer. Note also that either both must be divisible by 3, or neither are, else f ( x, y ) ≤ 3. We will proceed with casework. ′ • Case 1: x is not divisible by 3. Then, note that y only has prime factors that are at least ′ 50 50 50