1990 AIME Problems/Problem 10

Revision as of 20:15, 11 April 2008 by Azjps (talk | contribs) (fmmtting)

Problem

The sets $A = \{z : z^{18} = 1\}$ and $B = \{w : w^{48} = 1\}$ are both sets of complex roots of unity. The set $C = \{zw : z \in A ~ \mbox{and} ~ w \in B\}$ is also a set of complex roots of unity. How many distinct elements are in $C_{}^{}$?

Solution

Solution 1

The least common multiple of $18$ and $48$ is $144$, so define $n = e^{2\pi i/144}$. We can write the numbers of set $A$ as $\{n^8, n^{16}, \ldots n^{144}\}$ and of set $B$ as $\{n^3, n^6, \ldots n^{144}\}$. $n^x$ can yield at most $144$ different values. All solutions for $zw$ will be in the form of $n^{8k_1 + 3k_2}$.

$8$ and $3$ are relatively prime, and it is well known that for two relatively prime integers $a,b$, the largest number that cannot be expressed as the sum of multiples of $a,b$ is $a \cdot b - a - b$. For $3,8$, this is $13$; however, we can easily see that the numbers $145$ to $157$ can be written in terms of $3,8$. Since the exponents are of roots of unities, they reduce $\mod{144}$, so all numbers in the range are covered. Thus the answer is $\boxed{144}$.

Solution 2

The 18 and 48th roots of $1$ can be found by De Moivre's Theorem. They are $\text{cis}\,\left(\frac{2\pi k_1}{18}\right)$ and $\text{cis}\,\left(\frac{2\pi k_2}{48}\right)$ respectively, where $\text{cis}\,\theta = \cos \theta + i \sin \theta$ and $k_1$ and $k_2$ are integers from $0$ to $17$ and $0$ to $47$, respectively.

$zw = \text{cis}\,\left(\frac{\pi k_1}{9} + \frac{\pi k_2}{24}\right) = \text{cis}\,\left(\frac{8\pi k_1 + 3 \pi k_2}{72}\right)$. Since the trigonometric functions are periodic every $2\pi$, there are at most $72 \cdot 2 = 144$ distinct elements in $C$. As above, all of these will work.

See also

1990 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions