Maths Olympiad Prep

Library / /857 of 1394

, 2023

Algebra Difficulty 5.4 AIME, harder Prove it United States

Problem:
The number
316990099009901=32016000000000001101 316990099009901 = \frac{32016000000000001}{101}
is the product of two distinct prime numbers. Compute the smaller of these two primes.

Solution

Solution:
Let x=2000x = 2000, so the numerator is
x5+x4+1=(x2+x+1)(x3x+1). x^{5} + x^{4} + 1 = (x^{2} + x + 1)(x^{3} - x + 1).
(This latter factorization can be noted by the fact that plugging in ω\omega or ω2\omega^{2} into x5+x4+1x^{5} + x^{4} + 1 gives 00.) Then x2+x+1=4002001x^{2} + x + 1 = 4002001 divides the numerator. However, it can easily be checked that 101101 doesn't divide 40020014002001 (since, for example, 101120+04101 \nmid 1 - 20 + 0 - 4), so 40020014002001 is one of the primes. Then the other one is
200032000+110120003101>200024002001 \frac{2000^{3} - 2000 + 1}{101} \approx \frac{2000^{3}}{101} > 2000^{2} \approx 4002001
so 40020014002001 is the smaller of the primes.

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.