How to solve for solutions to the diophantine 5b^2*c^2 = 4a^2(b^2+c^2)

  • Thread starter SeventhSigma
  • Start date
In summary, it seems that the person is advocating for a brute force approach to solving this equation. They seem to be unfamiliar with how to factor a square equation.
  • #36
LittleNewton said:
How can I judge? Can you be more specific?

I simplified all results using the gcd's.
then I tried randomly picking primitives,
and all seemed legitimate...

By trial and error, I found that the cube root of limit is enough for the range.
However this might be by chance or might depend on that particular limit.

And that is still a lot of (primitive) starting points...
 
Physics news on Phys.org
  • #37
micromass said:
Finding all the solutions of these is not very hard. This contains some nice information: http://mathcircle.berkeley.edu/BMC4/Handouts/elliptic/node4.html [Broken]

I did case (2) explicitely, and the solutions of [itex]4d^2+e^2=5f^2[/itex] are given by

[tex]d= m^2 - 2mn - 4n^2,~~ e= m^2 + 8mn - 4n^2,~~ f= m^2 + 4n^2[/tex]

where we can take m and n coprime. We still got to take care that d and e are coprime, since they might not be in some cases. If we want f and e to be odd, then it clearly suffices to ask that m is odd.

I also read a lot of papers on that subject.
Most just state that these generating functions generate infinitely many solutions,
but they are not all the solutions, meaning there might be more.

They sometimes use modular arithmetic to show the non-existence of a solution.

I would like to know when we are sure that we have found all the primitives.
 
Last edited by a moderator:
  • #38
LittleNewton said:
I also read a lot of papers on that subject.
Most just state that these generating functions generate infinitely many solutions,
but they are not all the solutions, meaning there might be more.

They sometimes use modular arithmetic to show the non-existence of a solution.

I would like to know when we are sure that we have found all the primitives.

I'm pretty sure that those are all the solutions. Did you check the link in my post? There they give a proof (or at least an argument) for why these are all the solutions.
 
  • #39
LittleNewton said:
By trial and error, I found that the cube root of limit is enough for the range.
However this might be by chance or might depend on that particular limit.

And that is still a lot of (primitive) starting points...

false
 
  • #40
SeventhSigma said:
Hint:

Reduce the cases you know are correct to their primitives

Check which bounds produce those primitives

Please don't post unless you post your solution.
 
  • #41
micromass said:
I'm pretty sure that those are all the solutions. Did you check the link in my post? There they give a proof (or at least an argument) for why these are all the solutions.

Yes, I checked it. Somehow only they (this paper and others)
only confidently talk about primitives in case of the basic Pythagorean triples.

I want to know :

1) if I am supposed to extent to negative m,n values
2) what ranges of m & n will give me all the primitives

For example if I want to find all solutions below a certain limit, say 10K,
what is the complete set of primitives I need to start with?
 
  • #42
LittleNewton said:
Wow, that was fast!
My reply also got deleted...

I'm sorry about this thread. I should have locked it when I had the chance. Now I let it degenerate into a mess. My sincere apologies to all the readers.
 
  • #43
LittleNewton said:
Yes, I checked it. Somehow only they (this paper and others)
only confidently talk about primitives in case of the basic Pythagorean triples.

I was always under the impression that we could find all the rational points on a given conic. I'll admit that my knowledge about this is very small. But in the book "Rational points on elliptic curves" by Silverman and Tate, they certainly seem to indicate that all the rational points on a conic can be found with this method.

Can you explain me what makes this situation different from the Pythagorean triple situation?
 
  • #44
micromass said:
I was always under the impression that we could find all the rational points on a given conic. I'll admit that my knowledge about this is very small. But in the book "Rational points on elliptic curves" by Silverman and Tate, they certainly seem to indicate that all the rational points on a conic can be found with this method.

Can you explain me what makes this situation different from the Pythagorean triple situation?

I guess I am not very good at this either
(otherwise I would have found the solution by now :smile:)

I think they are both the same. I want to know where to stop
finding the primitives and jump to finding the all other non-primitive solutions.
If the answer is that m,n should span 0..limit, then that is a really big range.
I want to know if this is the most efficient way, i.e. we can't avoid the big search.
I tried to trim it by jumping on evens for m, and on odds for n, etc.
but each case missed some solutions. I tried squareroot(limit), which worked.
I tried cuberoot(limit), seemed to work, but I guess it was case-specific.
 
  • #45
