Displayname Posted November 13, 2017 Share Posted November 13, 2017 Hello everyone, Im new in this forum and in advance I would like to apologise for possibly posting this thread in a wrong place. I am learning mathematics and I came across this problem that I can't find a solution for: x^2 - 4^2 = 1000000 , find all possible integer solutions for x and y. Being an amateur mathematician I tried to understand this problem using system of equations technique and instead of million i used a prime number (5) as an anwser and turned this equation into difference of squares: (x+2y)(x-2y) = 5; 5 is prime, has two divisors -> 5, 1; (x+2y) = 5 (x-2y) = 1 2y - 2y = 0 (y is out) 2x = 6 x = 3; 3+2y = 5 2y = 2 y = 1; Anwser : x = 3, y = 1; I tried to do similar thing with a million: (x+2y)(x-2y) = 1000000 let's say (x+2y) = 1000 and (x-2y) = 1000 (x+2y)= 1000 (x-2y) = 1000 2x = 2000 x=1000 y = 0; But how do you find other solutions to this equation ? I found these anwsers using brute force algorithm in java: [[31258, 15621], [12520, 6240], [6290, 3105], [2600, 1200], [1450, 525], [1000, 0]] is there a formula for finding all of the Integer possibilities? Where should I look ? Thank you Link to comment Share on other sites More sharing options...
Country Boy Posted November 14, 2017 Share Posted November 14, 2017 (edited) I don't know why you are using "brute force" as you call it when you already had the solution staring at you! You have "either x+ 2y= 5 or x- 2y= 1". If x+ 2y= 5 then, for every y, x= 5- 2y. Solutions, in (x, y) form, are (5, 0). (3, 1), (1, 2). (-1. 3), ..., (5- 2y, y) for y non-negative and (7. -1), (9. -2). (11, -3),... for y negative. If x- 2y= 1 then, for every y, x= 2y+ 1. Solutions are (1, 0), (3, 1). (5, 2), (7, 3), ... for y non-negative and (-1, -1), (-3, -2), (-5, -3), ... for y negative. Those at are the solutions: $\{(5- 2y, y)\}\cup\{(2y+1, y)\}$ for y any integer. Edited November 14, 2017 by Country Boy Link to comment Share on other sites More sharing options...
Displayname Posted November 26, 2017 Author Share Posted November 26, 2017 (edited) On 14/11/2017 at 2:28 AM, HallsofIvy said: I don't know why you are using "brute force" as you call it when you already had the solution staring at you! You have "either x+ 2y= 5 or x- 2y= 1". If x+ 2y= 5 then, for every y, x= 5- 2y. Solutions, in (x, y) form, are (5, 0). (3, 1), (1, 2). (-1. 3), ..., (5- 2y, y) for y non-negative and (7. -1), (9. -2). (11, -3),... for y negative. If x- 2y= 1 then, for every y, x= 2y+ 1. Solutions are (1, 0), (3, 1). (5, 2), (7, 3), ... for y non-negative and (-1, -1), (-3, -2), (-5, -3), ... for y negative. Those at are the solutions: $\{(5- 2y, y)\}\cup\{(2y+1, y)\}$ for y any integer. 1 1 1 I was supposed to write a simple java app which finds all x's and y's that satisfy x^2 - ny^2 = k, where x, y >= 0 and x, y <= k Other conditions are : (x,y) are Natural numbers and 'n' is a square number. At first, I tried to work the equation out on paper and it was easy to figure out solutions for prime numbers, that only have two divisors, but I couldn't understand how could you figure out all of the variables I mentioned above when 'k' can be any Natural number you can think of without using brute force. After a little research, I used this approach. Set 'Pn' has all 'x's' and 'y's' that satisfy the equation x^2 - ny^2 = k, while x and y are Natural numbers and n is a square number. Set 'A' has divisors of k (i) and quotients (j) that come from dividing k by divisor (i) which is inside set 'A'. We don't take all of the divisors of k (for ex. k = 9009), our largest divisor of 'k' inside set 'A' is the one closest to the square root of 'k'. A square root of 9009 is approximately 95, closest number to 95 which divides 9009 is 91, therefore, the divisors of k, that are inside set 'A' are: i{1, 3, 7, 9, 11, 13, 21, 33, 39, 63, 77, 91}; Now, let's divide 9009 by all of the divisors above and get a final set 'A', that has all of the factors needed in further calculations: { (1; 9009) , (3; 3003), (7; 1287), (9;1001), (11;819), (13;693), (21;429), (33;273), (39;231), (63; 143), (77;117), (91;99) } (In the picture, I've missed (7; 1287) element, sorry). Now, let's figure out values of 'x' and 'y'. For example we'll only take first two elements from set 'A', and those are : { (1;9009), (3; 3003) }. x = ( j + i ) / 2; y = ( j - x ) / (square root of 'n', in our case n = 4, n = d^2, d = 3) = (j-x) / 3 Proof: x^2 - 9y^2 = (x+3y)(x-3y) = 9009, create a system of equations x + 3 y = j = 9009 x - 3 y = i = 1 combine x + 2y + x + (-2y) = 9010, 2x = 9010, x = 9010 / 2 = 4505 x = ( j + i ) / 2 = ( 9009 + 1 ) / 2 = 4505 we've found 'x', now, let's find 'y' 4505 + 3y = 9009 3y = 9009 - 4505 = 4504 y = 4504 / 3 = 1501.3333333333.... y = ( 9009 - 4505 ) / 3 = 1501.3333333333... These values cannot be included in our 'P9' set because 'y' is not a Natural number. Let's try out the second element in our 'A' set, which is (3, 3003) x = (3003 + 3) / 2 = 1503, y = (3003 - 1503) / 3 = 500, (1503)^2 - 9*(500)^2 = 2259009 - 2250000 = 9009 (x = 1503, y = 500) are the values that are suitable for 'P9' set. Interesting property: If you combine 9009 and 1 and divide it by n (n = 9) you won't get a Natural number, and the x and y values are not inside 'P9' set whereas you do the same operation with 3003 and 3, you'll get the opposite result: ( 9009 + 1 ) / 9 = 1001.11111 - > not a Natural number, 'x' and 'y' do not belong to 'P9' (3003 + 3 ) / 9 = 334 - Natural number, 'x' and 'y' belong to 'P9' Let's try a different value of 'k' and 'n': k = 16, n = 4. x^2 - 4y^2 = 16; i { 1, 2, 3 ,4} A{ (1, 16), (2, 8), (4, 4) } Let's use that "interesting property" 16+1 / n = 17 / 4 = 4.25 - not a Natural number, 2+8 / n = 10 / 4 = 2.5 - not a Natural number, 4+4 / 4 = 2 - Natural number, x = ( j + i ) / 2 = ( 4 + 4 ) / 2 = 4, y = ( j - x ) / (square root of 'n') = (4-4) / 2 = 0, 4^2 - 4*(0)^2 = 16, (x = 4, y = 0) are inside P4 set. Hope it made some sense, I've added java code inside a text file too. My question wasn't correct in the first place, but I still appreciate your contribution, thank you. equation.txt Edited November 26, 2017 by Displayname Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now