43
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Can you reveal the source of the problem? $\endgroup$ – jdoicj Jun 12 '14 at 15:01
  • 1
    $\begingroup$ Does $(k!)!\mid(I/k!-1)$ for some $n$? That would do it, but seems overly optimistic. $\endgroup$ – blue Jun 13 '14 at 2:47
9
$\begingroup$

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.

$\endgroup$
2
+25
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ All the $Q_i$ are greater than $2k$ since $\gcd(I,(2k)!)=k!$ $\endgroup$ – Aaron Meyerowitz Jun 20 '14 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.