LittleNewton said:
I guess I am not very good at this either
(otherwise I would have found the solution by now :smile:)

I think they are both the same. I want to know where to stop
finding the primitives and jump to finding the all other non-primitive solutions.
If the answer is that m,n should span 0..limit, then that is a really big range.
I want to know if this is the most efficient way, i.e. we can't avoid the big search.
I tried to trim it by jumping on evens for m, and on odds for n, etc.
but each case missed some solutions. I tried squareroot(limit), which worked.
I tried cuberoot(limit), seemed to work, but I guess it was case-specific.

It might be that the only problem is efficiency:
How can we efficiently generate all solutions?
i.e. how can we avoid spending time on degenerate solutions,
because it seems like there are lots of them...
 
  • #46
Dodo said:
Hi, ramsey2879,
what you found is a consequence of a theorem that says that a number can be expressed as a sum of squares if and only if its prime factors congruent to 3 mod 4 appear with an even power in the factorization. For example, 2x5x7 is not expressible as a sum of squares, 2x5x7x7 is (490 = 7^2 + 21^2), 2x5x7x7x7 is not, and so on.

My conjecture is stronger than that since 9*13 is an even power of 3 times a prime of the form 4n +1. 5*9 and 5*113^2 cannot be put into the form 4n^2+m^2 with n coprime to m [even] though 9 and 81 are even powers of 3
 
Last edited:
  • #47
LittleNewton said:
I also read a lot of papers on that subject.
Most just state that these generating functions generate infinitely many solutions,
but they are not all the solutions, meaning there might be more.

They sometimes use modular arithmetic to show the non-existence of a solution.

I would like to know when we are sure that we have found all the primitives.

My experience with Mathematica at this problem leads me to conjecture that the number of primitives is 1 if f is a power of 5, 2 if a power of a prime of the form 4n + 1 or 5 times a power of such a prime, for a product of n distinct primes of the form 4n + 1 or 5 times such a product, the number of primitives is 2^n, If f containes a factor of the form 4n+3 there is no primitive root.
My Mathematical program (for odd f )is the following:
t = 1;
tx = t + 401;
While[t < tx,
Print[t, Solve[
4*x*x + y*y == 5*t*t && GCD[x, y] == 1 && x > 0 && y > 0, {x, y},
Integers]]; t += 4]
for investigating a specific product like t = 13*17*37*29 I set tx = 1.
 
Last edited:
  • #48
I have a further observation: If 4x^2+y^2=f has at least one primitive solution and 5 does not divide f, then there are two primitive solutions for f (not divisible by 5) in 4x^2 + y^2 = 5f, (x1,y1) and (x2,y2) all positive values such that x2*y1 +/- x1*y2 = +/- 2f^2). Never mind my post about f being prime, f = 29*17 is a counter example to that conjecture.
Below is a proof;
The pell equation 4a^2+b^2 = 5f^2 has the solution set a = m^2 -2mn -4n^2, b = m^2 +8mn -4n^2, f = m^2 + 4n^2. If (m,n) form one solution set then (m,-n) will form a 2nd solution set (p,q). Also, my experience is that qa + pb = 2*f^2.

We need to show that q*(m^2-2mn-4n^2) + p*(m^2+8mn -4n^2) = 2*(m^2+4n^2)^2.

Substitute q =b'(m,-n) =m^2-8mn-4n^2 and p = a'(m,-n) =m^2+2mn-4n*2
then (m^2-8mn-4n^2)*(m^2-2mn-4n^2) + (m^2+2mn-4n^2)*(m^2+8mn-4n^2) =

m^4 -10m^3*n+(16-8)m^2*n^2+40n^3*m+16n^4 + m^4 +10m^3*n +
(16-8)m^2*n^2 - 40n^3*m + 16n^4 =

2*(m^4 + 8m^2*n^2 + 16n^4) = 2*(m^2+4n^2). Q.E.D.
 
Last edited:
  • #49
SeventhSigma said:
false
This was in response to LittleNewton saying f^3 appears to be an upper limit for searching for primitive solutions.

If you have some information on the upper range for searching for primitive solutions being the cube of f then would you provide it? I am not sure what you have in mind but am interested.
 
  • #50
LittleNewton said:
By trial and error, I found that the cube root of limit is enough for the range.
However this might be by chance or might depend on that particular limit.

And that is still a lot of (primitive) starting points...

I did a bit more experiments and found that I can get the range check down to
order of forth root: 2*limit^(0.25) to be precise.

Also using gcd = 1, skips many candidates.
Focusing on signs and parity also cuts it down.

I kept a hash of the results to avoid repeats,
but if I a nice method is outlined there shouldn't be a need
to store the results.
 
  • #51
LittleNewton said:
I did a bit more experiments and found that I can get the range check down to
order of forth root: 2*limit^(0.25) to be precise.

Also using gcd = 1, skips many candidates.
Focusing on signs and parity also cuts it down.

I kept a hash of the results to avoid repeats,
but if I a nice method is outlined there shouldn't be a need
to store the results.
I don't know what you mean by limit. I don't see why using gcd limits candidates should matter since if (d,e) > 1 then GCD(d,e,f) > 1 and I thought SeventhSigma was only interested in primitive solutions. As for limiting d,e to positive, it seems trival to test both d and -d when testing d will suffice, same for e.; but, then maybe you have a program to compute d and e that will give negative input. If so then go for it.
 
  • #52
ramsey2879 said:
I don't know what you mean by limit. I don't see why using gcd limits candidates should matter since if (d,e) > 1 then GCD(d,e,f) > 1 and I thought SeventhSigma was only interested in primitive solutions. As for limiting d,e to positive, it seems trival to test both d and -d when testing d will suffice, same for e.; but, then maybe you have a program to compute d and e that will give negative input. If so then go for it.

I am trying to get the primitive solutions under a certain limit.
The origin of this idea was micromass' suggetion:

micromass said:
Finding all the solutions of these is not very hard. This contains some nice information: http://mathcircle.berkeley.edu/BMC4/Handouts/elliptic/node4.html [Broken]

I did case (2) explicitely, and the solutions of [itex]4d^2+e^2=5f^2[/itex] are given by

[tex]d= m^2 - 2mn - 4n^2,~~ e= m^2 + 8mn - 4n^2,~~ f= m^2 + 4n^2[/tex]

where we can take m and n coprime. We still got to take care that d and e are coprime, since they might not be in some cases. If we want f and e to be odd, then it clearly suffices to ask that m is odd.

In the interest of generating the primitives efficiently, and
I am trying to eliminate the computation of gcd's if I can,
because there are too many degenerate (multiple) cases.
I think the solution would be along the lines of generating a solution
set similar to tree of primitive Pythagorean triples.
 
Last edited by a moderator:
  • #53
I edited the last post in page three to note that if d(m,n) = m^2-2mn-4n^2 and that if e(m,n) = m^2+8mn -4n^2 is a solution for f = m^2 + 4*n^2 then so are d(m,-n) and e(m,-n). Moreover, I proved that d(m,n)*e(m,-n) + d(m,-n)*e(m,n) equals 2f^2, that is 2*(m^2+4n^2)^2.
Currently, I am looking at a method of using matrix operations with the set {{d,e},{d'e'}} to get from a solution for f = r to a solution for f=r^2. What is interesting is that the same matrix operation can be repeated n times to go from a solution for f = 1 to a solution for f = r^n. This may be a precurser to a general matrix operation for going from f=r to f = r*s, but this later bit may just be wishful thinking.
 
Last edited:
  • #54
ramsey2879 said:
I edited the last post in page three to note that if d(m,n) = m^2-2mn-4n^2 and that if e(m,n) = m^2+8mn -4n^2 is a solution for f = m^2 + 4*n^2 then so are d(m,-n) and e(m,-n). Moreover, I proved that d(m,n)*e(m,-n) + d(m,-n)*e(m,n) equals 2f^2, that is 2*(m^2+4n^2)^2.
Currently, I am looking at a method of using matrix operations with the set {{d,e},{d'e'}} to get from a solution for f = r to a solution for f=r^2. What is interesting is that the same matrix operation can be repeated n times to go from a solution for f = 1 to a solution for f = r^n. This may be a precurser to a general matrix operation for going from f=r to f = r*s, but this later bit may just be wishful thinking.
Since the two solution sets for f= r form a matrix {{a,b},{p,q}} and the solution set for f=1 is {{1,-1},{1,1}} I wondered what

