Integer Solutions?

**Media_Man** · August 27th 2009, 05:47 PM

Find positive integers $X\neq Y\neq A\neq B$ such that $\frac{Y^2(Y^2-X^2)-A^2(A^2-X^2)-B^2(B^2-X^2)}{X^2+Y^2-A^2-B^2}$ is a perfect square integer.

Bonus: Find a formula generating solutions.

Bonus Bonus: Find a formula generating ALL solutions.

(This actually DOES have real implications on another problem, as random as it looks.)

**alunw** · August 28th 2009, 05:55 AM

Here's one solution:

Y = 12
X = 5
A = 3
B = 4 which gives 11*11

This is no doubt connected with the Pythagorean triples 3 4 5 and 5 12 13.
I posted a formula for finding pairs of triples containing common values a while back here:
http://www.mathhelpforum.com/math-he...-triplets.html
Maybe you might like to check if such pairs always work. I haven't got the time to do that right now, but maybe will take a look at it tomorrow if nobody else has helped in the mean time.

OK I've checked a few and that one seems to be a one off. I'll think about it more later.

**Media_Man** · August 28th 2009, 10:23 AM

alunw -

Thank you for your response. I have, however, made a mistake far simplifying my question. In order to work, not only must $X\neq Y\neq A\neq B$ , but three more criteria must hold that I overlooked, making your solution useless to my query.

You are correct in your observation that this question is connected to triples. In fact, I am looking for groups of triples related in a very specific way. If you wish, the main thread which I am working on is http://www.mathhelpforum.com/math-he...g-ladders.html

**alunw** · August 28th 2009, 01:48 PM

I did notice the "Polynomial Squaring ladder" thread yesterday and wondered if this might be connected with it. However, I'm don't feel I have the time or energy (and quite possibly not the ability) to understand that properly.
If it is any help to you I've now written a noddy C program that finds all the solutions with b>a (since the problem you posed is symmetric in a and b) and with x,y,a,b between 1 and 50 (which can obviously be increased to some higher value if need be).
You probably should also stipulate that the greated common divisor of x,y,a,b should be 1. Without that restriction, but with none of y,x,a or b equal to zero there are 12428 distinct solutions to this equation with all of x,y,a,b between 1 and 50 inclusive and all different and b > a, and another couple of hundred with a or x 0. There's no very obvious pattern to the solutions I'm finding. If you can specify your additional criteria I can try putting them into the program as well to see if I can then spot a pattern.

I'll end this post with a selection of solutions, all given in the order y,x,a,b, and with the fifth number the square root of the answer.
Apologies if it turns out I have made some gross programming error.

1 2 8 11 10
1 2 13 23 21
1 2 26 47 43
1 3 13 31 29
1 4 2 5 4
1 4 7 8 7
1 4 21 26 24
1 5 13 19 17
1 6 4 11 10
1 6 11 16 14
1 6 17 18 17
1 6 40 47 44
1 7 4 8 4
1 7 9 17 15
1 7 11 13 11
6 31 14 27 63
6 31 15 17 26
6 31 15 38 29
6 31 17 34 12
6 31 17 38 27
6 31 19 21 46
6 31 19 34 9
6 31 21 22 77
6 31 21 34 7
6 31 27 35 14
6 32 2 28 24
6 32 2 36 40
6 32 8 24 26
6 32 8 38 36
6 32 12 28 46
6 32 12 34 16
49 42 19 43 31
49 43 17 29 29
49 44 5 42 24
49 44 8 23 23
49 45 7 11 17
49 45 21 39 31
49 45 22 26 28
49 46 2 17 17
49 46 5 8 14
49 46 17 38 28
49 46 26 31 31
49 46 28 31 32
49 47 2 14 14
49 47 7 23 19
49 47 8 16 16
49 47 13 19 19
49 47 22 26 26
49 48 22 42 29
49 48 31 36 34

**Media_Man** · August 28th 2009, 03:03 PM

Thanks for your interest. What we are looking for is four Pythagorean triples with the same hypotenuse with an interesting restraint on their middle terms...

As you probably know, all triples are of the form $(n^2-m^2,2mn,m^2+n^2)$ . So if the four triples are...

$T_1=(b^2-a^2,2ab,a^2+b^2)$
$T_2=(d^2-c^2,2cd,c^2+d^2)$
$T_3=(f^2-e^2,2ef,e^2+f^2)$
$T_4=(h^2-g^2,2gh,g^2+h^2)$

... then our two conditions are...

(1) $a^2+b^2=c^2+d^2=e^2+f^2=g^2+h^2=S$
(2) $a^2b^2+c^2d^2=e^2f^2+g^2h^2$

Using simple substitution, this search boils down to the following: Given positive integers $a,c,e,g$ , define $S=\frac{a^4+c^4-e^4-g^4}{a^2+c^2-e^2-g^2}$ . It can be shown then that $b=\sqrt{S-a^2}, d=\sqrt{S-c^2}, f=\sqrt{S-e^2}, h=\sqrt{S-g^2}$ . If $S,b,d,f,h$ are all integers, we have a solution! This solution corresponds exactly to a polynomial squaring ladder, the subject of the other thread.

I too have created a java program to randomly search for solutions, and the only two I have found for $a<e<g<c<1000$ are

(1) -- $101^2+353^2=131^2+343^2=77^2+359^2=11^2+367^2$ where $101^2 353^2+77^2 359^2 = 131^2 343^2+11^2 367^2$
(2) -- $139^2+1087^2=317^2+1049^2=541^2+953^2=719^2+827^2$ where $139^2 1087^2 + 719^2 827^2=317^2 1049^2+541^2 953^2$

These two examples correspond to the two squaring ladders we already knew about. What we seek are (a) more examples (b) a way of narrowing the possibilities to blindly test, or ideally (c) a formula that spits out all possible solutions. And this is where we are stuck.

**alunw** · August 29th 2009, 12:46 AM

I'm going to write a little computer program to look for odd numbers that can be expressed as the sum of odd and even squares in at least four distinct ways, since I understand that this is what you are now looking for - at least this should give some candidate sets of four Pythagorean triples. These should be fairly numerous, so I'll filter them by seeing if, in some order, the set satisfies your second condition. I don't think it should take too long to enumerate all the possibilities where a,b,c... are reasonably sized - say up to the maximum 16 bit signed integer so that I can calculate your second condition above without needing more than 64 bit arithmetic. I think this will be more efficient than working out S,b,d,f,h and seeing if they are integers.
One related fact I do know which may be of interest if you are not already familiar with it is that a prime congruent to 1 modulo 4 can be expressed as a sum of two squares in essentially one way.

**jamix** · August 29th 2009, 01:50 AM

Ah, so this condition on $S$ will create a polynomial ladder k =4, yes? Or is it k = 3 still?

With regards to your question (c), perhaps this conjecture will help:

All solutions $(a_1,a_2,a_3,a_4)$ generating a k = 4 ladder, are generated by $(67405x^2,3525798096x^4,533470702551552000x^8,4692 08209191321600x^8)$ for every nonzero integer $x$ .

Btw, with regards to finding examples for k = 3, you can still use the idea that if $(a_1,a_2,a_3)$ generates a k = 3 ladder, then so does $(x^2a_1,x^4a_2,x^4a_3)$ for any nonzero integer $x$ .

I guess I should try proving some of this later, but I hope you will take it on faith for now.

**alunw** · August 29th 2009, 02:57 AM

