Maths Olympiad Prep

Library / /65 of 94

Geometry Difficulty 5.0 AIME, harder Find the answer United States

Problem:
Our third and final item comes to us from Germany, I mean Geometry. It is known that a regular nn-gon can be constructed with straightedge and compass if nn is a prime that is 11 plus a power of 22. It is also possible to construct a 2n2n-gon whenever an nn-gon is constructible, or a p1p2pmp_{1} p_{2} \cdots p_{m}-gon where the pip_{i}'s are distinct primes of the above form. What is really interesting is that these conditions, together with the fact that we can construct a square, is that they give us all constructible regular nn-gons. What is the largest nn less than 4,300,000,0004,300,000,000 such that a regular nn-gon is constructible?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
The known primes of this form (Fermat primes) are 33, 55, 1717, 257257, and 6553765537, and the result is due to Gauss (German). If there are other such primes (unknown), then they are much bigger than 101010^{10}. So for each product of these primes, we can divide 4.31094.3 \cdot 10^{9} by that number and take log2\log_{2} to find the largest power of 22 to multiply by, then compare the resulting numbers. There are 3232 cases to check, or just observe that 232=4,294,967,2962^{32} = 4,294,967,296 is so close that there's likely a shortcut. Note that 232+12^{32} + 1 is divisible by 641641, and hence not prime. 351725765537=23213 \cdot 5 \cdot 17 \cdot 257 \cdot 65537 = 2^{32} - 1 is smaller; replacing any of the factors by the closest power of 22 only decreases the product, and there's not enough room to squeeze in an extra factor of 22 without replacing all of them, and that gives us 2322^{32}, so indeed that it is the answer.

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.