solutions to a linear equation and perfect square

smslca · 05-08-2010 07:38AM #1

1) Is there any way to find integer solutions for a linear equation ax+by=c, with a,b,c known and without having an another equation to substitute in the above one.
ex : 3x+y=394;

Is there any worst case for c being very large.

2)Is there any easy and fastest way to get t=115734564=9*(3586^2)
from t1=116964=9*(12996) to "t" using the equation t=(81*x*x)+(390240*x)+116964

Actually Here if we dont know the value of "t" and searching for a perfect square using the above equation. "t" is the first perfect square we ecounter at x, and all below x cannot generate a perfect square.

answer is t=280 , can we get "x" in the shortest way without substituting 1,2,3,...........280 respectively.
i.e how to get from 12996 to a perfect square using the equation.

MathsManiac · 05-08-2010 07:55PM

1) is a linear diophantine equation. It has infinitely many solutions if the greatest common divisor of a and b also divides c. Otherwise it has no solutions. (Equivalently, if you can "cancel down" the equation to its simplest integer form, there is a solution if a and b have no common factor.)

The extended Euclidean algorithm can be used to solve it, and is computationally efficient.

See here:
http://en.wikipedia.org/wiki/Diophantine_equation#Linear_Diophantine_equations

2) Can you phrase the question a bit differently? It's not clear to me what you're trying to do.

smslca · 07-08-2010 07:13AM

MathsManiac wrote: »

2) Can you phrase the question a bit differently? It's not clear to me what you're trying to do.

u can see t1=116964 and t= (81x^2)+390240x+(t1)
So we have used t1 in t . i.e by adding something to t1 we get t.

also t1= 9*12996;
t = 9*(3568^2);

so by substituting x=280 in (81x^2)+390240x and adding it to t1 we get 12996 to 3568^2;

My question is : If we do not know the value of "t" and by substituting the integer values in
the equation of "t" , to search for a value of "t" which gives a perfect square, we will get it at x=280. So is there any fastest way(method) to say "x" value is 280 without substuting the whole integer values.

MathsManiac · 08-08-2010 11:55PM

You still haven't said what you're trying to do.

i.e. What are you given, and what are you trying to find?

smslca · 09-08-2010 03:37PM

MathsManiac wrote: »

You still haven't said what you're trying to do.

i.e. What are you given, and what are you trying to find?

""So is there any fastest way(method) to say "x" value is 280 without substuting the whole integer values.""

Doesnt it seem like a question?

CJC86 · 09-08-2010 04:41PM

I'm with MathsManiac on this one, please state the question clearly.

Would I be correct in saying the question is as follows?

"Given an integer t1, is there a method to find the smallest integer x such that t=81x^2 +309240x+t1 is a perfect square?"

smslca · 15-08-2010 04:33AM

CJC86 wrote: »

I'm with MathsManiac on this one, please state the question clearly.

Would I be correct in saying the question is as follows?

"Given an integer t1, is there a method to find the smallest integer x such that t=81x^2 +309240x+t1 is a perfect square?"

yes. that's the question I am asking.

equivariant · 17-08-2010 05:19PM

CJC86 wrote: »

I'm with MathsManiac on this one, please state the question clearly.

Would I be correct in saying the question is as follows?

"Given an integer t1, is there a method to find the smallest integer x such that t=81x^2 +309240x+t1 is a perfect square?"

Observe that [latex] 81x^2+309240x+t_1 = (9(x+1909)-1)^2-295152400+t_1 [/latex]

So the answer to the above question follows if you can solve the following problem (with z = 9(x+1909)-1 and with m = t1-295152400.

Given an integer m, find all integers z such that [latex] z^2 + m [/latex] is a perfect square.

This can be solve as follows. Suppose that [latex]z^2 +m= y^2[/latex]. Then [latex] m = y^2-z^2 = (y-z)(z+y)[/latex] Now there are only finitely many ways to factor m in integers, so we get finitely many possible systems of equations.
[latex] z-y = a [/latex]

[latex]z+y = b[/latex]

(where ab=m)
These systems of equations can be solved using Gaussian elimination to find all possible values of z. Going back to the original problem this means, we can list off all possible values of x that make 81x^2 +309240x+t1 a perfect square (there are only finitely many for any given t1). Then we can easily identify the smallest.

solutions to a linear equation and perfect square

Comments