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.



Cardinality of the prime divisor set of a k-power sum
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).


