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$?

  • $\begingroup$ As p is odd, x and y can't both be 1. Also x+y will be divisible by p^a and x*y will be close to p^(b-a). I will be surprised if you have any solutions for large p. Can you say something about the solutions you do know, especially for x=1? Gerhard "Likes Learning More About Lagrange" Paseman, 2016.08.25. $\endgroup$ – Gerhard Paseman Aug 25 '16 at 16:14
  • $\begingroup$ Also, ( p^a -1) dividing (p^c +1) has few solutions if any, as this involves (p^a-1) dividing (p^d+1) for some d less than a, for which feasible solutions take us to p even. So I don't expect x to be 1 Gerhard "Assuming I Didn't Mess Up" Paseman, 2016.08.25. $\endgroup$ – Gerhard Paseman Aug 25 '16 at 16:22

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.

  • $\begingroup$ I just realized I did not check if x or y was odd, much less being coprime to p. If all the examples I found resulted in one of them being even, I would be quite surprised. However, I will do another check later and see if I can give some statistics. Gerhard "Needs To Read Fine Print" Paseman, 2016.08.25. $\endgroup$ – Gerhard Paseman Aug 26 '16 at 0:50
  • $\begingroup$ According to my statistics (trial factoring $p^{a+b}+1$ up to $10^6$), the most popular $b$ are 28,68,76,and 64. 28 has primes 3 11 19 43 59 83 107 131 and 139, 68 has those (but 67 and not 131), 76 has those primes of 28 except for 83, and 64 has has those prime of 28 except for 11 and 131. For these values of $b$, $a$ is 1. I checked that $x$ and $y$ were coprime, and found for $p=3$ some factors with $a=3$ or $4$. In spite of my earlier goof, I still maintain the same beliefs regarding the infinity of solutions. Gerhard "Trial Factorization Isn't Chopped Liver" Paseman, 2016.08.26. $\endgroup$ – Gerhard Paseman Aug 26 '16 at 22:15
  • $\begingroup$ Hi Gerhard,Thanks for thinking about this problem and doing some searches. I must admit, though, that I'm having a little trouble keeping track of the calculations that you've done. Would you be able to post some lists of the tuples $(x,y,p,a,b)$ that you have found and that satisfy the constraints of the question? $\endgroup$ – Nick Gill Aug 30 '16 at 8:07

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.

  • $\begingroup$ Sorry for the delay in responding to your answer. Your discussion is reminiscent of something that a friend showed me when I was first thinking about this problem: it seems like the heuristics do point in a certain direction... But I'm all at sea when it comes to thinking about how one might turn this into some kind of proof... $\endgroup$ – Nick Gill Sep 6 '16 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.