# $n!+k$ is never any power of any prime number if $n\ge 6$ and $2\le k\le n$?

Question : Is the following true?

"If $n!+k$ is a power of a prime number, then it is one of $2!+2, 3!+2, 3!+3, 4!+3, 5!+5$ where $n,k\in\mathbb Z$ satisfy $n\ge 2$ and $2\le k\le n$."

Motivation : The following is well known :

1. A sequence $(n+1)!+k\ (k=2,3,\cdots,n+1)$ does not have any prime number for any $n\in\mathbb N$.

I've just got the following :

2. A sequence $\{(n+1)!+(n+1)\}!+(n+1)!+k\ (k=2,3,\cdots,n+1)$ does not have any power of any prime number for any $n\in\mathbb N$.

After thinking about these sequences, I reached the above expectation. However, I can neither prove this expectation is true nor find any counterexample. Can you help?

-
You might want to use "power of any integer", instead of restricting it to "power of any prime". –  Calvin Lin Oct 2 '13 at 13:41
It is easy to prove that $(2n)!+k$ is not a power of prime for $2 \leq k \leq n$. –  N. S. Oct 2 '13 at 14:20
@CalvinLin: What I want to use is "power of any prime" though this question might be easy for you to solve. –  mathlove Oct 2 '13 at 14:50
@N.S.: Nice info. So, "odd cases" still remain unsolved for you? I would like you to write the proof, though. –  mathlove Oct 2 '13 at 14:52
Actually, it is not an issue of odd/ even, my proof works only for small $k$. More exactly, I added the proof which works for all $n$ and all $2 \leq k \leq \frac{n}{2}$. –  N. S. Oct 2 '13 at 18:14

This is not a solution. As Daniel pointed out, the first step is incorrect, and should instead be $k = p^m$ instead of $k=p$. I'm leaving this up here for a while, to see if it helps anyone else.

(There is a missing case at the end, which I believe is minor.)

First, since $k \mid n! + k$, in order for it to be a prime power, we must have $k = p$ a prime. For a fixed prime $p$, suppose there exists an $n$ such that $p^i = n! + p$.

Since $p \mid n!$ thus $n \geq p$. Observe that if $n \geq 2p$, then the RHS would be equivalent to $p \pmod{p^2}$, hence cannot be a power. So we have $p \leq n < 2p$, with $n! = p^i - p$.

The cases $p=2, 3, 5$ are easily dealt with, and yield your counterexamples. For $p \geq 7$, we first restrict our attention to $p < n < 2p$. We have $p! \geq p^4$, and so $n! \geq p^{n-p+4}$, which leads to $i \geq n-p+4$.

Now, working modulo $p^{n-p+4}$, we get that

$$n! \equiv - p \pmod{p^{n-p+4}} \Rightarrow (n-p)! \equiv -1 \pmod{p^{n-p+3}}.$$

However, since $0 < (n-p)! < p^{n-p} < p^{n-p+3}$, it cannot leave a remainder of $-1$. Hence, there are no solutions.

Missing case:

It remains to deal with the case that $p! + p = p^i$, which I don't know how to complete. Ideally I would like to show how $p=5$ arises from this, which would allow me to rewrite the above for $p \geq 5, p! \geq p^2$.

Edit The case $k=p^m, m \geq 2$.

We claim that for $p \geq 3$ we have $p^m \geq (m+1)p$. Indeed, this is equivalent to $p^{m-1} \geq m+1$, which is true since,

$$p^{m-1} \geq 3^{m-1} =(1+2)^{m-1} \geq 1+2(m-1) \geq 2m-1 \geq m+1$$

As $n\geq p^m \geq (m+1)p$ there are at least $m+1$ multiples of $p$ in $n!$, and hence $p^{m+1}|n!$.

If $p=2$ then it is easy to prove that $2^{m-1} \geq m+1$ holds for all $m \geq 3$.

Then, if $p \geq 3$ or if $p=2$ and $m \geq 3$, we can write $n!=ap^{m+1}$ with $a \geq 1$ integer.

Then

$$n!+k=ap^{m+1}+ p^m=p^m(ap+1) \,.$$

As $ap+1$ is relatively prime to $p$ and $ap+1 >1$ it follows that $n!+k$ is not a power of $p$.

The only case left to study is $p=2, m=2$, in which case we need to show that if $n \geq 4$ we have $n!+4 \neq 2^{m}$, which is obvious as the LHS is $4 \pmod 8$ and not equal to $4$.

-
$k = p^m$ a prime power cannot be immediately ruled out. –  Daniel Fischer Oct 2 '13 at 14:00
@DanielFischer Good point. I can't seem to deal with $k = p^m$ properly, even for $k=p$. –  Calvin Lin Oct 2 '13 at 14:09
$k=p^m, m\geq 2$ can easily be ruled out, because in that case $n \geq p^m \Rightarrow p^{m+1}|n!$. –  N. S. Oct 2 '13 at 14:22
@N.S. I don't see why. E.g. if $m=2$, then we could have $n = 2p+1$. Notice that $(2p+1)! + p^2$ is a multiple of $p^3$. –  Calvin Lin Oct 2 '13 at 15:23
But is $p^2=k \leq n=2p+1$? ;) –  N. S. Oct 2 '13 at 16:22

