Analyzing a Diophantine equation: $A^k + 1 = B!$ Efficient way to solve.

I came across a Diophantine equation which has this form:

$$A^k + 1 = B!$$

Where we are given $$A$$ and need to find $$(k,B) \in \mathbb{N}^2$$ (Note, $$0 \notin \mathbb{N}$$ in this case), such that this equation is satisfied.
I started to analyze this and these are my observations:

$$1) ~~ \text{If} ~~ B \geq A$$ then $$A \mid B$$, so $$B = A\cdot t$$ for some natural $$t$$. $$A^k + 1 = A \cdot t$$. Looking at $$\mod(A)$$ we get that the $$\text{LHS}$$ is congruent to $$1 \mod(A)$$ while the $$\text{RHS}$$ is congruent to $$0 \mod(A)$$, thus no solutions exist.

$$2) ~~ \text{If} ~~ B < A$$ then we have two sub-options:

$$~~~~~~ 2.1)$$ We might be able to solve by checking each value one-by-one ($$2 \leq B < A$$) which may not be a lot. $$B=1$$ isn't a solution because then we would have: $$A^k = 0$$ which does not have a solution.

$$~~~~~~ 2.2)$$ If $$B$$ is a solution then: $$B \mid A^k + 1, ~~ B-1 \mid A^k + 1, ~~ \dots ~~, 2 \mid A^k + 1$$ Meaning $$A^k +1$$ should be divisible by any number between $$2$$ and $$B$$

Another observation is that if $$A$$ is even, then $$A = 2w$$ for some natural $$w$$, and also $$B \geq 2$$, then no solutions exist, because, $$B \geq 2$$ and thus even, however the $$\text{LHS}$$ will be odd: $$\text{Even}^{\text{k} + 1} = \text{Even} + 1 = \text{Odd}$$.

However, when $$A$$ is odd, meaning that $$A = 2w+1$$ for some natural $$w$$, then nothing helps and the only choice I see here is to check one-by-one, but, the gap between $$2$$ and $$A$$ can be big and potentially infinite. For example: $$99^k + 1 = B!$$

Do we need to check each number $$2 \leq B \leq 98$$ ? Is there a better way to approach this? I would like to hear if you have more observations I missed, Thank you!.

• In the case $99^k+1=B!$, clearly $B>3$, so $99^k$ and $B!$ are divisible by $3$, a contradiction, - no solution. Sep 28, 2020 at 22:45
• If $p$ is a prime factor of $A$, then $p \nmid B!$, so $B$ is smaller than the smallest prime factor of $A$. Sep 28, 2020 at 22:47
• In general if $p$ is the smallest prime dividing $A$, then $B$ must be $<p$. So it is best to assume that $A$ is prime, $B<A$. For example $97^k+1=B!$. That equation also has no solution (use $\mod 4$). Sep 28, 2020 at 22:49
• Moreover, if $k$ is odd then $A^k+1$ is divisible by $A+1$, so every prime $p$ dividing $A+1$ satisfies $p\leq B$. That is to say $A+1$ is $B$-smooth and $A$ is $B$-rough. Sep 29, 2020 at 12:18
• Also $p-1$ does not divide $k$, for every odd prime $p\leq B$, as otherwise $$A^k+1\equiv2\pmod{p}.$$ Then checking a few small values of $B$ for solutions, it quickly follows that $k$ must be astronomically large. Sep 29, 2020 at 12:24

Given a positive integer $$A$$, if $$k$$ and $$B$$ are positive integers such that $$A^k+1=B!,$$ it is clear that $$A^k$$ and $$B!$$ are coprime. Then also $$A$$ and $$B!$$ are coprime, and so $$B$$ is strictly smaller than the smallest prime factor of $$A$$. If $$A$$ is not too large, an effective approach is to determine the smallest prime factor of $$A$$, and then simply try all values of $$B$$ up to that prime. In particular, for your example with $$A=99$$ we see that the smallest prime factor is $$3$$, so we only need to try $$B=2$$ to see that there are no solutions.

