How to prove $k!+(2k)!+\cdots+(nk)!$ has a prime divisor greater than $k!$

Question:

Let $k$ be a positive integer. Show that there exist $n$ such that $$I=k!+(2k)!+(3k)!+\cdots+(nk)!$$ has a prime divisor $P$ such that $P>k!$.

My idea: Let us denote by $d_{p}(n)$ the maximal power of p that n is divisible by. $$I=k![1+(k+1)(k+2)\cdots (2k)+\cdots+(k+1)(k+2)\cdots (nk)]$$ Then I can't prove it. Maybe we can use Zsigmondy's theorem?

It is said can use follow inequality $$\left(1+\dfrac{1}{12n}\right)\left(\dfrac{n}{e}\right)^n\cdot\sqrt{2n\pi}<n!<\left(1+\dfrac{1}{4n}\right)\left(\dfrac{n}{e}\right)^n\cdot\sqrt{2n\pi}$$ By the way: I fell this problem is very interesting.But I can't prove it.

This is In 2014 China mathematics national team training question(Now china Select 6 people for training, is for China to participate in the IMO. This problem is from the training topic)

Maybe @Ivanh and so on can help me .Thank you.

Solution 1:

Fix $k$ arbitrarily and denote the sum $k! + (2k)! + \cdots + (nk)!$ by $I_n$. It is enough to show that the set of primes $p$ that divide at least one of the $I_n$ is infinite—here is an argument that this is so.

Suppose otherwise that there are only finitely many primes that divide any of the $I_n$. For a given prime $p$ and integer $a$, let $e_p(a)$ be the exponent of $p$ in $a$. We'll need the following property of $e_p$: for any pair $a,b$ of integers, \begin{align*} e_p(a+b) = \min\{e_p(a),e_p(b)\} \tag{1} \end{align*} except possibly when $e_p(a) = e_p(b)$.

Let $U$ be the set of all primes $p$ such that $e_p(I_{n-1}) \geq e_p((nk)!)$ for all $n$ (the primes with unbounded exponent in the sequence $\{I_n\}$), and let $B$ be the complementary set, i.e., the set of all primes $p$ such that $e_p(I_{n-1})<e_p((nk)!)$ for some $n$. Note that if $e_p(I_{n-1}) < e_p((nk)!)$ then $e_p(I_{n-1}) = e_p(I_n) = \cdots$ by virtue of $(1)$. Since there are only finitely many primes $p \in B$ for which $e_p(I_n)$ is ever nonzero, there is an integer $N$ with the property that $e_p(I_n) = e_p(I_N)$ for each $p \in B$ and for all $n \geq N$ (any $N$ such that $Nk$ is at least as big as the largest prime that divides some $I_n$ will do). The point is that $e_p(I_n)$ is constant for sufficiently large $n$ unless $p\in U$.

We have required only that $e_p(I_{n-1}) \geq e_p((nk)!)$ when $p \in U$. But $(1)$ implies that in certain circumstances the two exponents must be equal. Indeed, where $((n+1)k)!$ contains more factors of $p$ than $(nk)!$, we must have $e_p(I_{n-1}) = e_p((nk)!)$ lest $(1)$ give \begin{align*} e_p(I_n) = \min\{e_p(I_{n-1}),e_p((nk)!)\} = e_p((nk)!) < e_p(((n+1)k)!) \end{align*} in violation of the assumption that $p \in U$.

If we now choose $n$ carefully we can force $e_p(I_{n-1}) = e_p((nk)!)$ for all $p \in U$. The foregoing argument shows that this will happen whenever $e_p((nk)!) < e_p(((n+1)k)!)$ for all $p\in U$. If $m = \prod_{p\in U}p$, then $n = am -1$ satisfies this condition for all $a\in\mathbb{N}$. Thus: \begin{align*} e_p(I_{am-2}) = e_p(((am-1)k)!) \quad\text{for $p\in U$ and $a\in\mathbb{N}$.} \end{align*}

