Diophantine equation

[Displayname]

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

[Country Boy]

  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

[Displayname]

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