# looking for a multiplicity one prime in a finite sum

So I'm trying to compute the Galois group of family of polynomials (indexed by their degree) using the technique of the Newton polygon. In order to apply this technique I need to find some good prime number $p$.

So this is the motivation behind my question that might seem a little bit unmotivated:

Let $N$ be a large integer. Then it is not too difficult to show the following statement:

Theorem: For every prime $p$ such that $N/2< p< 2N/3$ one has that $p$ divides the following sum $$S_N:=\sum_{k=0}^N \binom{N+k}{k}2^{N-k}(-1)^k$$

After many numerical examples, it always happens that most of the primes in the interval $N/2 < p < 2N/3$ divide $S_N$ with multiplicity one. So here is my question:

Q: How would you show that there exists at least one prime $p$ in the interval $N/2 < p < 2N/3$ that divides exactly $S_N$, i.e., $p|S_N$ but $p^2\nmid S_N$ ,?

Note that the square of the product of all primes in the interval $(\frac{N}{2},\frac{2N}{3})$ is less that $\binom{2N}{N}$, so a naive counting argument does not seem to work here.

If you think that this problem is intractable then let me know, I'll try a different strategy.

-
I expect you mean there exists $p$ in this range which divides $S_N$ but $p^2$ does not? – Todd Trimble Mar 26 '11 at 15:03
Yes exactly Todd – Hugo Chapdelaine Mar 26 '11 at 15:44
Hi GH, the key point is to notice that for $2p-N\leq k\leqp-1$ and $3p-N\leq k\leq N$ that $p$ divides $\binom{N+k}{k}$. Then one uses simple manipulations and congruences modulo $p$ and Wilson's theorem at one place and that's it. But the sketch of proof that I just explained does not say much about the residue class modulo $p^2$. – Hugo Chapdelaine Mar 26 '11 at 21:53
I was trying to compute $S_p \mod p^2$ but won't help as $73^2 | S_{73}$. – Felipe Voloch Mar 27 '11 at 7:02
@Gerhard Yes it is that much bigger. $\small S_{100}=2^5 \cdot 3 \cdot 53 \cdot 59 \cdot 61 \cdot 67 \cdot 3567917 \cdot 163655344202455746133481155996257157083231473$ which is about $7 \cdot 10^{59}$ the square of the product of all the primes up to $67$ is about $6.2 \cdot 10^{49}$. – Aaron Meyerowitz Mar 28 '11 at 0:12

No answer, just some data. Up to $n=825$ there are 41 pairs $[p,n]$ such that $S_n \equiv 0 \mod p^2$ and $\frac n2 \lt p \lt \frac{2n}{3}$. Here they are: $\small [7, 12], [11, 21], [29, 55], [41, 68], [43, 72], [47, 80], [61, 100], [73, 136], [\mathbf{89}, 138], [\mathbf{89}, 150], [79, 156], [89, 167]$ $\small [109, 183] [\mathbf{127}, 206], [\mathbf{127}, 230], [131, 231], [157, 276], [181, 301], [199, 306], [197, 364], [227, 386], [257, 445]$ $\small [\mathbf{277}, 450], [\mathbf{277}, 475] [313, 482], [251, 492], [353, 538], [307, 542], [421, 654], [439, 670], [367, 701], [431, 702]$ $\small [\mathbf{359}, 703], [\mathbf{359}, 710], [373, 731] [401, 737], [467, 737], [409, 755], [431, 757], [491, 798], [419, 822]$
Over the same range the (naively ) expected number of repeat divisors of that type is about $43$ so the result seems almost certainly true, but perhaps for no special reason.
It is notable that several times one gets the same $p$ twice in a row. I don't know if it is significant however.