MHB Find all non-negative integers (x,y)

[anemone]

Find all paris $(x,\,y)$ of non-negative integers for which $x^2+2\cdot 3^y=x(2^{y+1}-1)$.

 

[anemone]

Solution of other:

Spoiler

For fixed values of $y$, the original equation is a simple quadratic equation in $x$. For $y\le 5$, the solutions are listed below:

[TABLE="class: grid, width: 500"]
[TR]
[TD]Case[/TD]
[TD]Function[/TD]
[TD]Discriminant[/TD]
[TD]Integer Roots[/TD]
[/TR]
[TR]
[TD]$n=0$[/TD]
[TD]$x^2-x+2=0$[/TD]
[TD]$-7$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=1$[/TD]
[TD]$x^2-3x+6=0$[/TD]
[TD]$-15$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=2$[/TD]
[TD]$x^2-7x+18=0$[/TD]
[TD]$-23$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=3$[/TD]
[TD]$x^2-15x+54=0$[/TD]
[TD]$9$[/TD]
[TD]$x=6$ or $x=9$[/TD]
[/TR]
[TR]
[TD]$n=4$[/TD]
[TD]$x^2-31x+162=0$[/TD]
[TD]$313$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=5$[/TD]
[TD]$x^2-63x+486=0$[/TD]
[TD]$2025$[/TD]
[TD]$x=9$ or $x=54$[/TD]
[/TR]
[/TABLE]

We prove that there is no solution for $y\ge 6$.

Suppose that $(x,\,y)$ satisfies the original equation and $y\ge 6$. Since $x|2\cdot 3^y=x(2^{y+1}-1)-x^2$, we have $x=3^k$ with some $0\le k\le y$ or $x=2\cdot 3^k$ with some $0\le k \le y$.

In the first case, let $m=y-k$, then $2^{y+1}-1=x+\dfrac{2\cdot 3^y}{x}=3^k+3\cdot 3^m$

In the second case, let $k=y-m$, then $2^{y+1}-1=x+\dfrac{2\cdot 3^y}{x}=3^k+3\cdot 3^m$

Hence in both cases we need to find the non negative integer solutions of $3^k+2\cdot 3^m=2^{y+1}-1$, $m+k=y$. (*)

Next we prove bounds for $m,\,k$. From (*), we get

$3^k<2^{y+1}=8^{\tiny\dfrac{y+1}{3}}<9^{\tiny\dfrac{y+1}{3}}=3^{\tiny\dfrac{2(y+1)}{3}}$

and

$2\cdot 3^{m}<2^{y+1}=2\cdot 8^{\tiny\dfrac{y}{3}}<2\cdot 9^{\tiny\dfrac{y}{3}}=2\cdot 3^{\tiny\dfrac{2y}{3}}<2\cdot 3^{\tiny\dfrac{2(y+1)}{3}}$

so $m,\,k<\dfrac{2(y+1)}{3}$.

Combining these inequalities with $m+k=y$, we obtain

$\dfrac{y-2}{3}<m,\,k<\dfrac{2(y+1)}{3}$ (**)

Now, let $h=\text{min}(p,\,q)$. By (**), we have $h>\dfrac{y-2}{3}$, in particular, we have $h>1$. On the LHS of (*), both terms are divisible by $3^h$, therefore, $9|3^h|2^{y+1}-1$. It is easy to check that $ord_g(2)=6$, so $9|2^{y+1}-1$ iff $6|y+1$. Therefore, $y+1=6r$ for some positive integer $r$, adn we can write

$2^{y+1}-1=4^{3r}-1=(4^{2r}+4^r+1)(2^r-1)(2^r+1)$

Notice that the factor $4^{2r}+4^r+1=(4^r-1)^2+3\cdot 4^r$ is divisible by 3, but it is never divisible by 9. The other two factors in $2^{y+1}-1=4^{3r}-1=(4^{2r}+4^r+1)(2^r-1)(2^r+1)$, i.e.e $2^r-1$ and $2^r+1$ are coprime, both are odd and their difference is 2. Since the whole product is divisible by $3^h$, we have either $3^{h-1}|2^r-1$ or $3^{h-1}|2^r+1$.

In any case, we have

$3^{h-1}\le 2^r+1\le 3^r=3^{\tiny\dfrac{y+1}{6}}$

$\dfrac{y-2}{3}-1<h-1\le \dfrac{y+1}{6}$

$n<11$

But this is impossible since we assumed $y\ge 6$ and we proved $6|y+1$.

 

[kaliprasad]

Solution of other:

Spoiler

For fixed values of $y$, the original equation is a simple quadratic equation in $x$. For $y\le 5$, the solutions are listed below:

[TABLE="class: grid, width: 500"]
[TR]
[TD]Case[/TD]
[TD]Function[/TD]
[TD]Discriminant[/TD]
[TD]Integer Roots[/TD]
[/TR]
[TR]
[TD]$n=0$[/TD]
[TD]$x^2-x+2=0$[/TD]
[TD]$-7$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=1$[/TD]
[TD]$x^2-3x+6=0$[/TD]
[TD]$-15$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=2$[/TD]
[TD]$x^2-7x+18=0$[/TD]
[TD]$-23$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=3$[/TD]
[TD]$x^2-15x+54=0$[/TD]
[TD]$9$[/TD]
[TD]$x=6$ or $x=9$[/TD]
[/TR]
[TR]
[TD]$n=4$[/TD]
[TD]$x^2-31x+162=0$[/TD]
[TD]$313$[/TD]
[TD]None[/TD]
[/TR]
[TR]
[TD]$n=5$[/TD]
[TD]$x^2-63x+486=0$[/TD]
[TD]$2025$[/TD]
[TD]$x=9$ or $x=54$[/TD]
[/TR]
[/TABLE]

We prove that there is no solution for $y\ge 6$.

Suppose that $(x,\,y)$ satisfies the original equation and $y\ge 6$. Since $x|2\cdot 3^y=x(2^{y+1}-1)-x^2$, we have $x=3^k$ with some $0\le k\le y$ or $x=2\cdot 3^k$ with some $0\le k \le y$.

In the first case, let $m=y-k$, then $2^{y+1}-1=x+\dfrac{2\cdot 3^y}{x}=3^k+3\cdot 3^m$

In the second case, let $k=y-m$, then $2^{y+1}-1=x+\dfrac{2\cdot 3^y}{x}=3^k+3\cdot 3^m$

Hence in both cases we need to find the non negative integer solutions of $3^k+2\cdot 3^m=2^{y+1}-1$, $m+k=y$. (*)

Next we prove bounds for $m,\,k$. From (*), we get

$3^k<2^{y+1}=8^{\tiny\dfrac{y+1}{3}}<9^{\tiny\dfrac{y+1}{3}}=3^{\tiny\dfrac{2(y+1)}{3}}$

and

$2\cdot 3^{m}<2^{y+1}=2\cdot 8^{\tiny\dfrac{y}{3}}<2\cdot 9^{\tiny\dfrac{y}{3}}=2\cdot 3^{\tiny\dfrac{2y}{3}}<2\cdot 3^{\tiny\dfrac{2(y+1)}{3}}$

so $m,\,k<\dfrac{2(y+1)}{3}$.

Combining these inequalities with $m+k=y$, we obtain

$\dfrac{y-2}{3}<m,\,k<\dfrac{2(y+1)}{3}$ (**)

Now, let $h=\text{min}(p,\,q)$. By (**), we have $h>\dfrac{y-2}{3}$, in particular, we have $h>1$. On the LHS of (*), both terms are divisible by $3^h$, therefore, $9|3^h|2^{y+1}-1$. It is easy to check that $ord_g(2)=6$, so $9|2^{y+1}-1$ iff $6|y+1$. Therefore, $y+1=6r$ for some positive integer $r$, adn we can write

$2^{y+1}-1=4^{3r}-1=(4^{2r}+4^r+1)(2^r-1)(2^r+1)$

Notice that the factor $4^{2r}+4^r+1=(4^r-1)^2+3\cdot 4^r$ is divisible by 3, but it is never divisible by 9. The other two factors in $2^{y+1}-1=4^{3r}-1=(4^{2r}+4^r+1)(2^r-1)(2^r+1)$, i.e.e $2^r-1$ and $2^r+1$ are coprime, both are odd and their difference is 2. Since the whole product is divisible by $3^h$, we have either $3^{h-1}|2^r-1$ or $3^{h-1}|2^r+1$.

In any case, we have

$3^{h-1}\le 2^r+1\le 3^r=3^{\tiny\dfrac{y+1}{6}}$

$\dfrac{y-2}{3}-1<h-1\le \dfrac{y+1}{6}$

$n<11$

But this is impossible since we assumed $y\ge 6$ and we proved $6|y+1$.

good solution we can simplify as below

Spoiler

we can convert $x^2+2\cdot 3^y=x(2^{y+1}-1)$

quadratic in x

$x^2-x(2^{y+1}-1) + 2\cdot 3^y=0$

now discriminant should be greater than zero
$(2^{y+1}-1)^2- 4\cdot 2\cdot 3^y\ge 0$

as y increase 1st term almost doubles and 2 term triples and we get upper limit for y as 5