# $N=(x^2-1)(y^2-1)$ has more than one solution

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?

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|}$.

• 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. – Cataline Mar 7 '16 at 14:07
• See edit; is $504$ correct according to what you know? – punctured dusk Mar 7 '16 at 14:13
• $360=(11^2-1)(2^2-1)=(4^2-1)(5^2-1)$, so $504$ is not the smallest. – Cataline Mar 7 '16 at 14:19
• 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$. – Daniel Fischer Mar 7 '16 at 14:42
• 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. – punctured dusk Mar 7 '16 at 14:43