5
$\begingroup$

Given that $N=(x^2-1)(y^2-1)$ where $N,x,y,a,b$ are positive integers, find with proof the smallest value of $N$ such that $N=(x^2-1)(y^2-1)=(a^2-1)(b^2-1)$, where $a$ is not equal to either $x$ or $y$, and likewise for $b$?

In other words, the smallest $N$ for which it cannot be written uniquely in the form $(x^2-1)(y^2-1)$.

You can brute force this question, but that is very laborious to do, and not a pretty solution. I tried using modular arithmetic in some way, like that $N \equiv 0,1 (\mod 3)$, but this doesn't seem to be all that helpful.

Does anyone have any ideas for solving this problem, without using a computer?

$\endgroup$
1
$\begingroup$

An upper bound for the smallest such $N$ can be found as follows: Fix two positive integers $x_1\neq x_2$ and find corresponding $y_1,y_2$ s.t. $(x_1^2-1)(y_1^2-1)=(x_2^2-1)(y_2^2-1)$. This is a Pell-like equation in $y_1,y_2$ with one trivial solution ($y_1=y_2=1$), hence it also has a non-trivial solution (infinitely many, in fact), which can be found using the theory of Pell-type-equations.

Choosing $x_1=2$, $x_2=3$ we get $3y_1^2-8y_2^2=-5$. Let $a=3y_1$, $b=y_2$ to get $$a^2-24b^2=-15$$ to which we know the solution $(3,1)$.

A non-trivial solution to $a^2-24b^2=1$ is $(5,1)$. (In general, you'd want to consult a table to find a non-trivial solution, such as the one on Wikipedia.) Composing both, we find the non-trivial

$$a+b\sqrt{24}=(3+\sqrt{24})(5+\sqrt{24})=39+8\sqrt{24}.$$

(Indeed, $39^2-24\cdot8^2=-15$.)

It follows that

$$(2^2-1)(13^2-1)=(3^2-1)(8^2-1)=504.$$

Finding the smallest such $N$ can now easily be done using a computer, by checking all $n\leq 504$.

Alternatively, note that $(5^2-1)^2>504$, so that any smaller not uniquely representable $N$ has a factor $2^1-1$, $3^2-1$ or $4^2-1$. Because the procedure above gives the smallest possible solution $(y_1,y_2)$ for a given pair $(x_1,x_2)$ (This is a subtle point and needs more clarification; provisionally see the remark at the end), it suffices to repeat the procedure with the pairs $(2,4)$ and $(3,4)$. The results are:

  • $(2,4)$: $3y_1^2-15y_2^2=-12$, or $y_1^2-3y_2^2=-4$; The smallest nontrivial solution to $a^2-3b^2=1$ is $(2,1)$. Composing, we get $(2+\sqrt3)(1+\sqrt3)=11+5\sqrt3$, giving $(2^2-1)(11^2-1)=(4^2-1)(5^2-1)=360$.

  • $(3,4)$: $8y_1^2-15y_2^2=-7$; let $(a,b)=(8y_1,y_2)$: $a^2-120b^2=-56$. The smallest nontrivial solution to $a^2-120b^2=1$ is $(11,1)$. Composing $11+\sqrt{120}$ and $8+\sqrt{120}$ clearly gives a larger $N$ (at least $120^2-1$).

We conclude that the smallest $N$ is $360$.

Note: In general, to guarantee that we found the second smallest solution to a Pell-type equation $x^2-dy^2=a$ it does not suffice to find one primitive solution $z_1$ and compose it with the minimal solution $z_0$ of $x^2-dy^2=1$; as there could be other primitive solutions, in which case the second smallest solution is the second smallest primitive solution, and not the composition of the smallest primitive, $z_1$, with $z_0$. Finding all primitive solutions is a non-trivial task, but upper bounds are known, such as $|y|\leq\frac{z_0+1}{2\sqrt{dz_0}}\sqrt{|a|}$.

$\endgroup$
  • $\begingroup$ A nice idea, but it's not really what I'm looking for; I know the answer already, but I want to prove it without exhausting every single possibility. $\endgroup$ – Cataline Mar 7 '16 at 14:07
  • $\begingroup$ See edit; is $504$ correct according to what you know? $\endgroup$ – punctured dusk Mar 7 '16 at 14:13
  • $\begingroup$ $360=(11^2-1)(2^2-1)=(4^2-1)(5^2-1)$, so $504$ is not the smallest. $\endgroup$ – Cataline Mar 7 '16 at 14:19
  • $\begingroup$ For the $(2,4)$ pair, you should divide by $3$ rather than multiplying, to obtain the equation $y_1^2 - 5 y_2^2 = - 4$ with the nontrivial solution $y_1 = 11, \, y_2 = 5$. $\endgroup$ – Daniel Fischer Mar 7 '16 at 14:42
  • $\begingroup$ The problem with this method is that when looking for all solutions of a Pell-type equation one needs all primitive solutions (which are solutions in $\mathbb Z[\sqrt d]$ $>1$ and $<$ the minimal solution to the corresponding Pell-type equation). For $d=45$ the minimal solution $161+24\sqrt{45}$ is large and indeed there are multiple primitive solutions to $x^2-45y^2=-36$; e.g. $3+\sqrt{45}$; $33+5\sqrt{45}$ (the one we're looking for). As far as I know there's no easy way to get one primitive solution from another, and if we don't find all primitive solutions we can't guarantee minimality. $\endgroup$ – punctured dusk Mar 7 '16 at 14:43

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.