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.
 A: 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).
