# Thread: [SOLVED] Complete Square

1. ## [SOLVED] Complete Square

Can anyone help me to prove this:

Suppose $\displaystyle x+xy$ and $\displaystyle y+xy$ are complete squares. prove that exactly one of $\displaystyle x$ and $\displaystyle y$ is a complete square.

2. ## Data

This is a very interesting problem. Using the notation $\displaystyle f(x,y)=(x+xy,y+xy)=(m^2,n^2)$, here are all the solutions $\displaystyle x<y<10000$, generated by computer. As you can see, there are only $\displaystyle 15$, so they are somewhat rare. No counterexamples under $\displaystyle 10000$. Does anyone see any helpful patterns?

$\displaystyle f(1,8)=(3^2,4^2)$
$\displaystyle f(1,288)=(17^2,24^2)$
$\displaystyle f(1,9800)=(99^2,140^2)$
$\displaystyle f(4,80)=(18^2,20^2)$
$\displaystyle f(8,49)=(20^2,21^2)$
$\displaystyle f(8,1681)=(116^2,123^2)$
$\displaystyle f(9,360)=(57^2,60^2)$
$\displaystyle f(16,1088)=(132^2,136^2)$
$\displaystyle f(25,2600)=(255^2,260^2)$
$\displaystyle f(36,5328)=(438^2,444^2)$
$\displaystyle f(49,288)=(119^2,120^2)$
$\displaystyle f(49,9800)=(693^2,700^2)$
$\displaystyle f(80,1444)=(340^2,342^2)$
$\displaystyle f(288,1681)=(696^2,697^2)$
$\displaystyle f(1681,9800)=(4059^2,4060^2)$

3. Well it's quite trivial that not both $\displaystyle x,y$ can be perfect squares, because if $\displaystyle x=u^2$ and $\displaystyle x(y+1)=m^2 \Rightarrow y+1 = \left(\frac{m}{u}\right)^2$ and it's impossible that both $\displaystyle y, y+1$ be perfect squares, unless $\displaystyle y=0$.

I'll think a bit about this problem!

4. Originally Posted by Bruno J.
Well it's quite trivial that not both $\displaystyle x,y$ can be perfect squares, because $\displaystyle x(y+1)=m^2 \Rightarrow y+1 = \left(\frac{m}{x}\right)^2$ and it's impossible that both $\displaystyle y, y+1$ be perfect squares, unless $\displaystyle y=0$.

I'll think a bit about this problem!
Actually, shouldn't the statement be:

$\displaystyle x(y+1)=m^2 \Rightarrow y+1 = \frac{m^2}{x}$?

5. Yeah! Stupid mistake, I fixed it. Thanks!

6. It's a relief to know that I am not the only one to have been baffled by this intriguing problem. I have spent a lot of time thinking about it, and have made essentially no progress. I started by thinking about the conditions that a counterexample would have to satisfy.

If the equations $\displaystyle x(y+1) = \Box,\ y(x+1) = \Box$ (where $\displaystyle \Box$ denotes a square, of course) have a solution in which neither x nor y is a square, then there must exist squarefree integers p, q with $\displaystyle x = p\Box,\ y+1=p\Box,\ y=q\Box,\ x+1 = q\Box$. Equivalently, the system of Diophantine equations

$\displaystyle \left.{pw^2 - qx^2 = \phantom{.}1 \atop py^2 - q z^2 = -1}\right\}\quad \text{($p$,$q$squarefree with gcd 1)}\qquad(*)$

must have a solution.

