It is a well-known fact that there exist arbitrarily large gaps in the set of prime numbers. Prove that there are, furthermore, arbitrarily large gaps in the set of powers of primes (i.e. \(2^{1}, 2^{2}, 2^{3}, \ldots, 3^{1}, 3^{2}, 3^{3}, \ldots, 5^{1}, 5^{2}, 5^{3}\ldots,\) etc.). I have a proof using similar construction based on factorials (like the original problem uses), but I wanted to see if there were any other approaches out there.

## Comments

Sort by:

TopNewestHere's the beginning of my proof:

Let \(a!+b=p^{k}\) for some integers \(1<b\leq a\) and \(p\) prime. Since \(b\leq a,\) we have \(b|a!,\) and so \(b|a!+b= p^{k}\). Thus, \(b=p^{m}\) for some \(m<k\). If \(m>1\), then \(p, p^{2}, \ldots , p^{m}<a\), and so \(p^{(m+(m-1)+⋯+1)}|a!=p^{k}-p^{m}=p^{m}(p^{(k-m)}-1)\), and \(p^{((m-1)+(m-2)+⋯+1)}|p^{(k-m)}-1\). This implies that \(p^{(k-m)} \equiv 0 \pmod{p})\). But this only works if \(p^{(k-m)}=1\), or \(k=m\), a contradiction.

So we now have \(a!+p=p^{k}\). Let’s assume that \(2p\leq a\). Then \(p,2p \leq a\), therefore \(p^{2}|a!\). But then \(p^{2}|p^{k}-a!=p\), a contradiction. So \(p\leq a<2p\). Now working with our equation, we get:

\(a!+p=p^k\)

\((p-1)!(p+1)⋯(a-1)a+1=p^{(k-1)}\)

\((p-2)!(p+1)⋯(a-1)a=p^{(k-2)}+p^{(k-3)}+⋯+p+1.\)

From here on, let’s assume that \((p-1)>4\). Then we know that \((p-2)! \equiv 0 \pmod{(p-1)}\) (by the above lemma). We also have \(p^{r} \equiv 1 \pmod{(p-1)}\) for all nonnegative \(r\). Applying these,

\(0 \equiv 1+1+⋯+1+1=k-1 \pmod{(p-1)}\).

So \((k-1)=n(p-1)\), or \(k=n(p-1)+1\) for some integer \(n\). We have \(a!+p=p^{(n(p-1)+1)}\).

Since \(a<2p\), we can write:

\(a! \leq (2p-1)!=[(p-(p-1))(p+(p-1))]\cdot \cdot \cdot [(p-2)(p+2)][(p-1)(p+1)]p\)

\(a! \leq [p^{2}-(p-1)^{2} ][p^{2}-(p-2)^{2} ]\cdot \cdot \cdot [p^{2}-2^{2} ][p^{2}-1^{2} ]p\)

\(a! < (p^{2})(p^{2})\cdot \cdot \cdot (p^{2})(p^{2}-1)p\)

\(a! < (p^{2})^{(p-2)}(p^{2}-1)p\)

\(a! < p^{(2(p-2)+1)}(p^{2}-1).\)

And so:

\(p^{(n(p-1)+1)}=a!+p<p^{(2(p-2)+1)}(p^{2}-1)+p=p^{(2(p-1)+1)}-p^{(2p-3)}+p<p^{(2(p-1)+1)}\).

Since \(p>4\), we thus have \(n(p-1)+1<2(p-1)+1\), or \(n<2\). Clearly, \(n\) must be nonnegative. If \(n=0\), then \(k=1\), a contradiction. So \(n=1\) and \(a!+p=p^{p}\).

From here, I rewrite as \(a!=p^{p}-p\) and compare factors of both sides to prove that no such solutions exist. – Anthony Kirckof · 1 year, 1 month ago

Log in to reply

There's also the chinese remainder theorem approach.

Let \( p_i \) be composite numbers, that are (pairwise) relatively prime. By CRT, there is a solution to the system \( N \equiv - i \pmod { p_i } \).

Then, \(N+1, N+2, \ldots N+n \) are composite numbers (multiplies of \( p_i \)) that are not prime powers.

Note: This problem was posted in IMO 1989, which is why it's so familiar to me. – Calvin Lin Staff · 1 year, 1 month ago

Log in to reply

– Anthony Kirckof · 1 year, 1 month ago

Ah of course! Yeah I came up with a solution by construction: \(k!^{2}+2, ..., k!^{2}+k\). I also made it a fun challenge to try and work with the original construction: \(k!+2, ..., k!+k\), and by golly, that actually holds as well.Log in to reply

Edit: Thanks for adding your proof using the original construction. I wasn't expecting that! – Calvin Lin Staff · 1 year, 1 month ago

Log in to reply

So if \(\{x_n\}\) is the ordered sequence of the powers of primes, given any integer \(n\), you'd like to find \(x_k\) and \(x_{k+1}\) such that \(n\leq x_{k+1}-x_k\)? Sounds pretty convoluted and ill-defined, but I think that's what you're getting at. – Alex Siryj · 1 year, 1 month ago

Log in to reply