[SOLVED] Complete Square

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Feb 6th 2010, 10:56 AM
havaliza
[SOLVED] Complete Square
Can anyone help me to prove this:

Suppose $x+xy$ and $y+xy$ are complete squares. prove that exactly one of $x$ and $y$ is a complete square.
• Feb 11th 2010, 11:29 AM
Media_Man
Data
This is a very interesting problem. Using the notation $f(x,y)=(x+xy,y+xy)=(m^2,n^2)$, here are all the solutions $x, generated by computer. As you can see, there are only $15$, so they are somewhat rare. No counterexamples under $10000$. Does anyone see any helpful patterns?

$f(1,8)=(3^2,4^2)$
$f(1,288)=(17^2,24^2)$
$f(1,9800)=(99^2,140^2)$
$f(4,80)=(18^2,20^2)$
$f(8,49)=(20^2,21^2)$
$f(8,1681)=(116^2,123^2)$
$f(9,360)=(57^2,60^2)$
$f(16,1088)=(132^2,136^2)$
$f(25,2600)=(255^2,260^2)$
$f(36,5328)=(438^2,444^2)$
$f(49,288)=(119^2,120^2)$
$f(49,9800)=(693^2,700^2)$
$f(80,1444)=(340^2,342^2)$
$f(288,1681)=(696^2,697^2)$
$f(1681,9800)=(4059^2,4060^2)$
• Feb 11th 2010, 12:26 PM
Bruno J.
Well it's quite trivial that not both $x,y$ can be perfect squares, because if $x=u^2$ and $x(y+1)=m^2 \Rightarrow y+1 = \left(\frac{m}{u}\right)^2$ and it's impossible that both $y, y+1$ be perfect squares, unless $y=0$.

• Feb 11th 2010, 12:40 PM
icemanfan
Quote:

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

Actually, shouldn't the statement be:

$x(y+1)=m^2 \Rightarrow y+1 = \frac{m^2}{x}$?
• Feb 11th 2010, 01:10 PM
Bruno J.
Yeah! Stupid mistake, I fixed it. Thanks! (Cool)
• Feb 12th 2010, 03:42 AM
Opalg
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 $x(y+1) = \Box,\ y(x+1) = \Box$ (where $\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 $x = p\Box,\ y+1=p\Box,\ y=q\Box,\ x+1 = q\Box$. Equivalently, the system of Diophantine equations

$\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 $\sqrt{13/17}$ (using the standard procedure for solving Pell's equation). That leads to the solution $17\times7^2 - 13\times8^2 = 1$ for one of the equations in (*). But I could not find a solution for the equation $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.
• Feb 12th 2010, 01:18 PM
Media_Man
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 $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 $x=a_{odd}^2, y=a_{even}^2-1$, and you have a solution. (No, this is not a notation error, the choices of $a_{odd}$ and $a_{even}$ can be completely random; they do not have to be consecutive.) Now, $x(y+1)$ is a square trivially, but I could use some help proving $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 $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, $a_{n}^2=2b_n^2-1$, and for all n even, $a_{n}^2=2b_n^2+1$. Assuming for the moment this hypothesis is true, $x=a_{odd}^2=2b_{odd}^2-1, y=a_{even}^2-1=2b_{even}^2$. Notice that $x=\square=2\square-1$ and $y=\square-1=2\square$. This is enough to prove $x(y+1)$ and $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.
• Feb 12th 2010, 01:38 PM
icemanfan
This should be fairly obvious, but I'll post it anyway. If $x = a^2$ for some integer a, then $y = b^2 - 1$ for some integer b.

It follows that

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

The first equation is trivial, but the second is not. It is unclear whether all solutions $(a, b, n)$ would lead to a solution to the original problem. However, writing it this way eliminates m as a necessary variable.
• Feb 13th 2010, 08:51 AM
Media_Man
Pell Numbers
(Further reading: Pell number - Wikipedia, the free encyclopedia)

Here we go. The continued fraction representation of $\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 $\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 $\frac{P_{n-1}+P_n}{P_n}$, where $P_n$ denotes the nth Pell Number, $P=\{1,2,5,12,29,70,...\}$. This sequence grows similarly to Fibonacci, and a closed formula is $P_n=\frac{\alpha^n-\beta^n}{2\sqrt2}$, where $\alpha=1+\sqrt2,\beta=1-\sqrt2$. It can easily be shown that the numerators, $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 $\alpha\beta=-1$. Now, $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=$ $\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, $H_{odd}^2=2P_{odd}^2-1, H_{even}^2=2P_{even}^2+1$.

Back to the problem. Define $x=H_{even}^2=2P_{even}^2+1, y=H_{odd}^2-1=2P_{odd}^2$, and it follows immediately that $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 $(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 $p^2-nq^2=1$ by $(p,q)^+$ and all solutions to the negative Pell equation $p^2-nq^2=-1$ by $(p,q)^-$. Define $x=a^2-1=nb^2, y=c^2=nd^2-1$, for $(a,b)\in(p,q)^+, (c,d)\in(p,q)^-$ and you can easily see that $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 $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 $x=\square$. Except for the trivial $x=0$, $x+1\neq\square$, so $x+1=n\square$ for some squarefree n. Since $x=\square, y=\square-1$ for $x(y+1)=\square$, and since $x+1=n\square, y=n\square$ for $y(x+1)=\square$. So, there is a one-to-one correspondence between simultaneous solutions to the Pell equations $p^2-nq^2=1$ and $p'^2-nq'^2=-1$ and ALL integer $(x,y)$ solutions to $(x(y+1),y(x+1))=(m^2,n^2)$ with the constraint that $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?
• Feb 13th 2010, 03:18 PM
Media_Man
Simple Proof... if it's right
Going back to the original question, I came up with this. Please verify or discredit...

Let $x(y+1)=m^2,y(x+1)=n^2$. So $y=\frac{m^2-x}x=\frac{n^2}{x+1}$. Cross-multiplying and expanding, $x^2+(n^2-m^2+1)x-m^2=0$, so $2x=m^2-n^2-1\pm\sqrt{(n^2-m^2+1)^2+4m^2}$. For this to be an integer, the $()^2+()^2$ expression under the radical must sum to a perfect square. Since all solutions to $a^2+b^2=c^2$ can be enumerated by $(u^2-v^2)^2+(2uv)^2=(u^2+v^2)^2$, let $n^2-m^2+1=u^2-v^2, 2m=2uv$. So now, $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 $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?
• Feb 13th 2010, 07:33 PM
Bacterius
Hi,
just for me to better understand the question, do you mean that if $x(y + 1)$ and $y(x + 1)$ are perfect squares, then either $x$ or $y$ is a perfect square ?
• Feb 14th 2010, 12:48 PM
Opalg
Quote:

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

Let $x(y+1)=m^2,y(x+1)=n^2$. So $y=\frac{m^2-x}x=\frac{n^2}{x+1}$. Cross-multiplying and expanding, $x^2+(n^2-m^2+1)x-m^2=0$, so $2x=m^2-n^2-1\pm\sqrt{(n^2-m^2+1)^2+4m^2}$. For this to be an integer, the $()^2+()^2$ expression under the radical must sum to a perfect square. Since all solutions to $a^2+b^2=c^2$ can be enumerated by $(u^2-v^2)^2+(2uv)^2=(u^2+v^2)^2$, let $n^2-m^2+1=u^2-v^2, 2m=2uv$. So now, $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 $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 $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 $x = ku^2$ or $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.)
• Feb 14th 2010, 01:03 PM
icemanfan
Quote:

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?
• Feb 14th 2010, 01:35 PM
Opalg
Quote:

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!
• Feb 14th 2010, 02:29 PM
icemanfan
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 $ca^2$ and y is of the form $db^2$.

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

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

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

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

If you suppose that none of $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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last