$ a_1, a_2, \ldots, a_n$ are integers, not all equal. Prove that there exist infinitely many prime numbers $ p$ such that for some $ k$ \[ p\mid a_1^k + \dots + a_n^k.\]
Problem
Source: Iranian National Olympiad (3rd Round) 2004
Tags: number theory, greatest common divisor, modular arithmetic, prime numbers, number theory proposed
10.01.2009 17:15
Without loss of generality, assume that the greatest common divisor of $ a_i$ is $ 1$ (if not divide each by the gcd - the claim and its reverse is not changed). Suppose for the sake of contradiction, there was a finite set of primes $ \{p_1,p_2,...,p_n\}$ that constituted all factors of $ \sum a_i^k$. Let $ f(p_i)$ be the number of $ a_j$ not divisible by $ p_i$ (notice that this number is at least $ 1$). Now let $ p_i^{e_i}$ be the least power of $ p_i$ such that it does not divide $ f(p_i)$. Letting $ k=2\prod \phi(p_i^{e_i})$ yields that $ \sum a_i^k\equiv f(p_i)\not\equiv0\pmod{p_i^{e_i}}$. Thus, the largest factor of $ p_i$ dividing into the sum is $ p_i^{e_i-1}$. We know that $ \phi(p_i^{e_i})=p_i^{e_i-1}(p-1)\ge p_i^{e_i-1}$ thus $ k> \prod p_i^{e_i-1}$. Also, from $ \sum_{i,j}(a_i-a_j)^2>0$, we know that at least one of $ a_i$ is greater than $ 1$. Suppose that $ a_n\ge2$. Then $ \sum a_i^k\ge 2^k\ge k>\prod p_i^{e_i-1}$. Thus, there must be some other prime factor dividing $ \sum a_i^k$.
11.04.2018 05:05
My proof looks a bit different from the above one, so can anybody check
(btw also see this for a possible generalization.)