1990 AIME Problems/Problem 10
The sets and are both sets of complex roots of unity. The set is also a set of complex roots of unity. How many distinct elements are in ?
The least common multiple of and is , so define . We can write the numbers of set as and of set as . can yield at most different values. All solutions for will be in the form of .
and are relatively prime, and by the Chicken McNugget Theorem, for two relatively prime integers , the largest number that cannot be expressed as the sum of multiples of is . For , this is ; however, we can easily see that the numbers to can be written in terms of . Since the exponents are of roots of unities, they reduce , so all numbers in the range are covered. Thus the answer is .
Comment of S1
Using Chicken McNugget Theorem and the property of complex numbers for reasoning is sharp, but note that the Frobenius Number is only constrained to positive integer pairs. Please check on "Comment of S2" below to see how to use Diophantine equation to make a simple deduction. ~ Will_Dai
The 18 and 48th roots of can be found by De Moivre's Theorem. They are and respectively, where and and are integers from to and to , respectively.
Comment on S2
By the property of Diophantine equation, given a problem to find integers x and y so that ax + by = c for some integer constants a, b, c: if gcd(a, b) = 1, then any arbitrary integer c could by formed with some combination of integers (x, y). Double checking the constraints of k_1 and k_2, we realize that all integers of [0, 143] can be formed by 8 * k1 + 3 * k2, yielding the answer of 144. ~Will_Dai
The values in polar form will be and . Multiplying these gives . Then, we get , , , , up to .
|1990 AIME (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|