8
$\begingroup$

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$.
  • 0
    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: http://www.metapress.com/content/v55247h338723q15/fulltext.pdf2012-03-02

1 Answers 1

6

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, 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; $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$

  • 0
    This is great! Many thanks @Brian.2012-03-03