Cardinality of the prime divisor set of a k-power sum

Let $a_{1},\dots,a_{n}$ be positive natural numbers ($n>2$) such that $a_{i}\neq a_{j}$ if $i\neq j$. I want to prove that $$\left\lvert \left\{ p \text{ prime} \; : \; p \mid \sum_{i=1}^n a_{i}^{k} \text{ for some } k\in\mathbb{N} \right\} \right\rvert = \infty .$$ I considered $p > a_{i},\,\forall i=1,\dots,r$ and $k=\frac{p-1}{2}$ so $$\sum_{i=1}^n a_{i}^{k} \equiv \sum_{i=1}^n \left(\frac{a_{i}}{p}\right) \bmod p$$ where $\left(\frac{*}{*}\right)$ is the Legendre symbol. But now I'm stuck because nothing guarantees that $$\sum_{i=1}^n \left(\frac{a_{i}}{p}\right) \equiv 0 \bmod p .$$ Thanks.

• This follows from the finiteness of solutions to the $S$-unit equation. See for example the main theorem in math.uwaterloo.ca/pure-mathematics/sites/ca.pure-mathematics/… . Maybe there's an easier proof ... – Lucia Dec 20 '14 at 10:21
• The phrase " narrowness implies uniformity" comes to mind. This may be a result of McKenzie. I will check on it later. – The Masked Avenger Dec 20 '14 at 10:36
• @lucia Sorry but I can't see how this can help me... Can you give me an hint? – peppo Dec 20 '14 at 10:45
• Assume that only finitely many primes occur. Let $S$ be the set consisting of those primes together with the prime divisors of the $a_i$. Then $a_i^k$ for all $i$ and $b = a_1^k + \ldots + a_n^k$ are $S$-units, and we have the relation $a_1^k + \ldots + a_n^k - b = 0$. The main result on $S$-unit equations says that there are only finitely many solutions (up to scaling by $S$-units) such that no nontrivial sub-sum vanishes. This condition follows in your case from $a_i > 0$. – Michael Stoll Dec 20 '14 at 15:35
• A stronger result for the case $k=3$ seems to be called "Reutter's theorem". A question on MSE asking a reference for it (and a link to AoPS with an elementary proof) can be found here math.stackexchange.com/questions/1475267/… – Paolo Leonetti Oct 11 '15 at 20:15

Without loss of generality, we can assume that there is no prime dividing all $a_i$. For each prime $p$, denote by $n_p$ the number of those $a_i$ not divisible by $p$, and let $v_p$ be the power to which $p$ divides $n_p$. (Notice that $n_p>0$ by the assumption that no prime divides all $a_i$; hence, $v_p$ are well-defined.) By Euler's theorem from the elementary number theory, we have $$a_i^{p^{v_p}(p-1)}\equiv 1\pmod {p^{v_p+1}}$$ for each $a_i$ not divisible by $p$, implying $$\sum_{i=1}^n a_i^k\equiv n_p\not\equiv 0\pmod {p^{v_p+1}}$$ whenever $k$ is a multiple of $p^{v_p}(p-1)$. It follows that for every finite set $P$ of primes, if $k$ is divisible by the product $\prod_{p\in P} p^{v_p}(p-1)$, then each prime $p\in P$ divides the sum $\sum_{i=1}^n a_i^k$ to the power not exceeding $v_p\le\log_p n$. Taking $k$ sufficiently large, we see that this sum is just too large to have all its prime divisors in $P$. In other words, for every finite set $P$ of primes, there exists $k$ such that the sum in question has a prime divisor outside of $P$. This shows that the set of all prime divisors of all these sums is infinite.
Incidentally, this argument does not use the fact that all $a_i$ are pairwise distinct; it suffices that not all of them are equal to each other (which is easily seen to be a necessary condition, too).