# Proof of existence of infinitely many primes that divide the sequence $\{S(k)\}=\sum_{i=1}^{n} a_i^k$ where $\{a_i\}_{i=1}^{n}$ forms an AP

For the sake of a mathjax solution and because of finding an error in my previous solution (which I had posted here for correction), I have edited the whole document

Let $a_i$ for $1 \leq i \leq n$ be a non constant Arithmetic Progression.

Define: $$S(k)=\sum_{i=1}^{n} a_i^k$$

Prove that there are infinitely many primes which divide the sequence $\{ S(k) \} _{k\in \mathbb{N}}$ where $S(k)$ doesn't remain constant.

The term: infinitely many primes which divide the sequence $\{ S(k) \} _{k\in \mathbb{N}}$ is a bit messy to understand.

Clarification of the statement:

The sequence $\{S(k)\}$ has infinitely many terms different terms since it's not constant. Now the terms are not restricted to being divisible by only a certain number of primes. Like suppose, consider a set of primes: $\mathcal{P}=\{p_1, p_2, \cdots, p_m\}$. Then there will exist a term in the sequence of $\{S(k)\}_{k=1}^{\infty}$ which will get divided by a prime $p_j$ such that $p_j \notin \mathcal{P}$.

Doubt:

Here (below in the form of images) I have provided half of the solution, as best I could. I think I'm not wrong.

May I get some guidance to complete the second case?

Solution:

First, let us assume to the contrary and let $\mathcal{P}=\{p_1, p_2, \cdots, p_m\}$ denote the set of primes that ONLY divide $S(k)$ and suppose $\text{GCD}(a_1, a_2, \cdots, a_n)=d$. Then we get $a_i=db_i$ such that $\text{GCD}(b_1, b_2, \cdots, b_n)=1$ Choose $p > n$ which means $p \nmid n$.

Fix a prime $p \in \mathcal{P}$ and show that there exists a prime $p \mid S(k)$ such that $p \notin \mathcal{P}$ leading to a condration and hence proving the inexistence of finitely many primes that divide the sequence.

We get two cases:

Case 1: $p \nmid d$

If $p \mid S(k)$, then, $p \mid d^k \sum_{i=1}^n b_i$ and since $p \nmid d$, we see $p \mid \sum b_i$. Set $k=\prod (p_i-1); ~ p \in \mathcal{P}$ From Euler's theorem (the one that uses Totient\Phi function), we get that $b_i \equiv \{0,1\} \pmod p \implies \sum b_i \not\equiv 0 \pmod p$ and hence we get the desired contradiction.

Case 2: $p \mid d$

(Could not solve)

• Bumping the topic, can anyone check my proof? Is there any loophole? – Mathejunior Jul 3 '17 at 12:25
• No, simply no. Your main idea looks somewhat promising, but your work is really hard to read. If you want someone here to check it, turn it into a nice to read form... Two short comments from the first page: The question talks about an arithmetic progression $a_i$ and you use some $b_i$ that don't have a common divisor; why? – Dirk Jul 3 '17 at 12:34
• I have initially shown that irrespective of the sequence being in AP, just if all terms are distinct and have GCD=1, then we'll get infinitely many primes dividing the sequence. And then, I have have considered the AP (having GCD=d). It's like a lemma that I have used initially – Mathejunior Jul 3 '17 at 12:38
• Take $n=1$ and you only get finitely many primes. Take $n = 2$ and $a_1 = 0, a_2 = 1$ and you will get no primes at all. I'm sure there are other counter examples. Thus, the first step should be to state the question correctly. Then you might want to ask a single question regarding your proof, not just give three pages and say "please read"... – Dirk Jul 3 '17 at 12:56
• For a prime $p$ and a sequence $\{S_k\}_{k\in\Bbb N}$ what is the meaning of "$p$ divides the sequence $\{S_k\}_{k\in\Bbb N}$"? I would understand it as $\forall k\in\Bbb N\colon p\mid S_k$, but that won't make sense here ... – Hagen von Eitzen Jul 3 '17 at 13:10

Let us assume that the prime divisors of $S(k)$ belong to $\{p_1,p_2,\ldots,p_m\}$ for any $k\geq 0$. By Van Der Waerden's theorem, there are arithmetic progressions $k_1,k_2,k_3,\ldots,k_\eta$ of arbitrary length such that $S(k_1),S(k_2),\ldots,S(k_\eta)$ are multiples of some $p_\mu$, and we may assume without loss of generality $k_\eta>p_\mu$. Newton's identities then imply that $a_1,a_2,\ldots,a_n$ are multiples of $p_\eta$. We may define $\tilde{a}_j = a_j/p_\eta$ and repeat the same argument, but since $\mathbb{Z}$ is a UFD an infinite descent is not allowed and the claim is proved.
• @Mathbg: in your case $2$, just replace $a_i$ with $a_i/p$ and restart, like I do at the end of my proof. – Jack D'Aurizio Jul 5 '17 at 17:35