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.

#NumberTheory

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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 - 5 years, 5 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.

Anthony Kirckof - 5 years, 5 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!

Calvin Lin Staff - 5 years, 5 months ago

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.

Anthony Kirckof - 5 years, 4 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.

Alex Siryj - 5 years, 5 months ago

Math	Appears 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}$