We just need one more fact, and that is that $((am-1)k)!$ contains no more factors of any prime $p \in U$ than $((am-2)k)!$ does. If this is true, then we get the following chain for $p\in U$ and $a\in\mathbb{N}$: \begin{align*} e_p(I_{am-3})\geq e_p(((am-2)k)!) = e_p(((am-1)k)!) = e_p(I_{am-2}). \tag{2} \end{align*} Since for large $a$ we have $e_p(I_{am-3}) = e_p(I_{am-2})$ for $p \notin U$, the chain $(2)$ implies for large $a$ that $I_{am-3}$ contains at least as many factors of every prime $p$ as $I_{am-2}$ does. This in turn means that $I_{am-3}\geq I_{am-2}$, which is our desired contradiction.

So it remains only to show that \begin{align*} e_p(((am-1)k)!) = e_p(((am-2)k)!)\quad\text{for $p\in U$}. \tag{3} \end{align*} Since $((am-1)k)!/((am-2)k)! = (amk - k)(amk-k-1)\cdots (amk - 2k+1)$, the exponents will be unequal only if $p$ divides $amk-j$ for some $j<2k$. For $p\in U$ this will be true only if $p$ divides $j$, since in that case $p$ divides $m$. In particular, we would need $p<2k$. But no prime $p$ smaller than $2k$ has unbounded exponent in the sequence $\{I_n\}$ because $I_n/k!$ is not divisible by any such prime. Thus every prime $p\in U$ is bigger than $2k$, and $(3)$ is proved.

Solution 2:

Here are a few observations and thoughts.

Up to $k=30$ one needs $n=3$ for $k=7,11,12,15,16,18,19,20,21,23$ but $n=2$ is sufficient the other $20$ times.

Let $I_{k,n}=I=k!+(2k)!+(3k)!+\cdots+(nk)!=k!J_{k,n}$ where $J_{k,n}=1+\frac{2k!}{k!}+\frac{3k!}{k!}+\cdots+\frac{nk!}{k!}$. A prime less than $2k$ divides all the summands of $J_{k,n}$ except $1$ and hence does not divide $J_{k,n}.$ For $t \gt 2$ and prime $tk \lt p \lt (t+1)k$ we have that $J_{k,n} \equiv J_{k,t} \bmod p$ for $n \ge t$ since all the summands starting with $\frac{(t+1)k!}{k!}$ are multiples of $p$. Hence $p$ divides either all of the $J_{k,n}$ with $kn+k \gt p$ or none of them.

This feels like it is getting close to giving hope for a proof but gaps remain. It seems likely that , for fixed $k$, most primes (in a sense) divide only finitely many of the $J_{k,n}$, in fact probably most divide none of them. It turns out that $1+\frac{26!}{13!}=31\cdot 4591 \cdot 455061112081$ so $31 \mid J_{13,n}$ for all $n \ge 2.$ Similarly $31 \mid J_{15,n}$ , $41 \mid J_{18,n}$ and $23 \mid J_{11,n}$ for $n \ge 2$. Even for such primes, $p^e$ divides either all or none of the $J_{k,n}$ with $kn+n \gt ep.$ In these four cases, none get to $p^2$ except that $41^2 \mid J_{18,4}.$ However $41^3 \nmid J_{18,6}.$

Up to $k=30$ there are three small cases of $J_{k,2}$ being a square (a square of a prime as it happens) but otherwise no repeated prime factors (also none for $J_{k,3}$ in the $10$ cases above that needed it.)

