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{p1}{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.

2$\begingroup$ This follows from the finiteness of solutions to the $S$unit equation. See for example the main theorem in math.uwaterloo.ca/puremathematics/sites/ca.puremathematics/… . Maybe there's an easier proof ... $\endgroup$ – Lucia Dec 20 '14 at 10:21

$\begingroup$ The phrase " narrowness implies uniformity" comes to mind. This may be a result of McKenzie. I will check on it later. $\endgroup$ – The Masked Avenger Dec 20 '14 at 10:36

$\begingroup$ @lucia Sorry but I can't see how this can help me... Can you give me an hint? $\endgroup$ – peppo Dec 20 '14 at 10:45

$\begingroup$ 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 subsum vanishes. This condition follows in your case from $a_i > 0$. $\endgroup$ – Michael Stoll Dec 20 '14 at 15:35

$\begingroup$ 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/… $\endgroup$ – 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 welldefined.) By Euler's theorem from the elementary number theory, we have $$ a_i^{p^{v_p}(p1)}\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}(p1)$. It follows that for every finite set $P$ of primes, if $k$ is divisible by the product $\prod_{p\in P} p^{v_p}(p1)$, 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).