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

No vote yet
1 vote

Comments

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:

\(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).\) Anthony Kirckof · 10 months, 3 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 · 10 months, 2 weeks 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\)

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

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...