Competition problem — Number theory

Library / /34 of 299

Number theory Difficulty 5.7 AIME, harder Prove it Iran

We call a positive integer n lucky if it has at least two prime divisors and can be written in the form
$n = p_1^{\alpha_1} + \cdots + p_k^{\alpha_k}$
where $p_1, \dots, p_k$ are distinct prime divisors of $n$ . (Note that $n$ may have other prime divisors than $p_1, \dots, p_k$ .) Prove that for every prime number $p$ , there exists a lucky number $n$ such that $p \mid n$ .

Solution

We claim that there exist $n$ with three prime factors. Choose a prime $p_1$ . Using quadratic reciprocity and Dirichlet's theorem on arithmetic progressions, choose a prime $p_2$ such that
$\left( \frac{p_1}{p_2} \right) = \left( \frac{p_2}{p_1} \right) = 1$
and choose $p_3$ such that
$\left(\frac{p_1}{p_3}\right) = -1, \quad \left(\frac{p_2}{p_3}\right) = 1$
Now, choose $\alpha_1$ such that its exponents modulo $p_2, p_3$ are equal to $\frac{p_2-1}{2}, \frac{p_3-1}{2}$ respectively, and choose $\alpha_2, \alpha_3$ similarly. Then $n = p_1^{\alpha_1} + p_2^{\alpha_2} + p_3^{\alpha_3}$ satisfies the condition required in the problem. ■

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.