For a positive integer $n$, let $P(n)$ be the set of distinct prime divisors of $n$. We are looking for pairs of numbers $A,B$ such that $P(A)=P(B)$ and $P(A+1)=P(B+1)$. The pair $A=2$, $B=8$ is a simple example.

There are infinitely many such pairs given by $A=2^m-2$ and $B=2^mA$, for any integer $m>1$. (this is how I solved a problem asking whether there exist infinitely many such pairs. I'm pretty sure the problem was in one of the Miklós Schweitzer competitions, but I can't for the life of me find it now).

Another "sporadic" solution is given by $A=75=3\times 5^2, B=1215=3^5\times 5$. Miraculously, $A+1=2^2\times 19$ and $B+1 = 2^6 \times 19$. I'm unable to fit this coincidence into an infinite family of solutions.

Questions: Are there any additional pairs? Can we prove that there aren't any? Can we at least prove that there are only finitely many such pairs, except for the infinite family I mentioned?

  • $\begingroup$ I think that Catalan's conjecture (which has been proved) states that no such pairs exist where $P(A)=P(B)=\{2\}$ and $P(A+1)=P(B+1)=\{3\}$. In fact, it states an even stronger claim, according to which, there is only a single value of $A$ such that $P(A)=\{2\}$ and $P(A+1)=\{3\}$. But all of this answers your question only for two given sets of primes (namely, $\{2\}$ and $\{3\}$). $\endgroup$ – barak manos Nov 30 '15 at 6:04
  • $\begingroup$ @barak Yes, for me the surprise of this question is that there are actually infinitely many such pairs, in contrast with things like Catalan. It "almost feels like" a violation of ABC, but of course it's not. $\endgroup$ – Alon Amit Nov 30 '15 at 6:05
  • $\begingroup$ For $A,B\le 10^6$, the only "sporadic solution" is the one mentioned in the question. $\endgroup$ – Peter Nov 30 '15 at 12:12

Your Answer

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

Browse other questions tagged or ask your own question.