31
$\begingroup$

Problem

Prove or disprove that, for any $n \in \mathbb{N_+}$, there exist $a,b \in \mathbb{N_+} $ such that $$\frac{a^2+b}{a+b^2}=n.$$

My Thought

Assume that the statement is ture. Then, the equality is equivalent to that

$$a^2-na+b-nb^2=0.$$

Regard it as a quadratic equation with respect of $a$.Then $$a=\dfrac{n \pm \sqrt{n^2+4nb^2-4b}}{2}.$$ Thus, $n^2+4nb^2-4b$ must be a square number. Let $$n^2+4nb^2-4b=k^2,k \in \mathbb{N_+}.$$ How to go on with this? May it work?

P.S.

The statement seems to be true. Here are parts of verification examples: \begin{array}{r|r|r} n&a&b \\ \hline 1&1&1\\ 2&5&3\\ 3&5&2\\ 4&10&4\\ 5&27&11\\ 6&69&27\\ \vdots&\vdots&\vdots \end{array}

Besides, the equation could be rewritten as

$$n(2a-n)^2-(2nb-1)^2=n^3-1,$$

which is a $\textbf{ Pell-like equation}$. This will help?

$\endgroup$
17
  • 5
    $\begingroup$ Computer search confirms the conjecture for $1 \leq n \leq 100$, though the requisite values of $a$ and $b$ can be very large (for example, $n=54$ gives $(a,b) = (9\,683\,509, 1\,317\,755)$ and $n=89$ gives $(a, b) = (22\,276\,589, 2\,361\,309)$). I've looked for useful patterns but can't find any, except for a vague tendency to have $a \equiv b \bmod 2$ for larger $n$ (it holds for 28 out of the 40 integers $60 \leq n \leq 99$). It can greatly accelerate computer searches to note that $a/\sqrt{n} - b$ is positive but never more than about $10$. $\endgroup$ May 31 '18 at 15:21
  • 5
    $\begingroup$ Where did you get this problem? $\endgroup$ May 31 '18 at 17:23
  • 2
    $\begingroup$ @user477343 If $k$ is a square number, then $ k\equiv 0,1\pmod 4$. That's true! But you can't reason like this: since $ k\equiv 0,1\pmod 4$,then $k$ is a square number. For counterexample, $17 \equiv 1\pmod 4$,but it's not a square number at all. Right,sir? $\endgroup$ Jun 1 '18 at 0:48
  • 4
    $\begingroup$ I've confirmed the conjecture for $n \leq 200$ (going much further runs into limits on 64-bit integer arithmetic). Solutions (listed in the form $n, a, b$) are here: pastebin.com/L1b1bqJT $\endgroup$ Jun 1 '18 at 17:38
  • 5
    $\begingroup$ Apparently this is due to Zhining Yang see oeis.org/A290332 $\endgroup$ Jun 4 '18 at 21:17
10
$\begingroup$

Proof for all non-quadratic $n$

Lemma: Pell's equation $x^2-n y^2 = 1$, with $n$ not being a perfect square, has infinitely many solutions such that $x$ is odd, $y$ is even and $x\equiv1$ (mod $2n$).

Proof: It's a well known fact that the Pell's equation with non-quadratic $n$ has an inifinite number of solutions. Pick any such solution $(x_1,y_1)$. It's worth noticing that $x_1$ and $y_1$ must be co-prime as well as $x_1$ and $n$.

Now calculate:

$$x_2=x_1^2+ny_1^2,\quad y_2=2x_1y_1$$

It can be easily proved that $(x_2,y_2)$ is also a solution of the same Pell's equation. Obviously $y_2$ is even.

If you replace $x_1^2=ny_1^2+1$ into the expression for $x_2$ you get:

$$x_2=1+2ny_1^2\implies x_2\equiv1\space (\text{mod}\space 2n)$$

