$ 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
cosinator
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$.
Kayak
11.04.2018 05:05
My proof looks a bit different from the above one, so can anybody check
Perform change $a_i \rightarrow \frac{a_i}{\gcd(a_1, \cdots, a_n)}$ to ensure that no prime simontaneously divides all of them. Suppose FTSOC there are only finitely many primes $\{p_1, \cdots, p_k\}$. Define $S_i = \{a_j | p_i \text{ doesn't divide } \; a_j\}$ (by clearing the gcd, we have ensured that each of $S_i$ are nonempty) and let $g_i = v_{p_i}(\sum_{a_j \in S_i}{a_j})$ and $g(i) = \sum_{1 \leq j \leq n} a_j^i$
and $m = lcm(p_1- 1, p_2-1, p_3 - 1, \cdots, p_k-1, p_1^{2g_1}, p_2^{2g_2} \cdots, p_k^{2g_k})$ and $q = 2* \max (g_1, g_2, \cdots, g_k) + 1$
Now I claim that $g(qm + 1)$ has a prime divisor other than those $k$ primes.
Claim: $v_{p_i}(g(mq+1)) = g_i$
ProofSince for all $a_j \in S_i$ we have $\gcd(p_i, a_j) = 1$, so $ \sum_{a_j \in S} a_j \equiv \sum_{a_j \in S} a_j^{mq + 1} \equiv p_i^{g_i} s \mod p_i^{2g_i}$, with $ s \not \equiv 0 \mod p_i$ since $mq+1 \equiv 1 \mod \phi(p_i^{2g_i})$, so $v_{p_i}(\sum_{a_j \in S_i} a_j^{mq+1}) = g_i$. Also, $v_{p_i}(\sum_{a_j \not \in S_i} a_j^{mq+1}) \geq mq + 1$, so by the identity $v_p(a+b) = \min(v_p(a), v_p(b))$ when $v_p(a) \neq v_p(b)$we have $v_{p_i}(\sum_{1 \leq j \leq n} a_j^{mq+1}) = \min (v_{p_i}(\sum_{a_j \in S_i}{a_j^{mq+1}}),v_{p_i}(\sum_{a_j \not \in S_i}{a_j^{mq+1}})) = g_i $
So if there are only finitely many primes, then $$ g(1) << g(mq+1) = \prod_{1 \leq i \leq k} p_i^{\nu_{p_i}(g(mq+1))} = \prod_{1 \leq i \leq k} p_i^{g_i} \leq g(1) $$, which is a clear contradiction.
(btw also see this for a possible generalization.)