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

Question

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!.

Answer 1

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<p$.

Answer 2

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).