if we did repeated matrix operation with a matrix r' = r/1 so that 1*r' = r, r*r' = the solution set for f=r^2 etc. Thus r' = {{4n^2-m^2, 8mn},{-2mn, 4n^2 - m^2}}.

As an example, subsitute m=1,n=2: r' = {{15,16},{-4,15}}.

{{1,-1},{1,1}}*r' ={{19,1},{11,31}}

{{19,1},{11,31}}*r'={{281,319},{41,641}}

{{281,319},{41,641}*r' ={{2939,9281},{-1949,10271}}

{{2939,9281},{-1949,10271}}*r' ={{6961,186239},{-70319,122881}}

etc.

These are the solution sets for f =17, 17^2, 17^3, 17^4, etc. Note that the matrix {{1,-1},{1,1} can be changed to any sets long as there are 3 of one sign, and 1 of the other, the same matrix operations will give the solution sets for powers of 17, only the format, i.e. the order or signs,etc. will be changed. However, you can't mess with the solution sets for positive powers of a number or the matrix operation will likely give out garbage.
 
  • #55
ramsey2879 said:
Since the two solution sets for f= r form a matrix {{a,b},{p,q}} and the solution set for f=1 is {{1,-1},{1,1}} I wondered what

if we did repeated matrix operation with a matrix r' = r/1 so that 1*r' = r, r*r' = the solution set for f=r^2 etc. Thus r' = {{4n^2-m^2, 8mn},{-2mn, 4n^2 - m^2}}.

As an example, subsitute m=1,n=2: r' = {{15,16},{-4,15}}.

{{1,-1},{1,1}}*r' ={{19,1},{11,31}}

{{19,1},{11,31}}*r'={{281,319},{41,641}}

{{281,319},{41,641}*r' ={{2939,9281},{-1949,10271}}

{{2939,9281},{-1949,10271}}*r' ={{6961,186239},{-70319,122881}}

etc.

These are the solution sets for f =17, 17^2, 17^3, 17^4, etc. Note that the matrix {{1,-1},{1,1} can be changed to any sets long as there are 3 of one sign, and 1 of the other, the same matrix operations will give the solution sets for powers of 17, only the format, i.e. the order or signs,etc. will be changed. However, you can't mess with the solution sets for positive powers of a number or the matrix operation will likely give out garbage.
I generalized the above solution. Given a,b,m,n, then r' = {{a*a*n*n-m*m,2*a*a*m*n/b},{-2*m*n*b,a*a*n*n-m*m}} . Now
{{1,-1},{1,1}}*r' equals {{x1,y1},{x2,y2}} where (x1,y1) and (x2,y2) are solution sets for a^2*x^2 + b^2*y^2 = (a^2+b^2)*N^2
{{1,-1},{1,1}}*r'*r' equals {{x3,y3},{x4,y4}} ... are solution sets for a^2*x^2+b^2y^2 = (a^2+b^2)*N^4
{{1,-1},{1,1}}*r'*r'*r' = {{x5,y5},{x6,y6}} ... are solution sets for a^2*x^2 + b^2*y^2 = (a^2+b^2)*N^6
etc.
 
  • #56
ramsey2879 said:
I generalized the above solution. Given a,b,m,n, then r' = {{a*a*n*n-m*m,2*a*a*m*n/b},{-2*m*n*b,a*a*n*n-m*m}} . Now
{{1,-1},{1,1}}*r' equals {{x1,y1},{x2,y2}} where (x1,y1) and (x2,y2) are solution sets for a^2*x^2 + b^2*y^2 = (a^2+b^2)*N^2
{{1,-1},{1,1}}*r'*r' equals {{x3,y3},{x4,y4}} ... are solution sets for a^2*x^2+b^2y^2 = (a^2+b^2)*N^4
{{1,-1},{1,1}}*r'*r'*r' = {{x5,y5},{x6,y6}} ... are solution sets for a^2*x^2 + b^2*y^2 = (a^2+b^2)*N^6
etc.[/QUOTEI] I forgot to ask the obvious questions, I know that for a=4,b = 1 the above formulas give all solution sets except for reordering and sign. Is this true for all a and b? If not how can it be modified or what needs to be added?
 
Last edited:
<h2>1. How do you solve for solutions to the diophantine 5b^2*c^2 = 4a^2(b^2+c^2)?</h2><p>To solve for solutions to this diophantine equation, you can use the method of infinite descent. This involves finding a smaller solution to the equation and then using that solution to find an even smaller solution, continuing until you reach the smallest possible solution.</p><h2>2. What is the significance of the diophantine equation 5b^2*c^2 = 4a^2(b^2+c^2)?</h2><p>This equation is significant because it is an example of a diophantine equation, which is a type of mathematical problem that involves finding integer solutions to polynomial equations. These types of equations have been studied for centuries and have important applications in number theory and cryptography.</p><h2>3. Can the diophantine equation 5b^2*c^2 = 4a^2(b^2+c^2) have infinitely many solutions?</h2><p>Yes, it is possible for this equation to have infinitely many solutions. For example, if we let b and c be any positive integers and let a = 0, then the equation will have infinitely many solutions. However, there are also cases where the equation has a finite number of solutions, such as when b and c are both 0.</p><h2>4. What is the role of the Pythagorean triple in solving this diophantine equation?</h2><p>The Pythagorean triple (3, 4, 5) plays a crucial role in solving this diophantine equation. This triple satisfies the equation 5b^2*c^2 = 4a^2(b^2+c^2) when a = 3, b = 4, and c = 5. Using this solution, we can then use the method of infinite descent to find smaller solutions to the equation.</p><h2>5. Are there any real-world applications of the diophantine equation 5b^2*c^2 = 4a^2(b^2+c^2)?</h2><p>Yes, this diophantine equation has applications in cryptography, specifically in the field of elliptic curve cryptography. This equation is used to generate points on an elliptic curve, which are then used in the encryption and decryption of data. It is also used in the study of rational points on elliptic curves, which has implications in number theory and algebraic geometry.</p>

1. How do you solve for solutions to the diophantine 5b^2*c^2 = 4a^2(b^2+c^2)?

To solve for solutions to this diophantine equation, you can use the method of infinite descent. This involves finding a smaller solution to the equation and then using that solution to find an even smaller solution, continuing until you reach the smallest possible solution.

2. What is the significance of the diophantine equation 5b^2*c^2 = 4a^2(b^2+c^2)?

This equation is significant because it is an example of a diophantine equation, which is a type of mathematical problem that involves finding integer solutions to polynomial equations. These types of equations have been studied for centuries and have important applications in number theory and cryptography.

3. Can the diophantine equation 5b^2*c^2 = 4a^2(b^2+c^2) have infinitely many solutions?

Yes, it is possible for this equation to have infinitely many solutions. For example, if we let b and c be any positive integers and let a = 0, then the equation will have infinitely many solutions. However, there are also cases where the equation has a finite number of solutions, such as when b and c are both 0.

4. What is the role of the Pythagorean triple in solving this diophantine equation?

The Pythagorean triple (3, 4, 5) plays a crucial role in solving this diophantine equation. This triple satisfies the equation 5b^2*c^2 = 4a^2(b^2+c^2) when a = 3, b = 4, and c = 5. Using this solution, we can then use the method of infinite descent to find smaller solutions to the equation.

5. Are there any real-world applications of the diophantine equation 5b^2*c^2 = 4a^2(b^2+c^2)?

Yes, this diophantine equation has applications in cryptography, specifically in the field of elliptic curve cryptography. This equation is used to generate points on an elliptic curve, which are then used in the encryption and decryption of data. It is also used in the study of rational points on elliptic curves, which has implications in number theory and algebraic geometry.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
584
  • Linear and Abstract Algebra
Replies
24
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
178
  • Calculus and Beyond Homework Help
Replies
4
Views
943
Replies
10
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
762
  • Linear and Abstract Algebra
Replies
14
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
1K
Replies
7
Views
782
  • Linear and Abstract Algebra
Replies
2
Views
918
Back
Top