12
$\begingroup$

Let $1<m<n$ be two natural numbers. Let us call $(m,n)$ a math.se pair if the prime factors of $m$ are the same as those of $n$ and the prime factors of $m+1$ are the same as those of $n+1$, e.g. $(2,8)$. For every $s\geq 2$, the pair $((2^s-2),2^s(2^s-2))$ is such a pair (for $s=2$ we have the previous pair).

The question I asked myself was: are there other math.se pairs, i.e., math.se pairs not of the form $((2^s-2),2^s(2^s-2))$?

So, I made a fortran program that verifies if $(i,j)$ is a math.se pair for $1<i<j$ and for $1<i\leq m$ and $m<j\leq n$ where $m$ and $n$ are input values, but the only different math.se pair that I (actually, it was the computer) found is $(75,1215)$ (we have that $75=3\cdot5^2$, $1215=3^5\cdot 5$, $76=2^2\cdot19$ and $1216=2^6\cdot19$). The problem is that the greater $i$ or $j$ is, the greater is the time the computer takes.

Now I wonder if that $(75,1215)$ is the only math.se pair not of the form $((2^s-2),2^s(2^s-2))$. If there are others, are there infinitely many of them? If yes, can we list them all?

If you look carefully, you'll see that $(a_s+1)^2=b_s+1$, where $a_s=2^s-2$ and $b_s=2^s(2^s-2)$. With this in mind, I tried to obtain a math.se pair $(a,b)$ that satisfies $(a+1)^3=b+1$. In this case, we need to find a number $b$, such that $b=a^3+3a^2+3a$ and such that $b$ and $a$ have the same prime factors. But even in this case I don't know how to show if there is or if there isn't such a math.se pair.

$\endgroup$
9
  • $\begingroup$ if $b$ and $a$ have same prime factors, then it must mean that any prime factor of $a^2+3a+3$ will divide $a$. So this would mean $a$ is a power of 3. $\endgroup$
    – dezdichado
    Apr 2, 2016 at 4:28
  • $\begingroup$ @dezdichado I can't see why "any prime factor of $a^2+3a+3$ will divide $a$" implies "$a$ is a power of $3$". $\endgroup$
    – Larara
    Apr 2, 2016 at 4:38
  • $\begingroup$ @Larara It does imply that $a^2+3a+3$ is a power of $3$, which assuming $a$ and $b$ have the same prime factors, means $a$ is also a power of $3$. $\endgroup$
    – Erick Wong
    Apr 2, 2016 at 4:46
  • 2
    $\begingroup$ @Larara It's very easy to show that if $p$ divides both $a^2+3a+3$ and $a$ then it also divides $3$. $\endgroup$
    – Erick Wong
    Apr 2, 2016 at 5:53
  • 3
    $\begingroup$ The infinite family and the sporadic pair $\{75, 1215\}$ appear in my article "The ABC's of Number Theory", see Section 6.6 (page 17, numbered 72 in the journal). I report there on a computation that found there were no further examples with $n,n' < 10^8$. See dash.harvard.edu/bitstream/handle/1/2793857/… $\endgroup$ Apr 6, 2016 at 4:20

1 Answer 1

5
+50
$\begingroup$

I asked the same question in 2007 in my paper

Noam D. Elkies The ABC's of number theory. The Harvard College Mathematics Review 1(1): 57-76.

See Section 6.6 (page 17, numbered 72 in the journal). It seems to be a hard question; I'm not aware of any progress on it. [The question arises there as an analogue for integers of a problem on the 1956 Putnam exam, asking that if $P$ and $Q$ are nonconstant polynomials of a complex variable such that $\{ z: P(z)=0 \} = \{ z: Q(z)=0 \}$ and $\{ z: P(z)+1=0 \} = \{ z: Q(z)+1=0 \}$ (without assuming that the zeros have the same multiplicity) then $P$ and $Q$ are the same polynomial.]

As I reported in that paper, the infinite family $\{2^s-2, 2^s(2^s-2\}$, together with the sporadic example $\{75, 1215\}$, are the only solutions up to $10^8$. If you allow negative $m,n$ as well then there is a second infinite family $\{2^s+1, -(2^s+1)^2\}$ and a second sporadic example, $\{35, -4375\}$, and no examples up to $\pm 10^8$ other than those and their images under the involution $\{m,n\} \leftrightarrow \{-1-m,-1-n\}$.

I have now checked that for positive $m,n$ there are no further solutions with $m,n < 10^9$, nor with $m,n < 10^{16}$ under the further condition that the radicals $\prod_{p|m} p$ and $\prod_{p|n} p$ both be smaller than $10^6$. Such calculations are feasible because it is not necessary to try all pairs in the respective range. One strategy to find all solutions with radicals up to $R$ and $m,n \leq H$ is as follows:

for each r up to R:
   factor r;
   list all m up to H with radical r;
   for each such m, factor m+1 and record its radical;
   sort the resulting list of radicals of m+1;
   for each consecutive pair in the sorted list of radicals:
      if they are equal, print the corresponding pair of values of m.

Doing this for $(R,H) = (10^6, 10^{16})$ produced the following list (each row of output lists $r$ as well as the pair of $m$'s):

2[2, 8]
6[6, 48]
14[14, 224]
15[75, 1215]
30[30, 960]
42[126, 16128]
62[62, 3968]
254[254, 65024]
510[510, 261120]
1022[1022, 1046528]
2046[2046, 4190208]
2730[8190, 67092480]
4094[4094, 16769024]
16382[16382, 268402688]
32766[32766, 1073676288]
58254[524286, 274876858368]
65534[65534, 4294836224]
131070[131070, 17179607040]
262142[262142, 68718952448]
419430[2097150, 4398042316800]
599186[4194302, 17592177655808]

In this range only the pair [75, 1215] is not of the form $\{2^s-2, 2^s(2^s-2\}$. (Those pairs don't appear in order of increasing $s$ because some $2^s-2$ are not squarefree.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .