MathDB
Subsets and gcd

Source: Romania TST,Day 3,problem 4

May 18, 2014
number theorygreatest common divisorfunctionnumber theory unsolved

Problem Statement

Let nn be a positive integer and let AnA_n respectively BnB_n be the set of nonnegative integers k<nk<n such that the number of distinct prime factors of gcd⁡(n,k)\gcd(n,k) is even (respectively odd). Show that ∣An∣=∣Bn∣|A_n|=|B_n| if nn is even and ∣An∣>∣Bn∣|A_n|>|B_n| if nn is odd.
Example: A10={0,1,3,7,9}A_{10} = \left\{ 0,1,3,7,9 \right\}, B10={2,4,5,6,8}B_{10} = \left\{ 2,4,5,6,8 \right\}.
Back to ProblemsView on AoPS