The three cases are as follows (the expansions given look nice but I don't claim anything special about them) $$J_{3,2}=1+4\cdot 5 \cdot 6=1+4\frac{11-1}{2}\frac{11+1}{2}=11^2$$ $$J_{4,2}=1+(5 \cdot 8) (6 \cdot 7) =1+(41-1)(41+1)=41^2$$ and $$J_{7,2}=1+12 \cdot(9\cdot 11 \cdot 14)(8 \cdot 10 \cdot 13)=1+12\frac{4158}{3}\frac{4160}{4}=4159^2.$$

As far as the phenomenon seen above (for $p=23,31$) of primes $p=2k+1$ with $p \mid J_{k,2},$ these are the primes described here.

Solution 3:

I tried a proof by contradiction without succes. Here is my approach nonetheless. I will use the same notation Aaron has used. Write $J_{k,n} = \frac{k!}{k!} + \dots + \frac{nk!}{k!}$ and $I_{k,n} = k! + \dots + (nk)!$.

Suppose the statement is not true. Then a $k \in \mathbb{N}_{>0}$ exists with the following property: for every $n \in \mathbb{N}_{>0}$ we can write $J_{k,n}$ as a product of primes smaller than $k!$. Consider such a number $k$. Define $$A = \{ p \leq k! \mid p \text{ is a prime} \}.$$ For every $p \in A$ let $t_pk < p < (t_p+1)k$ and thus for all $r \in \mathbb{N}_{>0}$ we know that $p^r \mid \frac{(r(t_p + 1)k)!}{k!}$. . This gives the congruence $J_{k,rt_p + r -1} \equiv J_{k,n} \mod{p^r}$ for all natural numbers $n \geq rt_p + r -1$. Therefore (with $p, n$ the same), $p^r \nmid J_{k,rt_p + e -1} \Rightarrow p^r \nmid J_{k,n}$. Thus, if we have $p^r \nmid J_{k,rt_p + r -1}$ for some $r \in \mathbb{N}_{>0}$ , $p \in A$, we can conclude that the exponent of the prime $p$ in the prime factorisation of $J_{k,n}$ has an upper bound (with $n$ variable). If such boundaries were to exist for all $p \in A$, we would have a contradiction, because $(J_{k,n})_n$ diverges and $A$ is a finite set. Thereby, the set $$B = \{ p \in A \mid \forall r \in \mathbb{N}_{>0}: p^r \text{ divides } J_{k,rt_p + r -1} \}$$ is not empty.

Now consider such a $p \in B$ and write $t = t_p$. We then have due to the earlier derived congruence: $$ \forall r \in \mathbb{N}_{>0}: \forall n \geq rt + r -1: p^r \mid J_{k,n}.$$

This being true seems very unlikely to me, but I can't get a contradiction from it. Maybe it is possible to use the given inequality to show there exists a $r \in \mathbb{N}_{>0}$ such that $$qp^{r} < J_{k,n} < (q+1)p^{r},$$ for some $n \geq rt + r -1$ and $q \in \mathbb{N}$.

Solution 4:

Okay, after thinking about this for a while, I don't have a final answer, but I think I've made some progress. I'm not positive that we can extend this to $k!$, but I'll walk through it anyway. It starts by recognizing that we can rewrite $I$ as $$I=k![1+(k+1)(k+2)\cdots (2k)+\cdots+(k+1)(k+2)\cdots (nk)]$$

Now, $k!$ has some prime factorization: $$k! = P_1*P_2*\cdots*P_n$$ These may not all be unique, but it doesn't matter. As $k!$ is not prime for $k\geq3$ we can say WLOG that $P_i<k!$. We can also say (trivially) that every prime number less than $k$ is a factor of $k!$.

Now, since $I$ also has it's own prime factorization, we can say that:$$I = P_1*\cdots*P_n*Q_1*\cdots*Q_m$$ where all $Q_i$ are prime, so therefore $$1+(k+1)(k+2)\cdots(2k) + \cdots + (k+1)(k+2)(k+3)\cdots(nk) = Q_1*Q_2*\cdots*Q_j$$

Finally, we can say that at least one of the $Q_i$'s is greater than $k$. This is true because $(k+1)(k+2)\cdots(2k)$ is a multiple of every prime less than $k$. So therefore $q + (k+1)(k+2)\cdots(2k)$ must have a prime larger than $k$ as a factor.

Now I hit a block, because I'm not sure how (or if we can) extend this to show that as we increase n we're going to ensure that we get a prime factor larger than $k!$. Comments?