Some equalities involving prime powers

Question

Let $p,a,b,x,y$ be positive integers where $p$ is an odd prime; $x$ and $y$ are odd; $p,x$ and $y$ are all coprime. I'm interested in finding examples of such numbers that satisfy this equation: \begin{equation}\label{e:a} p^a.x.y - x - y = p^b.\end{equation} Notice that you can rewrite this equation as follows: $$(xp^a-1)(yp^a-1) = p^{a+b}+1.$$

1. First line of inquiry: let's fix $b$ and consider what solutions might be possible. It has been suggested to me that there are likely to be many (an infinite number?) of examples with $a>1$, but for $a=1$ perhaps only a finite number. Can anyone give me a proof/ reference/ counter-example for this assertion?

2. Second line of inquiry: for the application I have in mind, I'd be very interested in lower bounds on the number $b$ in terms of the prime $p$. Is it possible that such a lower bound exists? And, if so, what might its form be?

3. Third line of inquiry: in light of the second displayed equation above, one might also consider the following question:

   Given $a>1$, $c>2a$, are there only finitely many primes $p$ such that $p^c+1$ has a factor congruent to $-1$ modulo $p^a$?

Answer 1

EDIT 2016.08.25 So I paid more attention to the conditions, fixed some bugs, and found solutions more in line with the problem. (However, I have not added code to guarantee coprimality between any two of $x$, $y$, and $p$ yet.) In particular, one must have $p = 3 \bmod 4$ and $a+b$ is odd. Using small primes up to 400000 for trial factorization and testing exponents up to 60, as well as ensuring that both factors were even, I found factorizations for $p^{a+b} + 1$ where both factors were even and the easier one was $-1 \bmod p$, for primes 3,11,19,43,59,67,83,107,131,139,163,179, and others. Possibly there are exponents for bases 7,23,31,47,71,79, etc., but my search was rather limited. $a+b=9$ worked for many $p$, including 11,43,59,67, and 179. I am still confident there are many solutions for $a=1$.

For $a=2$ I found solutions for 3,11,19,59, 67, and other primes . I will report on $a=3$ later in a comment. I apologize for the goof below. While I still believe there are infinitely many solutions for a fixed b, my evidence is weaker than before. I think $a+b=45$ will have solutions for many primes. END EDIT 2016.08.25

I decided to run a computer program to convince myself of the paucity of examples, without fixing $b$. So, for many small odd primes $p$ and small exponents $c$, partially factor $p^c+1$ and stop when you find a divisor which is $-1 \bmod p$ for some $c$. For simplicity I am doing trial division with small primes.

Well. Just trial dividing with primes below $60000$, and exponents below $100$, I am finding example exponents with such divisors for every odd prime base $\lt 1000$ except 503, 719, and 823. If I did trial factorization with more primes I might find exponents for those bases also. So for $a=1$ I believe there are not only finitely many examples. Since an example for $a \gt 1$ is also an example for $a=1$, I think you have something confused in the post at the time of this writing. Of course, I am not fixing $b$ as you are, but still.

Of course, if $p^e+1$ has such a factor congruent to $-1 \bmod p^a$, then so does $p^{ek} +1$ for any odd positive integer $k$, and the question now becomes how big do you want $a$ to be. Running the program for $a=2$ I get no small examples for 31,71,97 and more primes, but it looks like I could fix that by improving the trial divisor bound. For $a=3$ my limited search does not find examples with the base being 13 or 19 or lots of other primes; if you have more CPU cycles you can probably find examples for those bases.

If you have fixed $b$, note that algebraic factorization can play a role especially when $a+b$ is 'more composite than usual'. Unless you have further specifications on $b$, my guess is you can find plenty of $p$ with the right choice of $a$.

Gerhard "Maybe Factoral Abundance Helps Here" Paseman, 2016.08.25.

Answer 2

Heuristically, a number the magnitude of $p^c+1$ would seem to have a probability $\ll1-\left(1-\frac{1}{p^a}\right)^{\tau(p^c+1)}\ll1-\left(1-\frac{1}{p^a}\right)^{p^{\epsilon c}}\ll \frac{1}{p^{a-\epsilon c}}$ of at least one factor being a fixed residue modulo $p^a$ if the factors are independent modulo $p^a$ (however they aren't). Taking into account that they aren't, and choosing the distinct prime factors modulo $p^a$ one at a time, one rough way of estimating might yield $1-\prod_{i=1}^{\omega(p^c+1)}\left(1-\frac{a_i}{p^a}\right)$ for the probability, each $a_i$ being the number of new residue classes the $i$-th distinct prime factor $p_i$ needs to avoid to prevent any factor made by choosing $p_i$ being in the fixed residue class. Eg. for a number $n=\prod_{i=1}^{\omega(n)}p_i^{e_i}$, let $a_i=(\prod_{j=1}^{i-1}(e_j+1))e_i$, so $\sum_{i=1}^{\omega(n)}a_i=\tau(n)-1$. Such a heuristic would then suggest a finite number of primes $p$ such that at least one factor of $p^c+1$ is in a given residue class modulo $p^a$ when $a>1$. It is not clear how well the heuristic estimates the actual behaviour.