Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

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

share|improve this answer
    
$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}$.

share|improve this answer
up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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