# Improving Gaps in Primes Proof to Include Powers of Primes

Find all positive integer solutions to the equation $$a!+b=p^{k}$$, with $$1<b≤a$$ and $$p$$ prime.

Note by Anthony Kirckof
2 years, 5 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:

Let $$a!+b=p^{k}$$ for some integers $$1<b≤a$$ and $$p$$ prime. Since $$b≤a, b|a!$$, and so $$b|a!+b= p^{k}$$. Thus, $$b=p^{m}$$ for some $$m<k$$. If $$m>1$$, then $$p,p^{2},⋯,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 1 \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≤a$$. Then $$p,2p≤a$$, therefore $$p^{2}|a!$$. But then $$p^{2}|p^{k}-a!=p$$, a contradiction. So $$p≤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)}$$. 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!≤(2p-1)!=[(p-(p-1))(p+(p-1))]⋯[(p-2)(p+2)][(p-1)(p+1)]p$$

$$a!≤[p^2-(p-1)^2][p^2-(p-2)^2]⋯[p^2-2^2 ][p^2-1^2]p$$

$$a!<(p^2)(p^2)⋯(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$$, which is a contradiction. So $$n=1$$ and $$a!+p=p^p$$.

Now let $$p-1=2^{c}x$$ and $$p+1=2^{d}y$$, with $$x$$ and $$y$$ odd. Note either that $$c$$ or $$d$$, but not both, must equal 1. Furthermore, let $$P_2(e)$$ denote the power of 2 in the prime factorization of some integer $$e$$. For example, by our definitions, $$P_2(p-1)=c$$ and $$P_2(p+1)=d$$. Note that if we can write $$e$$ out as a product $$e_1\cdot e_2\cdot \cdot \cdot e_i$$, then we can write $$P_2(e)=P_2(e_1\cdot e_2⋯e_i)=P_2(e_1)+P_2(e_2)+⋯+P_2(e_i)$$.

Case 1: $$c=1$$. We then have:

$$a!=p^p-p=p(p^{p-1}-1)=p(p^{2x}-1)=p(p^{x}-1)(p^{x}+1)$$

$$a!=p(p-1)(p^{x-1}+⋯+p^2+p+1)(p+1)(p^{x-1}-⋯+p^2-p+1)$$

$$P_2(a!)=0+1 + 0 + d + 0$$

$$P_2(a!)=d+1$$

Case 2: $$d=1$$. We then have:

$$a!=p^p-p=p(p^{p-1}-1)=p(p^{2^cx}-1)$$

$$a!=p(p^x-1)(p^x+1)(p^{2x}+1)(p^{2^2x}+1)⋯(p^{2^{c-1}x}+1)$$

$$P_2(a!)=0+c + 1 + 1 + 1 + ⋯ + 1$$

$$P_2(a!)=2c$$

To generalize, we can say that $$P_2(a!)=c(d+1)$$ to cover both of these cases. We now directly give a bound for $$P_2(a!)$$:

$$P_2(a!)=⌊a/2⌋+⌊a/2^2⌋+⋯+⌊a/2^z⌋,$$

where $$z$$ is such that $$2^z≤a<2^{z+1}$$. Since $$a≥2^z$$,

$$P_2(a!)≥2^{z-1}+2^{z-2}+⋯+1=2^z-1.$$

Moving on, we have:

$$2^cx=p-1<a<2^{z+1}$$

$$2^{c-1}-1<2^{c-1}x-1<2^z-1≤P_2(a!)=c(d+1)$$

$$2^{c-1}-1<c(d+1)$$.

Also,

$$2^dy=p+1≤a+1<2^{z+1}+1<2^{z+1}+2$$

$$2^{d-1}-2<2^{d-1}y-2<2^z-1≤P_2(a!)=c(d+1)$$

$$2^{d-1}-2<c(d+1)$$.

In the case where $$c=1$$, we use the second result here, and simplify: $$2^{d-1}-3<d$$. The only $$d$$ for which this equation holds are $$d=1,2,3$$. Once again, we can’t have $$d=1$$, so here, $$d=2$$ or $$3$$. Likewise, in the case where $$d=1$$, using the first result and simplifying, we get $$2^{c-1}-1<2c$$. In this case, omitting the solution of $$c=1$$, we must have $$c=2, 3$$ or $$4$$. Since $$c≤4$$ and $$d≤3$$, but one of $$c,d$$ is 1, we have $$P_2(a!)=c(d+1)≤8$$. But then note that $$P_2(12!)=10$$, so we must then have $$a≤11$$. But then $$p≤a≤11$$, and $$p=7,11$$ are the only possibilities. But $$a!=7^7-7$$ and $$a!=11^{11}-11$$ have no solutions for $$a$$.

Our original assumption that $$(p-1)>4$$ must then be false, so we consider $$a!+p=p^k$$ for $$p=2,3,5$$ and $$p≤a<2p.$$ If $$p=2$$, then $$a=2$$ or $$3$$. We see that $$2!+2=2^2$$ and $$3!+2=2^3$$. Moving on, if $$p=3$$, then $$a=3,4,$$ or $$5$$. From here, we get $$3!+3=3^2$$ and $$4!+3=3^3$$, but $$a=5$$ has no solutions. If $$p=5$$, then $$a=5,6,7,8,$$ or $$9$$. From these, we have $$5!+5=5^3$$ and no other solutions. Thus, the only solutions $$(a,p,k)$$ are $$(2,2,2), (3,2,3), (3,3,2), (4,3,3),$$ and $$(5,5,3).$$

- 2 years, 5 months ago

What a great solution! It captures so many useful ideas.

I likewise solved the problem by looking at powers of $$2$$. However, most of my solution is bounding work, which would have been greatly simplified if I found $$k=p$$. Something I have to keep in mind is $$p-1|k-1$$, which I have seen in another problem involving factorials, but forgot to consider here. Also that bound on $$a!$$ to derive $$n=1$$ takes a bit of intuition; it did not come to my mind though.

- 2 years, 5 months ago

Yeah that's a way I like to sometimes look at odd factorials. In general,

$$(2k-1)!=[k+1][k-1][k+2][k-2]\cdots [k+(k-1)][k-(k-1)]k$$

$$=[k^2-1^2][k^2-2^2]\cdots [k^2-(k-1)^2]k$$

$$<(k^2)^{k-1}k$$

$$=k^{2k-1}$$.

This result is also achievable through AM-GM, but this method allowed for the variation I needed to get the result I was looking for.

- 2 years, 5 months ago