Waste less time on Facebook — follow Brilliant.

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
8 months, 2 weeks ago

No vote yet
1 vote


Sort by:

Top Newest

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:




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!≤[p^2-(p-1)^2][p^2-(p-2)^2]⋯[p^2-2^2 ][p^2-1^2]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:



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


Case 2: \(d=1\). We then have:



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


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!)\):


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


Moving on, we have:








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).\) Anthony Kirckof · 8 months, 2 weeks ago

Log in to reply

@Anthony Kirckof 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. Xuming Liang · 8 months ago

Log in to reply

@Xuming Liang 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\)



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. Anthony Kirckof · 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...