PUMaC 2023 · 数论（B 组） · 第 1 题

PUMaC 2023 — Number Theory (Division B) — Problem 1

Find the number of positive integers n < 100 such that gcd( n , 2023) ̸ = gcd( n, 2023 ).

解析

Find the number of positive integers n < 100 such that gcd( n , 2023) ̸ = gcd( n, 2023 ). Proposed by Austen Mazenko Answer: 7 a b Consider a prime p that occurs as p in the prime factorization of n and p in the prime 2 2 factorization of 2023. Then, in the prime factorizations of gcd( n , 2023) and gcd( n, 2023 ) we min(2 a,b ) min( a, 2 b ) will have a p and a p , respectively. If these differ for some p , which is necessary and sufficient for the two gcd’s to differ, then min(2 a, b ) ̸ = min( a, 2 b ). This can’t happen if either one of a, b is zero. If they’re both nonzero, we notice this is true precisely when a = b . If b ̸ = a , then either min(2 a, b ) = b which isn’t equal to a or 2 b , or min(2 a, b ) = 2 a which doesn’t 2 equal a or 2 b , so the minima are indeed different. Now, 2023 = 7 · 17 , so the condition holds 2 for all n < 100 such that either 49 | n or 17 | n and 17 ∤ n . This first case happens for two n and the second happens for 5 choices of n (the second condition always holds for n < 100), giving 7 in total (49 , 98 , 17 , 34 , 51 , 68 , 85).