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
10 months, 4 weeks ago

No vote yet
1 vote

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 · 10 months, 3 weeks 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 · 10 months, 4 weeks ago

Log in to reply

@Calvin Lin 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 · 10 months, 3 weeks ago

Log in to reply

@Anthony Kirckof 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 · 10 months, 3 weeks 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 · 10 months, 4 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...