I tried looking at the situation where p and q are both prime. A necessary condition for (*) to have a solution in this case is that q and –q should both be quadratic residues mod p. This happens for example if p=13 and q =17. Then you look for solutions to (*) by forming the continued fraction expansion of $\displaystyle \sqrt{13/17}$ (using the standard procedure for solving Pell's equation). That leads to the solution $\displaystyle 17\times7^2 - 13\times8^2 = 1$ for one of the equations in (*). But I could not find a solution for the equation $\displaystyle 17y^2 - 13z^2 = -1$ by that method.

Other pairs of plausible primes also fail to produce solutions to (*). Taken together with Media_Man's numerical evidence, this begins to make it look as though (*) has no solutions unless p or q is equal to 1. Maybe someone who knows more about Diophantine equations than me can shed some light on this.

Edit. The x and y in the equations (*) are not the same as in the original equations. That was a bad choice of notation. I just needed four integer variables, and w, x, y, z were the obvious ones to go for, forgetting that x and y appeared in the original problem.

7. ## Okay, that is just weird.

At the expense of answering your original question, havaliza, I am trying to enumerate all the solutions. I have not found a general formula or algorithm, but I have found a subset that is so bizarre it is worth sharing.

Start with the sequence $\displaystyle a_1=1, a_2=3, a_n=2a_{n-1}+a_{n-2}, a=\{1,3,7,17,41,99,239,577,1393,3363,...\}$. Incidentally, this is Sloane's A001333, or "numerators of continued fraction convergents to sqrt(2)."

Let $\displaystyle x=a_{odd}^2, y=a_{even}^2-1$, and you have a solution. (No, this is not a notation error, the choices of $\displaystyle a_{odd}$ and $\displaystyle a_{even}$ can be completely random; they do not have to be consecutive.) Now, $\displaystyle x(y+1)$ is a square trivially, but I could use some help proving $\displaystyle y(x+1)$ is always a square.

Again, this is only a subset of solutions, but it is a pattern I gleaned from my data and for whatever strange reason it seems to work. This also supports Opalg's implication that the problem may be connected to continued fractions, of which I know very little. If we can find a method of producing all solutions, prove the method leaves no solutions out, and that the method always gives x or y a square, this path will lead to an answer to your question. However, I think this question has a lot more depth to it.

UPDATE: Define $\displaystyle b_0=0, b_1=1, b_n=2b_{n-1}+b_{n-2}, b=\{1,2,5,12,29,70,169,408,985,2378,...\}$. These are Sloane's A000129, the Pell Numbers, or "denominators of continued fraction convergents to sqrt(2)." HYPOTHESIS: for all n odd, $\displaystyle a_{n}^2=2b_n^2-1$, and for all n even, $\displaystyle a_{n}^2=2b_n^2+1$. Assuming for the moment this hypothesis is true, $\displaystyle x=a_{odd}^2=2b_{odd}^2-1, y=a_{even}^2-1=2b_{even}^2$. Notice that $\displaystyle x=\square=2\square-1$ and $\displaystyle y=\square-1=2\square$. This is enough to prove $\displaystyle x(y+1)$ and $\displaystyle y(x+1)$ are both squares. Again, if the above hypothesis is true linking sequences a,b, then this construction does give a subset of solutions.

8. This should be fairly obvious, but I'll post it anyway. If $\displaystyle x = a^2$ for some integer a, then $\displaystyle y = b^2 - 1$ for some integer b.

It follows that

$\displaystyle a^2 b^2 = m^2$ and $\displaystyle (b^2 - 1)(a^2 + 1) = n^2$.

The first equation is trivial, but the second is not. It is unclear whether all solutions $\displaystyle (a, b, n)$ would lead to a solution to the original problem. However, writing it this way eliminates m as a necessary variable.

9. ## Pell Numbers

(Further reading: Pell number - Wikipedia, the free encyclopedia)

Here we go. The continued fraction representation of $\displaystyle \sqrt2=1+\frac1{2+\frac1{2+\frac1{2+\frac1{...}}}}$. If you take the nth iteration of this repeated pattern, you get the rational "convergents," namely $\displaystyle \frac{1}{1},\frac{3}{2},\frac{7}{5},\frac{17}{12}, \frac{41}{29},\frac{99}{70},\frac{239}{169},\frac{ 577}{408},\frac{1393}{985},...\to\sqrt2$. These are all of the form $\displaystyle \frac{P_{n-1}+P_n}{P_n}$, where $\displaystyle P_n$ denotes the nth Pell Number, $\displaystyle P=\{1,2,5,12,29,70,...\}$. This sequence grows similarly to Fibonacci, and a closed formula is $\displaystyle P_n=\frac{\alpha^n-\beta^n}{2\sqrt2}$, where $\displaystyle \alpha=1+\sqrt2,\beta=1-\sqrt2$. It can easily be shown that the numerators, $\displaystyle H_n=P_{n-1}+P_n=\frac{\alpha^n+\beta^n}{2}$ (these are called the Half-companion Pell Numbers). Start by noting the product $\displaystyle \alpha\beta=-1$. Now, $\displaystyle H_n^2-2P_n^2=\left(\frac{\alpha^n+\beta^n}{2}\right)^2-2\left(\frac{\alpha^n-\beta^n}{2\sqrt2}\right)^2=$ $\displaystyle \frac14\left((\alpha^{2n}+2\alpha^n\beta^n+\beta^{ 2n})-(\alpha^{2n}-2\alpha^n\beta^n+\beta^{2n})\right)=\frac14(4\alph a^n\beta^n)=(\alpha\beta)^n=(-1)^n$. Therefore, $\displaystyle H_{odd}^2=2P_{odd}^2-1, H_{even}^2=2P_{even}^2+1$.

Back to the problem. Define $\displaystyle x=H_{even}^2=2P_{even}^2+1, y=H_{odd}^2-1=2P_{odd}^2$, and it follows immediately that $\displaystyle x(y+1),y(x+1)$ are both squares. QED

This produces only a subset of solutions here, which we shall call Pell Solutions. Removing these, the rest of the solutions under 10000 are $\displaystyle (4,80),(9,360),(16,1088),(25,2600),(36,5328),(1444 ,80)$. Conjecture: For all non-Pell Solutions, given any square x, there exists exactly one solution (x,y).

Again, havaliza, I apologize for skirting your question and dragging a lot of advanced number theory into your thread, but I believe this problem is much more complex than it seems at first glance, and deserves much more attention.

UPDATE: For any nonsquare n, denote all solutions to the Pell equation $\displaystyle p^2-nq^2=1$ by $\displaystyle (p,q)^+$ and all solutions to the negative Pell equation $\displaystyle p^2-nq^2=-1$ by $\displaystyle (p,q)^-$. Define $\displaystyle x=a^2-1=nb^2, y=c^2=nd^2-1$, for $\displaystyle (a,b)\in(p,q)^+, (c,d)\in(p,q)^-$ and you can easily see that $\displaystyle x(y+1),y(x+1)$ are squares. The Pell equation is known to always have an infinite number of solutions for any nonsquare n. However, no general solution to the negative Pell equation is currently known. Therefore, the solutions to your question, havaliza, cannot be enumerated wholly using known math. However, that is not to say your question cannot be answered. Extending the umbrella of the term "Pell Solution" to these numerous examples with $\displaystyle n\neq2$, your question can still be phrased as "Do there exist any non-Pell Solutions?" I have a feeling the answer is no, but seeing as how I just proved my own earlier conjecture false, I do not know.

UPDATE: WLOG, suppose $\displaystyle x=\square$. Except for the trivial $\displaystyle x=0$, $\displaystyle x+1\neq\square$, so $\displaystyle x+1=n\square$ for some squarefree n. Since $\displaystyle x=\square, y=\square-1$ for $\displaystyle x(y+1)=\square$, and since $\displaystyle x+1=n\square, y=n\square$ for $\displaystyle y(x+1)=\square$. So, there is a one-to-one correspondence between simultaneous solutions to the Pell equations $\displaystyle p^2-nq^2=1$ and $\displaystyle p'^2-nq'^2=-1$ and ALL integer $\displaystyle (x,y)$ solutions to $\displaystyle (x(y+1),y(x+1))=(m^2,n^2)$ with the constraint that $\displaystyle x=\square$. Therefore, with no need to categorize them, all the solutions I produced fall under the Pell Solutions umbrella. Again, do there exist any non-Pell solutions?

10. ## Simple Proof... if it's right

Going back to the original question, I came up with this. Please verify or discredit...

Let $\displaystyle x(y+1)=m^2,y(x+1)=n^2$. So $\displaystyle y=\frac{m^2-x}x=\frac{n^2}{x+1}$. Cross-multiplying and expanding, $\displaystyle x^2+(n^2-m^2+1)x-m^2=0$, so $\displaystyle 2x=m^2-n^2-1\pm\sqrt{(n^2-m^2+1)^2+4m^2}$. For this to be an integer, the $\displaystyle ()^2+()^2$ expression under the radical must sum to a perfect square. Since all solutions to $\displaystyle a^2+b^2=c^2$ can be enumerated by $\displaystyle (u^2-v^2)^2+(2uv)^2=(u^2+v^2)^2$, let $\displaystyle n^2-m^2+1=u^2-v^2, 2m=2uv$. So now, $\displaystyle 2x=v^2-u^2\pm (u^2+v^2)=2v^2,-2u^2$. Therefore, x is a perfect square. QED

This feels like cheating somehow. I think it might be necessary to show that since $\displaystyle 2uv>u^2-v^2, 2m>n^2-m^2+1$. Is this a hole? Can it be filled? Are there any other holes? Is this proof even valid?

11. Hi,
just for me to better understand the question, do you mean that if $\displaystyle x(y + 1)$ and $\displaystyle y(x + 1)$ are perfect squares, then either $\displaystyle x$ or $\displaystyle y$ is a perfect square ?

12. Originally Posted by Media_Man
Going back to the original question, I came up with this. Please verify or discredit...

Let $\displaystyle x(y+1)=m^2,y(x+1)=n^2$. So $\displaystyle y=\frac{m^2-x}x=\frac{n^2}{x+1}$. Cross-multiplying and expanding, $\displaystyle x^2+(n^2-m^2+1)x-m^2=0$, so $\displaystyle 2x=m^2-n^2-1\pm\sqrt{(n^2-m^2+1)^2+4m^2}$. For this to be an integer, the $\displaystyle ()^2+()^2$ expression under the radical must sum to a perfect square. Since all solutions to $\displaystyle a^2+b^2=c^2$ can be enumerated by $\displaystyle (u^2-v^2)^2+(2uv)^2=(u^2+v^2)^2$, let $\displaystyle n^2-m^2+1=u^2-v^2, 2m=2uv$. So now, $\displaystyle 2x=v^2-u^2\pm (u^2+v^2)=2v^2,-2u^2$. Therefore, x is a perfect square. QED

This feels like cheating somehow. I think it might be necessary to show that since $\displaystyle 2uv>u^2-v^2, 2m>n^2-m^2+1$. Is this a hole? Can it be filled? Are there any other holes? Is this proof even valid?
That's an ingenious method, but sad to say it doesn't seem to work. The reason is that the general form of a pythagorean triple is $\displaystyle k(u^2-v^2),\ 2kuv,\ k(u^2+v^2)$. If you leave out the k, you don't cover all possible cases. But if you include the k, you end up with the conclusion that $\displaystyle x = ku^2$ or $\displaystyle kv^2$, which of course doesn't prove that x is a perfect square.

I tried to see whether this ingenious idea could be adapted to give a correct proof, but I haven't succeeded in getting anywhere. One snag is that in the original problem it need not be true that x is a square. (It might be y that is the square, as in the example x = 8, y = 49.)

13. Originally Posted by Opalg
One snag is that in the original problem it need not be true that x is a square. (It might be y that is the square, as in the example x = 8, y = 49.)
Can't you assume by symmetry and without loss of generality that x is the square?

14. Originally Posted by icemanfan
Can't you assume by symmetry and without loss of generality that x is the square?
Not in Media_Man's argument, because if you exchange x and y then you also exchange m and n, and so the values of u and v will be different.

Alternatively, you had better not assume that x is a square, because that is what you are trying to prove!

15. I understand now why my earlier statement was rather nonsensical. However, you can use Media Man's argument to show that x is of the form $\displaystyle ca^2$ and y is of the form $\displaystyle db^2$.

Then you have $\displaystyle ca^2(1 + db^2) = m^2$ and $\displaystyle db^2(1 + ca^2) = n^2$.

We can rewrite these as $\displaystyle c(1 + db^2) = \left(\frac{m}{a}\right)^2$ and $\displaystyle d(1 + ca^2) = \left(\frac{n}{b}\right)^2$.

It must be true that either both $\displaystyle c$ and $\displaystyle 1 + db^2$ are squares or neither of them are.

It must also be true that either both $\displaystyle d$ and $\displaystyle 1 + ca^2$ are squares or neither of them are.

If you suppose that none of $\displaystyle c, d, 1 + ca^2, 1 + db^2$ is a square and manage to show that this leads to a contradiction, that would be enough for proof of the original statement that at exactly one of x and y is a square, since we have already eliminated the possibility that both of them are.

Page 1 of 2 12 Last