If my understanding is correct (and I've not fully got my head around the Polynomial ladder part of things) these sets of four triples should produce a k=4 ladder. But I've not yet fully puzzled out how to turn my triples into a ladder and will looking at this a bit later. It looks as though Media Man's triples are all generated by two odd numbers, and hence each number in the triple is even. I'm looking for triples that have two odd and one even number and where at least one, and so I think all four, is primitive (this wouldn't be the case for just any old collection of equal hyptoenuse triples, but I think the extra conditions enforce this). The fact mine are primitive won't matter much as I'll certainly be able to get the triples Media Man wants from the ones I'm producing by multiplying them by 2 if need be. Once I've worked out how to construct the ladders from the triples I'll post a few.
The number 67405 was the hypotenuse of the first set of four triples I found but I think there may be other possibilities. The second set of triples I found all have 600445 as the hypotenuse which is 5*29*41*101, and the third has 5915065 which is 5 * 13*17*53*101. So I expect these will give two new families of k=4 ladders. I haven't found any others yet which are not multiples of one of these three possibilities.

The three sets of four triples I have so far are
1) T(237,106) ,T(189,178) T(141,218), T(227,126)
2) T(773,54), T(613,474) T(683,366) T(747,206)
3) T(141,2428) T(1267,2076) T(2253,916) T(717,2324)

I'm searching for them by making a,c,e,g odd and b,d,f,h even and insisting a < c < e < g. I'm checking all the possibilities for gradually increasing values of a+b. Then I rearrange to meet the second condition.

**alunw** · August 29th 2009, 04:06 AM

Further to my last post. You are specifying ladders using four numbers. For example your 1 example of a k=4 ladder is given by

(a1,a2,a3,a4) = (67405,3525798096,533470702551552000,4692082091913 21600)

If I specify the a quadruple of triples as T(a,b),T(c,d),T(e,f),T(g,h)
then a1 = a^2+b^2=c^2+d^2 etc.
and a2 = (a^2*b^2 + c^2+d^2)*2
These aren't quite the same as Media Man's formulas, and I still haven't worked out how to get a3 and a4, though I expect it is related to his formulas in some straight-forward way.
Meanwhile my program has churned out two more sets of triples:
T(7363,1110),T(6605,3438),T(6915,2762),T(7155,2062 )
with a hypotenuse=a1 of 55445869=37^2*101*401 and
T(9003,686) T(7947,4286) T(3051,8498) T(8629,2658) with a hypotenuse of
81524605=5*17*41*149*157

**alunw** · August 29th 2009, 10:46 AM