As pointed in my comment, it is trivial to show that if $2 \leq k \leq n$ we have $(2n)!+k$ is not a power of prime.

Actually, we can prove the following stronger result: If $2 \leq k$ and $2k \leq n$ then $n!+k$ is not a power of prime.

The proof is identical to the case $k=p^m$ in Calvin's answer, just simpler.

As $2k \leq n$ then $k^2 |n!$ and hence

$$n!+k=k(ak+1)$$

for some positive integer $a$. Then, as $k \geq 2$ and $ak+1 \geq 2$, there exists a prime $p|k$ and a prime $q|ak+1$. As $k, ak+1$ are relatively prime, we have $p \neq q$, and both $p,q$ divide $k(ak+1)=n!+k$.

This takes care of the case $2 \leq k \leq \frac{n}{2}$.

-

Suppose that $$n!+k=p^r\ \ (r\ge 2).$$ Since it is obvious that $k$ is a power of $p$, let $k=p^s\ (1\le s\lt r).$ However, if $s\gt 1,$ then $n\ge k=p^s\gt p$ leads that $p^{s+1}$ is a divisor of $n!$. Noting that $s+1\le r$ and that $p^{s+1}$ is a divisor of $p^r$, this leads that $p^{s+1}$ is a divisor of $p^r-n!=p^s$, which is a contradiction. Hence, we get $s=1, k=p\le n$. By the same argument as above, we get $n\lt 2p$.

By the way, the number of a prime factor $2$ included in $n!\ (n\ge 2)$ is $\sum_{i=1}^{\infty}\lfloor{\frac{n}{2^i}}\rfloor$ where $\lfloor x\rfloor$ is the largest integer not greater than $x$, so we get \begin{align}\sum_{i=1}^{\infty}\lfloor\frac{n}{2^i}\rfloor\ge\lfloor\frac n2\rfloor+\lfloor\frac n4\rfloor\ge\left(\frac n2-\frac 12\right)+\left(\frac n4-\frac 34\right)=\frac{3n-5}{4}\qquad(1)\end{align} On the other hand, letting $r-1=2^mu$ where $m$ is non-negative integer and $u$ is odd, we get $$p^{r-1}-1=(p^{2^m})^u-1=(p^{2^m}-1)\{(p^{2^m})^{u-1}+\cdots+(p^{2^m})^2+p^{2^m}+1\}.$$ Since $\{\ \}$ is odd, we get $e(m)=\sum_{i=1}^{\infty}\lfloor{\frac{n}{2^i}}\rfloor$ where $e(m)$ represents the number of a prime factor $2$ included in $p^{2^m}-1$. Since $p^{2^m}-1=(p^{2^{m-1}}+1)(p^{2^{m-1}}-1)$, we know that $e(m)=1+e(m-1)$. (This is because $p^{2^s}+1\not\equiv 0$ (mod $4$) for any $s\in\mathbb N$.) This leads
\begin{align}e(m)\le e(1)+m-1\ \ (m\ge 0)\qquad(2)\end{align}

Let's consider $e(1)$. Letting $p=2l+1\ (l\in\mathbb N)$, since $p^2-1=(p+1)(p-1)=(2l+2)(2l)$, we get $2^{e(1)}=\frac{2^2(l+1)l}{q}$. Since $l\le q$, we get $2^{e(1)}\le 2^2(l+1)=2(p+1)\le 2(n+1)$, which leads \begin{align}e(1)\le \log_2(n+1)+1\qquad(3)\end{align}

Let's consider $m$. Since $u$ is odd, noting $r-1=2^mu,$ we get $2^m\le r-1\iff m\le \log_2(r-1).$ Since $p^r\lt p+2p^n\le 3p^n\le p^{n+1}$, we get $r\le n$. Here I used $n!\le 2\left(\frac n2\right)^n\lt 2p^n$ since $n\lt 2p$. Hence we get \begin{align}m\le \log_2(n-1)\qquad(4)\end{align}

From $(1)(2)(3)(4)$, we get $$\frac{3n-5}{4}\le \log_2(n^2-1).$$

To make calculations easier, let's consider $\frac{3n-5}{4}\lt \log_2n^2$. Then, we know that $n$ must satisfy the following condition : $$3n-5\lt 8\log_2n,\ n\ge 3.$$

Observing the function $f(x)=8\log_2x-3x+5=8\frac{\log_ex}{\log_e2}-3x+5\ (x\ge 3),$ we get $3\le n\le 10.$ Observing every $n$, we know that $2!+2, 2!+2, 3!+3,4!+3,5!+5$ are the only such examples. Now the proof is completed.

-