This also proves that $x_2$ has to be odd (which makes perfect sense because solutions of Pell's equation are always co-prime and $y_2$ is even).

You can construct more solutions of Pell’s equation in the same way and they all satisfy the criteria of the lemma. So there is not just one such solution. Actually there are infinitely many.

End of lemma proof

Back to the original equation (same approach as HERE):

$$\frac{a^2+b}{a+b^2}=n$$

can be rewritten as:

$$u^2-nv^2=1-n^3 \tag1$$

where:

$$u=2nb-1,\quad v=2a-n$$

Take $x,y$ such that:

$$x^2-ny^2=1\tag2$$

You can easily prove that $(-x+y n^2)$ and $(-y+nx)$ satisfy (1):

\begin{align*}(-x+ yn^2)^2-n(-y+nx)^2&=x^2-2xyn^2+y^2n^4-ny^2+2xyn^2-x^2n^3\\&=(x^2-ny^2)+n^3(ny^2-x^2)\\&=1-n^3.\end{align*}

This shows that:

$$u=-x+yn^2=2nb-1$$

$$v=-y+xn=2a-n$$

...represent a solution of $(1)$.

Hence,

$$a=\frac{(x+1)n-y}{2},\space b=\frac{yn^2-(x-1)}{2n}.\tag3$$

According to our lemma Pell's equation has infinitely many solutions $x,y$ such that $x$ is odd, $y$ is even and $x\equiv1$ (mod $2n$). Replace these solutions into (3) and you'll obviously get infinitely many integer values for $a,b$.

End of proof for all non-square $n$.

The following simple Mathematica script will generate single $a,b$ for fairly big non-square $n$ very fast (it follows the proof, word by word):

ABPair[n_] := Module[
   {x, y, a, b, a1, b1, a2, b2},
   pellSolutions = Solve[x^2 - n  y^2 == 1, {x, y}, Integers] /. C[1] -> 1;
   pellSolutions = {x, y} /. pellSolutions;
   {a1, b1} = First[Select[pellSolutions, #[[1]] > 0 && #[[2]] > 0 &, 1]];
   {a2, b2} = If[Mod[a1, 2 n] == 1 && Mod[b1, 2] == 0, {a1, b1}, {a1^2 + n b1^2, 2 a1 b1}];
   a = (n (a2 + 1) - b2)/2;
   b = (b2 n^2 - a2 + 1)/(2 n);
   {a, b, (a^2 + b)/(b^2 + a)}
];

For example:

ABPair[5613]
{60584278414870816497213, 808653403020126409200, 5613}

The third number is just a check that the calculated numbers are valid. In other words:

$$\frac{60584278414870816497213^2+808653403020126409200}{60584278414870816497213+808653403020126409200^2}=5613$$

The script is lightning fast even for $n$ with 12 digits:

ABPair[561044335534]

See Sil's solution for quadratic $n$. Case closed :)

$\endgroup$
6
  • 1
    $\begingroup$ I have question for only one part: if your initial solution has $x_0\equiv 1 \pmod n$ it looks like this might not work. Since $x_{i+1} \equiv x_i^2 \pmod n$ this results in $x_k \equiv 1 \pmod n$ for all $k$. (The other update formula also gives $x_k \equiv x_i x_j \equiv 1 \pmod n$. Then $b = (yn/2) + (x+1)/(2n)$ which is not an integer for $n>2$ since $x+1 \equiv 2 \pmod n$. This can happen for example by taking $(x_0,y_0) = (161,72)$ for the equation $x^2-5y^2=1$. $\endgroup$ Jun 14 '18 at 5:25
  • $\begingroup$ You are perfectly right, let me think about that. $\endgroup$
    – Oldboy
    Jun 14 '18 at 7:00
  • $\begingroup$ I also noticed that using $-x$ instead of $x$, i.e. $$a = \frac{(-x+1)n+y}{2}, b = \frac{-x+1 + yn^2}{2n}$$ would still give a solution and always works by your construction, but the problem is now it looks like $a < 0$. Perhaps some small adjustments can fix the argument. $\endgroup$ Jun 14 '18 at 7:13
  • $\begingroup$ Yes, that was exactly my plan how to fix the proof. it should work either for $x_k\equiv1$ or $x_k\equiv-1$ But some solutions could be negative. I think this can be tweaked. Bigger concern is how to prove this for square $n$ - looks like a simpler case but so far - no luck. $\endgroup$
    – Oldboy
    Jun 14 '18 at 8:37
  • 1
    $\begingroup$ @YongHaoNg: I think this is now rock solid for all non-quadratic $n$. $\endgroup$
    – Oldboy
    Jun 15 '18 at 10:22
8
$\begingroup$

Solution for non-square $n$ is provided in @Oldboy's answer and in linked questions. This answer handles the case for square $n$.

Case 1: $n=k^2,k \equiv 0 \pmod {2}$

Choose \begin{align} a=\frac{k^2(k^3+2)}{4}, b=\frac{k^4}{4}. \end{align}

Conditions imply that $k^2 \equiv 0 \pmod {4}$ and so both $a$ and $b$ are integers. By algebraic manipulation we can show that $(a^2+b)/(b^2+a)=k^2=n$ (it is quite technical).

Case 2: $n=k^2,k \equiv 1 \pmod {2}$

Choose

\begin{align} a=\frac{(k^2+1)(k^2-k+2)}{4}, b=\frac{(k-1)(k^2+1)}{4}. \end{align}

Here $2 \mid k^2+1$ and $2 \mid k^2-k+2$ implies $a$ is an integer and similarly $2 \mid k-1$, $2 \mid k^2+1$ for $b$. Again it can be verified that $(a^2+b)/(b^2+a)=k^2=n$.

This result is obtained by mindless following of solution of quadratic diophantine equation on https://www.alpertron.com.ar/QUAD.HTM. Basically for square $n$ and our equation the site instructs us to find $(X-\sqrt{n}Y)(X+\sqrt{n}Y)=4n(n^3-1)$ such that $4n \mid Y+2$ ($2$ being calculated there as $\beta$ and $4n$ being a determinant). So the problem is essentially to look at divisors $d$ of $4n(n^3-1)$ that satisfy above divisibility criteria. For $n=k^2$ the factorization is $2\cdot2\cdot(k-1)k^2(k+1)(k^2-k+1)(k^2+k+1)$ (not into primes, but fortunately this is enough). So by testing combinations of these factors (using Maple e.g.), it turns out that choices of $d=2k$ and $d=2k(k+1)$ work (for even and odd $k$ cases respectively, that is). Those choices when substituting all the way back simplify to the cases described above, but it is too long/technical to get there...

$\endgroup$
2
  • $\begingroup$ This looks like a lot of hard work to me. How many solutions did you pick from the site before you very actually able to spot the pattern? $\endgroup$
    – Oldboy
    Jun 16 '18 at 20:46
  • 1
    $\begingroup$ @Oldboy It was quite long for a comment, edited the answer instead. It's not that hard if one uses CAS system for help. $\endgroup$
    – Sil
    Jun 16 '18 at 21:19

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.