Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
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} \)

Comments

Sort by:

Top Newest

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

Log in to reply

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

Log in to reply

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

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...