Maths Olympiad Prep

Track / Stage 7 / 197 of 300 #1597 of 1964

Problem 1597

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.4 Prove it

Example 9 If in the standard factorization of a positive integer, the exponent of each prime factor is greater than 1, then it is called a power number. Prove: There exist infinitely many distinct positive integers, such that neither they nor the sum of any different numbers among them are power numbers.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Proof Let 2=p1<p2<<pn<2=p_{1}<p_{2}<\cdots<p_{n}<\cdots be all the prime numbers, then
p1,p12p2,p12p22p3,,p12p22pn12pn,p_{1}, p_{1}^{2} p_{2}, p_{1}^{2} p_{2}^{2} p_{3}, \cdots, p_{1}^{2} p_{2}^{2} \cdots p_{n-1}^{2} p_{n}, \cdots

satisfies the requirement.
To verify this claim, we denote the nn-th number in the sequence as ana_{n}. First, each ana_{n} is not a power. For any r,s,,n(1r<s<<n)r, s, \cdots, n(1 \leqslant r<s<\cdots<n), by (1), prarp_{r} \mid a_{r} but pr2arp_{r}^{2} \nmid a_{r}, and prasar,,pranarp_{r}\left|\frac{a_{s}}{a_{r}}, \cdots, p_{r}\right| \frac{a_{n}}{a_{r}}. Therefore, in
ar+as++an=ar(asar++anar+1)a_{r}+a_{s}+\cdots+a_{n}=a_{r}\left(\frac{a_{s}}{a_{r}}+\cdots+\frac{a_{n}}{a_{r}}+1\right)

the second factor is coprime with prp_{r}, so the prime prp_{r} appears exactly once in the standard factorization of ar+as++ana_{r}+a_{s}+\cdots+a_{n}, hence ar+as++ana_{r}+a_{s}+\cdots+a_{n} is not a power. Moreover, since there are infinitely many primes, there are also infinitely many numbers in (1).

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.