Note that if you intend to test this for many values of $$A$$, it may be worth while to verify that $$B!-1$$ is not a perfect power for any small value of $$B$$. (Thanks to Peter in the comments $$B!-1$$ is not a perfect power if $$B\leq10^4$$.)

Some more general results: A quick check shows that every solution with $$B\leq3$$ is of the form $$(A,k,B)=(1,k,2)\qquad\text{ or }\qquad(A,k,B)=(5,1,3).$$ For $$B\geq4$$ we have $$A^k=B!-1\equiv7\pmod{8}$$ and so $$k$$ is odd and $$A\equiv7\pmod{8}$$. Then $$B!=A^k+1=(A+1)(A^{k-1}-A^{k-2}+A^{k-3}-\ldots+A^2-A+1),$$ which shows that $$A+1$$ divides $$B!$$, so in particular $$A+1$$ is $$B$$-smooth. So for every prime $$p$$ dividing $$A$$ and every prime $$q$$ dividing $$A+1$$ we have $$q\leq B.

• For $3\le B\le 10^4$ , $B!-1$ is not a perfect power. Sep 29, 2020 at 12:46

Probably there are no nontrivial solutions. JCAA and Chappers in the comments have mentioned another obstruction: if $$p \mid A$$ is prime then $$A^k + 1 \equiv 1 \bmod p$$ so $$p \nmid B!$$, which means $$B < p$$. So $$A$$ should have no small prime factors (hence not only odd but not divisible by $$3$$ and so forth), and $$B \le A-1$$.

Similarly, if $$p$$ is an odd prime and $$A \equiv 1 \bmod p$$ then $$A^k + 1 \equiv 2 \bmod p$$ so $$p \nmid B!$$, which again means $$B < p$$. So $$A - 1$$ should also have no small prime factors, and $$B \le \frac{A-1}{2}$$ (since $$A$$ is odd, $$A-1$$ is even).

Ignoring solutions where $$k = 1$$ ("trivial" solutions), we can also check that $$B! - 1 = 0, 1, 5, 23, 119, 719, 5039$$ for $$B = 1, 2, 3, 4, 5, 6, 7$$ is never a perfect power, so we can assume that $$B \ge 8$$, which means that the prime factors of $$A$$ and $$A-1$$ (other than $$2$$ for $$A-1$$) must be at least $$11$$. We can get more precise information by working modulo a few small prime powers. Below we'll repeatedly use the following lemma: if $$\gcd(k, \varphi(n)) = 1$$ then $$x \mapsto x^k$$ is a bijection $$\bmod n$$, or equivalently $$k^{th}$$ roots $$\bmod n$$ exist and are unique.

• $$\bmod 3$$ we have that if $$B \ge 3$$ then $$A^k + 1 \equiv 0 \bmod 3$$, so $$A^k \equiv -1 \bmod 3$$. If $$k$$ is even this is impossible, so $$k$$ must be odd (this will turn out to be very helpful), and $$A \equiv -1 \bmod 3$$.
• $$\bmod 2^7$$ we have that if $$B \ge 8$$ then $$A^k + 1 \equiv 0 \bmod 2^7$$, so $$A^k \equiv -1 \bmod 2^7$$. Since $$k$$ is odd, it's invertible $$\bmod \varphi(2^7) = 2^6$$, which gives $$A \equiv -1 \bmod 2^7$$.
• $$\bmod 5$$ we have that if $$B \ge 5$$ then $$A^k + 1 \equiv 0 \bmod 5$$, so $$A^k \equiv -1 \bmod 5$$. Since $$k$$ is odd, it's invertible $$\bmod \varphi(5) = 4$$, which gives $$A \equiv -1 \bmod 5$$.
• $$\bmod 7$$ we have that if $$B \ge 7$$ then $$A^k + 1 \equiv 0 \bmod 7$$, so $$A^k \equiv -1 \bmod 7$$. If $$3 \nmid k$$ then $$k$$ is invertible $$\bmod \varphi(7) = 6$$ which gives $$A \equiv -1 \bmod 7$$; if instead $$3 \mid k$$ then $$A \equiv -1, -2, 3 \bmod 7$$.

