I am reading at a paper about all integers $x$ such that $x^2-1$ has only prime factors smaller than $100$ (Luca and Najman).

My problem is that it is not obvious to me that the number of $x$ would be finite. I get the feeling the authors think it is too simple to be explained, but I still wonder if someone might do me a favor of demonstrating it to me.

  • 1
    $\begingroup$ I think this is this paper: math.leidenuniv.nl/~fnajman/FLFNMC.pdf $\endgroup$ – miracle173 Feb 27 '14 at 17:49
  • 1
    $\begingroup$ @miracle173, you are right that the paper explains why there is a finite number only. And that is presumably the paper OP is referencing. $\endgroup$ – vonbrand Feb 27 '14 at 17:59
  • $\begingroup$ You are probably both right, it is in any case the article I am referring to. My problem is probably just that, as an amateur, I need some extra steps in the proof. $\endgroup$ – Mikael Jensen Feb 28 '14 at 10:02

I gave the issue some additional thought, using Pell’s equation for fixed d in the equations below (you might want to check the proof):

Using Brahmagupta’s technique, we can combine two Pell’s equations $((x_1)^2-d(y_1)^2)=1$ and $((x_2)^2-d(y_2)^2)=1 $ to get $((x_1)^2-d(y_1)^2)((x_2)^2-d(y_2)^2)=((x_1)(x_2)+d(y_1)(y_2))^2 - d((x_1)(y_2+(x_2)(y_1))^2$

The second lowest solution whose x component we now call $x_2$ can be achieved by combining the first solution with itself to get the first higher solution $(x_2,y_2,d)$ and get $x_2=2x_1^2-1 $ (using the substitution $d(y_1)^2)= (x_1)^2-1 $, and $y_2=2(x_1)(y_1)$.

We observe that $ (x_2)^2-1=(2x_1^2-1)^2-1=$ and $4(x_1)^2 ((x_1)^2-1) =d(y_2)^2=d(2(x_1)(y_1))^2$.

The LHS in the last equation contains the factor $ (x_1)^2-1$. This implies that this factor ($ (x_1)^2-1$ ) does not contain any of the primes making up $x_1$ since $(x_1)^2-1=-1$ (mod p) for all the primes p in x.

If $x_2$ is combined with $x_1$ we get the third lowest solution $x_3$: $ (x_3)^2-1= d(y_3)^2= (x_3)^2-1= ((x_1)*(x_2)+d*(y_1)*(y_2))^2-1=((x_1)*(2*(x_1)^2-1)+d*(y_1)*(2(x_1)*(y_1)))^2-1 $

so that $ (x_3)^2-1$ equals a constant $C(x_1)-1$. As above, this shows that all successive values of x for the chosen d must contain new primes. Since d also is subject to the same limitation being part of $(x_3)^2-1$ there must be a limited number of x, such that $x^2-1$ contains a limited number of primes. (I have used– without proof – the fact that the combination process yields all possible solutions of Pell’s equation for a given d. I realise it may have been more elegant using $x ± \sqrt{d}y$).

Edit: I now see that the second part of the proof only tells us that higher combinations are different from the nearest lower - the fact that y's highest prime factor increases for increasingly higher combinations (as they do), does not follow from the proof, as I first thought.

  • $\begingroup$ Perhaps you could use x_1 and \sqrt{d} to improve the readability. $\endgroup$ – Bart Michels Mar 7 '14 at 16:30
  • $\begingroup$ Thank you. I would be fully educated - since I only use modest equations - if I also knew how to write x^(n+1) the right way. The dollar sign will not do the trick. $\endgroup$ – Mikael Jensen Apr 1 '14 at 20:51
  • $\begingroup$ You can use curly braces like {} to group things. For example, x^{n+1} or x_{n+1}. $\endgroup$ – Bart Michels Apr 2 '14 at 14:51
  • $\begingroup$ Thank you, this completes my education but I just have to test: $\endgroup$ – Mikael Jensen Apr 4 '14 at 21:46
  • $\begingroup$ Thanks.I just have to test: $1^{2+3}$ - I've got it! $\endgroup$ – Mikael Jensen Apr 4 '14 at 21:48

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.