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.

A while ago, I was told of this exercise in Pollack's book, "Not always buried deep." I think it is exercise 3 in chapter 1, but I do not own a copy of the book, so I cannot give more precise references.

I have heard from different people that the exercise is harder than intended, and the reference given in the book does not quite prove the statement. I was hoping somebody knew of a reference, or sees how to solve it.

The question is to show the following. (I think this is then applied to show some estimates on the number of primes in an interval, but this is the part I am interested in.)

If $n\ge 6$ and $2\le k\le n$, then $\frac{n!}k+1$ has a prime factor larger than $n$.

Towards a contradiction, suppose that this is not the case. If $p$ is a prime factor of $(n!/k)+1$, then we are assuming that $p\le n$ and since $p\mid n!+k$, then $p\mid k$. In fact, $p=k$, or else $p$ appears in the factorization of $n!/k$. So we are saying that $(n!/p)+1$ is a power of $p$, and we are led to the equation $$ n! = p^r-p $$ from the title. Conversely, any solution to this equation leads to a pair $(n,k)$ contradicting the statement of the question, except for the fact that perhaps $n<6$.

Now, the above is on the trivial side of things but unfortunately I do not see how to continue. (We have that $n<2p$. Perhaps Stirling can be somehow used to bound the size of $r$?)

Note that $n\ge 6$ needs to be used somehow, as otherwise we have counterexamples:

  • If $n=2$, we have $2!=2^2-2$.
  • If $n=3$, we have $3!=2^3-2=3^2-3$.
  • If $n=4$, we have $4!=3^3-3$.
  • If $n=5$, we have $5!=5^3-5$.
share|improve this question
1  
The reference given in the book is M R Chowdhury, Uber die Zahlenfolge $n!+k$, $2\le k\le n$, Elem Math 44 (1989) 129-130. –  Gerry Myerson Mar 2 '12 at 5:27
    
The reference should be to T. Grundhöfer, Über die Zahlen der Form n!+k, Arch. Math. (Basel) 33 (1979/80), no. 4, 361–363. He gives a short elementary proof of only a page or so, but my German is too poor and I too lazy to decipher it. For those with access: metapress.com/content/v55247h338723q15/fulltext.pdf –  Thomas Bloom Mar 2 '12 at 10:54
add comment

1 Answer

up vote 6 down vote accepted

The Chowdhury paper is available here. He proves:

Theorem. If $n>1$ and $2\le k\le n$, then either

$\qquad(1)\quad n!+k$ has a prime factor greater than $n$, or
$\qquad(2)\quad k$ is prime, $k>n/2$, and $n!+k$ is a power of $k$.

His argument is essentially as follows:

Proof. Suppose that $n!+k$ has no prime factor greater than $n$, and let $p\le n$ be a prime dividing $n!+k\,$; clearly $p\mid k$. Suppose first that $p<k$, so that $k$ is not prime; if $q\le n$ is prime, then $q\mid\frac{n!}k$, so $q\nmid\frac{n!}k+1$, and $\frac{n!}k+1$ must therefore have a prime factor $q>n$. But then $q\mid k\left(\frac{n!}k+1\right)=n!+k$, a contradiction. Thus, $k$ must itself be prime, and $n!+k=k^m$ for some $m\ge 2$. Then $k\nmid k^{m-1}-1=\frac{n!}k$, so $k>\frac{n}2$. $\dashv$

He then cites T. Grundhöfer, Über die Zahlen der Form $n!+k$, Arch. Math. 33, 361-363 (1979), for the result that if $n>5$, none of the numbers $n!+k$ with $2\le k\le n$ can be a prime power. Thus, for $n\ge 6$ the second alternative of the Theorem cannot hold, and $n!+k$ must have a prime factor greater than $n$.

Added: I have now seen Grundhöfer’s paper. He first proves a

Lemma. For all $n\in\mathbb{Z}^+$, $n!\le 2\left(\frac{n}2\right)^n$.

The proof is by induction: $$2\le\left(1+\frac1n\right)^n=\left(\frac{(n+1)/2}{n/2}\right)^n\;,\tag{1}$$ whence $$\begin{align*} (n+1)!&=(n+1)n!\\ &\le(n+1)\left(2\left(\frac{n}2\right)^n\right)\\ &\le(n+1)\left(\frac{n+1}2\right)^n\tag{by (1)}\\ &=2\left(\frac{n+1}2\right)^{n+1}\;. \end{align*}$$

Then he proves that the only pairs $\langle n,k\rangle$ such that $n\ge 2$, $2\le k\le n$, and $n!+k$ is a prime power are $\langle 2,2\rangle,\langle 3,2\rangle,\langle 3,3\rangle,\langle 4,3\rangle$, and $\langle 5,5\rangle$, which are respectively $2^2,2^3,3^2,3^3$, and $5^3$.

