×

# Gaps in the Powers of Primes

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.

Note by Anthony Kirckof
1 year, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Here'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.

- 1 year, 10 months ago

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.

Staff - 1 year, 10 months 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.

- 1 year, 10 months ago

Hm, the original construction might not hold. For example, $$4! + 3 = 27 = 3^3$$ is a prime power. I don't know if there are larger possibilities. If you have a condition of $$k > 4$$, please let me know.

Edit: Thanks for adding your proof using the original construction. I wasn't expecting that!

Staff - 1 year, 10 months ago

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.

- 1 year, 10 months ago