Maths Olympiad Prep

Library / /7 of 12

, 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 iwr=zsi \cdot w^r = z^s.

Solution

Note that w=cosπ6+isinπ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=cos2π3+isin2π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
iwr=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+34s(mod12)r + 3 \equiv 4s \pmod{12}. In particular, r+30,4, or 8(mod12)r + 3 \equiv 0, 4, \text{ or } 8 \pmod{12}.

* If r+30(mod12)r + 3 \equiv 0 \pmod{12}, then r=9+12mr = 9 + 12m and s=3ns = 3n, where 0m70 \le m \le 7 and 1n331 \le n \le 33, accounting for 833=2648 \cdot 33 = 264 ordered pairs.
* If r+34(mod12)r + 3 \equiv 4 \pmod{12}, then r=1+12mr = 1 + 12m and s=1+3ns = 1 + 3n, where 0m80 \le m \le 8 and 0n330 \le n \le 33, accounting for 934=3069 \cdot 34 = 306 ordered pairs.
* If r+38(mod12)r + 3 \equiv 8 \pmod{12}, then r=5+12mr = 5 + 12m and s=2+3ns = 2 + 3n, where 0m70 \le m \le 7 and 0n320 \le n \le 32, accounting for 833=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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