Maths Olympiad Prep

Library / AIME I /7 of 12

AIME I, 2022

Algebra Difficulty 5.9 AIME, harder Prove it United States

Let w=3+i2w = \frac{\sqrt{3}+i}{2} and z=−1+i32z = \frac{-1+i\sqrt{3}}{2}, where i=−1i = \sqrt{-1}. Find the number of ordered pairs (r,s)(r, s) of positive integers not exceeding 100100 that satisfy the equation i⋅wr=zsi \cdot w^r = z^s.

Solution

Note that w=cos⁡π6+i⋅sin⁡π6w = \cos \frac{\pi}{6} + i \cdot \sin \frac{\pi}{6} is a primitive twelfth root of unity, so w3=iw^3 = i and wr=wr+12mw^r = w^{r+12m} for all integers mm and rr. Furthermore, z=cos⁡2π3+i⋅sin⁡2π3z = \cos \frac{2\pi}{3} + i \cdot \sin \frac{2\pi}{3} is a primitive cube root of unity, so w4=zw^4 = z and
i⋅wr=wr+12m+3=zs=w4s. i \cdot w^r = w^{r+12m+3} = z^s = w^{4s}.
Hence the given equation requires that there exists an integer mm such that r+12m+3=4sr + 12m + 3 = 4s, so r+3≡4s(mod12)r + 3 \equiv 4s \pmod{12}. In particular, r+3≡0,4, or 8(mod12)r + 3 \equiv 0, 4, \text{ or } 8 \pmod{12}.

* If r+3≡0(mod12)r + 3 \equiv 0 \pmod{12}, then r=9+12mr = 9 + 12m and s=3ns = 3n, where 0≤m≤70 \le m \le 7 and 1≤n≤331 \le n \le 33, accounting for 8⋅33=2648 \cdot 33 = 264 ordered pairs.
* If r+3≡4(mod12)r + 3 \equiv 4 \pmod{12}, then r=1+12mr = 1 + 12m and s=1+3ns = 1 + 3n, where 0≤m≤80 \le m \le 8 and 0≤n≤330 \le n \le 33, accounting for 9⋅34=3069 \cdot 34 = 306 ordered pairs.
* If r+3≡8(mod12)r + 3 \equiv 8 \pmod{12}, then r=5+12mr = 5 + 12m and s=2+3ns = 2 + 3n, where 0≤m≤70 \le m \le 7 and 0≤n≤320 \le n \le 32, accounting for 8⋅33=2648 \cdot 33 = 264 ordered pairs.
The requested number of ordered pairs (r,s)(r, s) is therefore 264+306+264=834264 + 306 + 264 = 834.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.