Maths Olympiad Prep

Library / Ukrainian National Mathematical Olympiad /42 of 201

Ukrainian National Mathematical Olympiad

Number theory Difficulty 5.2 AIME, harder Prove it Ukraine

How many distinct prime divisors does the number 118+117−13211^8 + 11^7 - 132 have?

Solution

Consider the following transformation:
118+117−132=116⋅(112+11)−132=116⋅132−132=132⋅(116−1). 11^8 + 11^7 - 132 = 11^6 \cdot (11^2 + 11) - 132 = 11^6 \cdot 132 - 132 = 132 \cdot (11^6 - 1).
Since 132=11⋅12=22⋅3⋅11132 = 11 \cdot 12 = 2^2 \cdot 3 \cdot 11, it has three prime divisors: 22, 33, 1111.
116−1=(113−1)(113+1)=(11−1)(112+11+1)(11+1)(112−11+1)=10⋅133⋅12⋅111=23⋅32⋅5⋅7⋅19⋅37. \begin{aligned} 11^6 - 1 &= (11^3 - 1)(11^3 + 1) = (11-1)(11^2 + 11+1)(11+1)(11^2 - 11+1) \\ &= 10 \cdot 133 \cdot 12 \cdot 111 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 19 \cdot 37. \end{aligned}
Therefore, we have four more prime divisors: 55, 77, 1919, 3737.

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.