Proof. Let $p$ be a prime such that $n!+k=p^r$, where $n\ge 2$ and $2\le k\le n$. Since $k\mid n!+k$, $k=p^s$ for some $s$ with $1\le s<r$; $p^{s+1}\mid p^r=n!+p^s$, so $p^{s+1}\nmid n!$, and since $p^s=k\le n$, we must have $s=1$ and $k=p$, so that $$n!=p^r-p=p(p^{r-1}-1)\;.\tag{2}$$ Moreover, we must have $p>n/2$. When $p=2$, the righthand side of $(2)$ is congruent to $2$ mod $4$, so $n<4$, and we have the first two exceptional $\langle n,k\rangle$ pairs, $\langle 2,2\rangle$ and $\langle 3,2\rangle$. Assume henceforth that $p$ is an odd prime.

For $a\in\mathbb{N}$ let $m(a)$ be the largest $m$ such that $$2^m\mid p^{2^a}-1=\left(p^{2^{a-1}}-1\right)\left(p^{2^{a-1}}+1\right)\;.$$ The factorization shows that $m(a+1)=m(a)+1$ for $a\ge 1$, so $m(a)=m(1)+a-1$ for $a\ge 1$. Moreover, $m(0)\le m(1)-1$.

Write $r-1=2^au$, where $u$ is odd. Then $$p^{r-1}-1=\left(p^{2^a}-1\right)\sum_{i=0}^{u-1}p^{2^ai}\;,$$ so $m(a)$ is the highest power of $2$ dividing $p^{r-1}-1$. Equating the maximum powers of $2$ dividing the two sides of $(2)$ yields $$\sum_{i\ge 1}\left\lfloor\frac{n}{2^i}\right\rfloor=m(a)\le m(1)+a-1\tag{3}\;.$$ Note that since $2^{m(1)}$ is the highest power of $2$ dividing $p^2-1=(p+1)(p-1)$, we must have $m(1)\le\lg(p+1)+1\le\lg(n+1)+1$, where $\lg$ is $\log_2$.

Next, note that by the lemma we have $p^r-p=n!\le 2\left(\frac{n}2\right)^n<2p^n$ (recall that $p>n/2$), which is false for $r>n$, so $r\le n$. Since $r-1=2^au\ge 2^a$, this implies that $$a\le\lg(r-1)\le\lg(n-1)\;,$$ whence from $(3)$ we have $$\sum_{i\ge 1}\left\lfloor\frac{n}{2^i}\right\rfloor=m(a)\le \lg(n+1)+1+\lg(n-1)-1<2\lg n\;.\tag{4}$$ I claim that $(4)$ has only finitely many solutions.

Clearly $$\sum_{i\ge 1}\left\lfloor\frac{n}{2^i}\right\rfloor\ge\left(\frac{n}2-\frac12\right)+\left(\frac{n}4-\frac34\right)=\frac14(3n-5)\;,$$ so $(4)$ implies that $3n-5<8\lg n$, i.e., $3n-8\lg n<5$. The function $3n-8\lg n$ is monotone increasing for $n\ge 4$, and for $n=11$ we already have $$33-8\lg 11=33-4\lg 121>33-4\lg 128=5\;,$$ so $(4)$ implies that $n\le 10$ and thence that $$\sum_{i\ge 1}\left\lfloor\frac{n}{2^i}\right\rfloor\le\lfloor 2\lg 10\rfloor=\lfloor\lg 100\rfloor=6\;.$$ Thus, we must have $n\le 7$. Since $p>n/2$ and $p\ge 3$, the only possible $\langle n,k\rangle$ pairs are $\langle 3,3\rangle,\langle 4,3\rangle,\langle 5,3\rangle,\langle 5,5\rangle,\langle 6,5\rangle,\langle 7,5\rangle$, and $\langle 7,7\rangle$, of which only the first, second, and fourth are prime powers. $\dashv$

share|improve this answer
    
So the question becomes, how did Grundhofer do it? –  Gerry Myerson Mar 2 '12 at 11:25
1  
@Gerry: Yep. But I wasn’t about to pay US$34.95 for online access to the Arch. Math. paper! –  Brian M. Scott Mar 2 '12 at 11:35
    
@Brian: Thanks. But unfortunately I had already mentioned all of this. –  Bruce George Mar 2 '12 at 18:26
    
@Bruce: No, you hadn’t. Gerry Myerson provided the Chowdhury reference, and Thomas Bloom apparently posted the Grundhöfer reference very shortly after I did. –  Brian M. Scott Mar 2 '12 at 22:28
    
@Brian: Gotcha, sorry for the misunderstanding. I just meant the mathematics, as in "Oh, so that paper does not help at all because all it does is what I already knew." Thomas' reference is the key one, it is now clear. I am currently trying to get a copy of it. –  Bruce George Mar 2 '12 at 23:19
show 2 more comments

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.