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

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 $Bleq10^4$.)

Some more general results: A quick check shows that every solution with $Bleq3$ is of the form
$$(A,k,B)=(1,k,2)qquadtext{ or }qquad(A,k,B)=(5,1,3).$$
For $Bgeq4$ we have $A^k=B!-1equiv7pmod{8}$ and so $k$ is odd and $Aequiv7pmod{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 $qleq B<p$.

Leave a Comment