I have now worked out the relation between my sets of triples and k=4 ladder polynomials.
Media Man gave formulas in the "Polynomial Ladders" topic using a different notation from the one on this page.
Suppose his four triples are generated by $(a,b),(c,d),(e,f),(g,h)$
The 16 roots of the polynomial were the 8 values $a,b,c,d,e,f,g,h$ and the corresponding negative values.
The 4 numbers $a_1,a_2,a_3,a_4$ can be expressed in terms of the first 8 values as follows (simplifying MM's expressions slightly):

$2a_1 = a^2+b^2 = c^2+d^2 = e^2+f^2 = g^2 + h^2$
$a_2 = a_1^2 - 0.5(a^2b^2+c^2d^2) = a_1^2 - 0.5(e^2g^2+g^2h^2$
$a_3 = (a_1^2-a_2)^2 - 0.5((abcd)^2 + (efgh)^2)$
$a_4 = 0.5((abcd)^2 - (efgh)^2)$

If my four triples are generated by $(p,q),(r,s),(t,u),(v,w)$ then we can get to MM's triple generators using
$a = p+q$ , $b=p-q$ , $c=r+s,d=r-s$ , etc.
Also we have
$a_1=p^2+q^2=r^2+s^2=t^2+u^2=v^2+w^2$
$a_2=0.5((2pq)^2+(2rs)^2)=2((2tu)^2+(2vw)^2)$
$a_3= (a_1^2-a_2)^2 - 0.5((p^2-q^2)^2(r^2-s^2)^2 + (t^2-u^2)^2(v^2-w^2)^2)$
$a_3= 0.5((p^2-q^2)^2(r^2-s^2)^2 - (t^2-u^2)^2(v^2-w^2)^2)$

For example my first triple set was
$T(237,106)=(44933,50244,67405)$
$T(189,178)=(4037,67284,67405)$
$T(141,218)=(27643,61476,67405)$
$T(227,126)=(35653,57204,67405),$
with roots 343,131,367,11,359,77,353,101
and $a_1 = 67405$
$a_2 = 3525798096$
$a_3 = 533470702551552000$
$a_4 = 469208209191321600$ (ignoring the sign which has no effect)

For the next triple set
$T(773,54)=(594 613,83 484,600 445)$
$T(613,474)=(151 093,581 124,600 445)$
$T(683,366)=(332 533,499 956,600 445)$
$T(747,206)=(515 573,307 764,600 445)$ we have
$a_1 = 600 445$
$a_2 = 172 337 340 816$
$a_3 = 16 685 576 724 080 968 704 000$
$a_4 = 10 660 920 170 019 569 049 600$
It would be as well to check these as I may have made a mistake, but the triple generators are correct.

I've found two more triple sets
$T(2671,12606),T(10609,7314),T(12351,3674),T(11199, 6374)$ with
$a_1 = 166045477 = 13*17*61*109*113$ and
$T(15403,2190),T(13045,8478),T(6597,14090), T(14853,4630)$ with
$a_1 = 242048509 = 53*73^2*857$

So we now have 7 sets of 4 primitive Pythagorean triples with the same hypotenuse and obeying the special condition. If there is a pattern that ought to be quite a lot of evidence, but I can't see one.

**Media_Man** · August 29th 2009, 12:00 PM

Alunw -

Superb job! Attached is a spreadsheet summarizing the raw data of your last few posts. Unfortunately, I changed your numbers from the $p,q,r,s$ version back to the $a,b,c,d$ version for consistency's sake. In the other thread, we are defining $r_i^2=a_1\pm\sqrt{a_2\pm\sqrt{a_3\pm a_4}}$ . I apologize for being all over the map with my choices of notation.

I too see no obvious pattern, but this allows a huge step toward finding a generating formula. Keep in mind, it is already currently known that there exists an infinite number of k=4 ladders, so all we are doing so far is catching up with the bar. The real challenge is understanding the k=4 case thoroughly enough to make the leap to the k=5 case. No squaring ladders for k=5 are currently known, according to a Carl Pomerance textbook.

I would be interested in seeing pseudocode for the algorithm you came up with to sift through them so fast. You found a highest $a_1$ value of 250 million!

**alunw** · August 29th 2009, 03:16 PM

Thanks - I would never have been able to work out these formulas without the work you did. I don't think my code is that fast - at least it hasn't found any more yet. However, I think it's about as efficient as you can get without creating VERY large arrays to remember places where it isn't going to be worth looking. In fact I am repeating some work unnecessarily, and the penalty looks to be getting bigger as I check bigger values. I think we have found ones that weren't known before, because all but the first I have posted are different from anything that would be got by multiplying a base solution by powers of x.

I'll attach the complete code of my program as it is quite small. I wrote it using an old Microsoft C++ dialect. To change it to proper C++ change __int64 to long long. The code is actually nearly in C. I don't have a large integer library handy, so I have to be careful about avoiding overflow. All the inner loops are essentially the same, so could be replaced by some kind of inner function or template, but I just did it the quick and dirty way.

Code:

#include <stdio.h>

void swap(unsigned long &a,unsigned long &b)
{
  unsigned long temp = a;
  a = b;
  b = temp;
}

void swap(__int64 &a,__int64 &b)
{
  __int64 temp = a;
  a = b;
  b = temp;
}

/**/

unsigned int hcf(unsigned long x,unsigned long y)
{
  if (x == y || !y)
    return x;
  if (!x)
    return y;

  for (;;)
  {
    if (x > y)
    {
      x = x % y;
      if (!x)
        return y;
    }
    else
    {
      y = y % x;
      if (!y)
        return x;
    }
  }
}

int main()
{
  unsigned long height;
  unsigned long a,b,c,d,e,f,g,h;
  __int64 sum;
  __int64 diff;
  double cond2_1,cond2_2;

  for (height = 3;height <= 65535; height += 2)
  {
    for (a = 1; a <= height; a += 2)
    {	 
      b = height - a;
      if (hcf(a,b) > 1)
        continue;
      sum = (__int64) a * (__int64) a + (__int64) b * (__int64) b;
      d = b;
      for (c = a+2;; c += 2)
      {
        diff =  (__int64) c * (__int64) c;
        if (diff > sum)
          break;
        diff = sum - diff;
        while ( (__int64) d * (__int64) d > diff)
          d -= 2;
        if ( (__int64) d * (__int64) d == diff)
        {
	  f = d;
          for (e = c+2;; e += 2)
          {
            diff =  (__int64) e * (__int64) e;
            if (diff > sum)
              break;
            diff = sum - diff;
            while ( (__int64) f * (__int64) f > diff)
              f -= 2;
            if ( (__int64) f * (__int64) f == diff)
            {
              h = f;
              for (g = e+2;; g += 2)
              {
                diff =  (__int64) g * (__int64) g;
                if (diff > sum)
                  break;
                diff = sum - diff;
                while ( (__int64) h * (__int64) h > diff)
                  h -= 2;
                if ( (__int64) h * (__int64) h == diff)
                {
                  unsigned long a1,b1,c1,d1,e1,f1,g1,h1;
                  __int64 ab,cd,ef,gh;
		  __int64 wanted;
                  a1 = a;
                  b1 = b;
                  ab = (__int64) a * (__int64) b;
                  c1 = c;
                  d1 = d;
                  cd = (__int64) c * (__int64) d;
                  e1 = e;
                  f1 = f;
                  ef = (__int64) e * (__int64) f;
                  g1 = g;
                  h1 = h;
                  gh = (__int64) g * (__int64) h;
		  /* Make ab the smallest and cd the largest value
                     by first ensuring that ab <= cd and ef <= gh
                     and then putting the smaller of ab and ef in ab
                     and the larger of cd and gh in cd */
                  if (cd < ab)
                  {
                    swap(a1,c1);
                    swap(b1,d1);
                    swap(ab,cd);
                  }
                  if (gh < ef)
                  {
                    swap(e1,g1);
                    swap(f1,h1);
                    swap(ef,gh);
                  }
                  if (ef < ab)
                  {
                    swap(a1,e1);
                    swap(b1,f1);
                    swap(ab,ef);
                  }
                  if (cd < gh)
                  {
                    swap(c1,g1);
                    swap(d1,h1);
                    swap(cd,gh);
                  }
                  wanted = (cd-ef)*(cd+ef);
                  if ((gh-ab)*(gh+ab) == wanted)
                  {
                    printf("Hurray we have an answer! %d %d %d %d %d %d %d %d\n",a1,b1,c1,d1,e1,f1,g1,h1);
                    printf("%I64d %I64d %I64d %I64d %I64d %I64d\n",
                           (__int64) a1 * (__int64) a1 +
                           (__int64) b1 * (__int64) b1,
                           (__int64) c1 * (__int64) c1 +
                           (__int64) d1 * (__int64) d1,
                           (__int64) e1 * (__int64) e1 +
                           (__int64) f1 * (__int64) f1,
                           (__int64) g1 * (__int64) g1 +
                           (__int64) h1 * (__int64) h1,
                           (__int64) a1*(__int64) a1*(__int64) b1*(__int64) b1+
                           (__int64) c1*(__int64) c1*(__int64) d1*(__int64) d1,
                           (__int64) e1*(__int64) e1*(__int64) f1*(__int64) f1+
                           (__int64) g1*(__int64) g1*(__int64) h1*(__int64) h1);
                           
                  }
                }
              }
            }
          }
        }
      }
    }
  } 
  return 0;
}

This code could be improved by calculating a2 and a3 as well, though I suspect we might get out of range. I hadn't worked out the formulas when I wrote it, and did the examples I did do using Windows calc.
Your parameters give the roots more naturally, but I think mine are overall slightly more elegant, because all the sides of each component of the triple appear in a natural way somewhere in the expressions for a1, a2, a3 or a4. I suspect I could improve my expression for a3 but it looked messy . The division into odd and even helps with the search, but may be disguising hidden patterns. One thing I did notice is that in each of the four pairs of generators of the triples one is divisible by 3, and at least one of these is odd and at least one is even. There might be similar patterns with other primes congruent to 3 mod 4, as the hypotenuse seems to want to avoid being divisible by these primes (I don't think being divisible by 9 or 49 etc is ruled out a priori, but all the hypotenuses so far are products of primes of the form 4n+1)

I'm afraid I can't look at your spreadsheet at the moment as I don't have Excel handy. You should be able to save the file in .CSV format or .XML and then it would be legible to people who don't have Office - I guess quite a few people on this forum are Linux users.

If you could formulate the conditions for k=5 in a similar way to what you did for k=4 I could try searching. However, it would probably need a large integer library. There are undoubtedly plenty of candidates where there are at least five triples with the same hypotenuse - similar code without the innermost checks for k=4 finds dozens of cases per second. The first occurs with hypotenuse 5525. However I suspect it might be the case that the number of conditions is such that there might well be no actual solutions for k=5 or at least only finitely many, whereas I suspect there are infinitely many distinct solutions for k=4.

**Media_Man** · August 29th 2009, 04:31 PM

Cool. I'll look at the code and see if I can't figure a way to speed things up. I'm thinking that $a_1$ must factor in a very specific way that can be taken advantage of. This site won't let me upload CSV and my computer won't save the file as XML, so we are just SOL for now.

Don't get too excited about building a program to search for k=5 solutions. As there are none currently known, we have to assume that if any exist they are probably ridiculously large and outside our computing capacity. I think the likeliest result to shoot for is proving none exist or placing a rather large lower bound on them if they do exist.

**alunw** · August 29th 2009, 10:53 PM

Here's one more triple, this time with a1=532946005=5*17*53*281*421

T(8743,21366),T(17769,14738),T(20583,10454),T(1220 1,19598)

After my last post I realised that for k=5 we would of course need to find not 5 but 8 triples all with the same lower bound. That on its own means that the minimum value of a1 to consider is 27625. However, such sets of 8 triples are very plentiful - it will be the extra conditions that makes it difficult.

As far as speeding up the code goes I wish you luck. I doubt factorising will help much, though it might just be worth checking that "sum" is plausible in the outer loop, from a table of precomputed primes. However one of the fastest known programs for finding all the prime numbers actually works by counting up the number of ways numbers can be expressed in various quadratic forms including a^2+b^2. The way the code is structured means that most time will be devoted to the values of sum that are the most plausible.

I've got some code that can in principle enumerate all the prime numbers up to 2^64. It takes 15 seconds or less to get to 2^32 and about 60 seconds to get to 2^33. I used it for factorising some of the a1 values in my list that weren't obviously factors.

Another thing I've noticed is that while the factors of a1 are all of the form 4n+1 some primes of this form are proving reluctant to appear: notably 89 and 97.

**jamix** · August 29th 2009, 11:29 PM

That a lot of cases found. Your going the distance.

Btw, since factorization is generally slow, perhaps you should consider downloading pari/gp, and running your programs here, since the software has fast methods for integer factoring.

Since k = 5 is likely undoable, I'm writing a post in the other thread which is a survey of alternatives to seeking polynomials of the form $P_k(x) = ((..(x^2 - a_1)^2 - a_2)^2 - .......)^2 - a_k^2$ which we've currently been working with.

Thread: Integer Solutions?

LinkBack

Thread Tools

Display

Integer Solutions?

Critical Mistake

Rigorous Conditions

Wow!

Similar Math Help Forum Discussions

No integer Solutions

integer solutions

No integer solutions to x^10 + px^9 - qx^7 + rx^4 - s = 0

Integer Solutions

Integer solutions to a^2+b^2=c^3

Search Tags