This is a lot of constraints on $$A$$. The constraints working $$\bmod 2^7, 3, 5$$ give that $$A \equiv -1 \bmod 1920$$ and the additional constraint $$\bmod 7$$ gives that if $$3 \nmid k$$ then

$$A \equiv -1 \bmod 13440$$

and if $$3 \mid k$$ then

$$A \equiv -1, 3839, 5759 \bmod 13440.$$

Since $$k$$ is odd we also have $$k \ge 3$$ so this gives $$A^k + 1 \ge 3839^3 + 1 = 56578878720$$ which gives $$B \ge 14$$, hence $$A^k + 1 \equiv 0 \bmod 11, 13$$ which imposes further constraints $$A \bmod 11, 13$$. It's slightly annoying to spell out what these are in general but we don't have to: $$11 \mid 3839$$ so that rules out $$A = 3839$$, and $$13 \mid 5759$$ so that rules out $$A = 5759$$ also.

This gives $$A \ge 13439$$ which gives $$B \ge 16$$, and we can probably continue like this for some time (although not forever). $$B \ge 16$$ implies that $$A^k \equiv -1 \bmod 2^{15}$$ which as above gives $$A \equiv -1 \bmod 2^{15}$$ so now we have

$$A \equiv -1 \bmod 2^{15} \cdot 3 \cdot 5 = 491520$$

which gives $$B \ge 19$$. This gives $$A \equiv -1 \bmod 2^{16}$$ and also (since $$\varphi(17) = 16$$ is a power of $$2$$) $$A \equiv -1 \bmod 17$$, so

$$A \equiv -1 \bmod 2^{16} \cdot 3 \cdot 5 \cdot 17 = 16711680$$

which gives $$B \ge 23$$ which gives

$$A \equiv -1 \bmod 2^{19} \cdot 3 \cdot 5 \cdot 17 = 133693440$$

which gives $$B \ge 25$$ which gives

$$A \equiv -1 \bmod 2^{22} \cdot 3 \cdot 5 \cdot 17 = 1069547520$$

which gives $$B \ge 27$$ which gives

$$A \equiv -1 \bmod 2^{23} \cdot 3 \cdot 5 \cdot 17 = 2139095040$$

which, finally, does not improve the lower bound on $$B$$. At this point $$27! \mid B!$$ is divisible by many primes and many powers of primes which gives other bounds on $$A$$ (and constraints on $$k$$) but things split into cases from here. For example either $$5 \mid k$$ or $$A \equiv -1 \bmod 11$$, and similarly either $$11 \mid k$$ or $$A \equiv -1 \bmod 23$$.

Again, probably there are no nontrivial solutions. The abc conjecture gives that for any $$\epsilon > 0$$ there is a constant $$K_{\epsilon}$$ such that

$$A^k + 1 = B! < K_{\epsilon} \text{rad}(A^k B!)^{1 + \epsilon} = K_{\epsilon} \text{rad}(A \prod_{p \le B} p)^{1 + \epsilon}$$

where the RHS notably does not depend on $$k$$ and the product $$\text{rad}(B!) = \prod_{p \le B} p$$ of all primes less than or equal to $$B$$ grows something like $$\exp(\pi(B)) \approx \exp \left( \frac{B}{\log B} \right)$$. With a reasonably small value of $$K_{\epsilon}$$ even for $$\epsilon$$ as large as $$\frac{1}{3}$$ this should rule out solutions for $$k \ge 3$$ and sufficiently large $$A$$ (and surely the bounds we've proven make $$A$$ sufficiently large by now).