Help me with this equations please!
Moderators: gmalivuk, Moderators General, Prelates
Help me with this equations please!
Hello all, I've been working on this equation off and on for 3 years now and am now not any closer to solving it than I was 3 years ago. It is as follows:
(a^2 + b) / (a + b^2) = n
a > b > 1 and a and b are both integers. Find the smallest pair of a and b for n = 202.
I tired solving it algebraically with no luck. I wrote a simple program to increment b starting at 2 and going up and then checking if a is an integer for any given value of b, but the program just runs forever and never quits. I tested the program out for other values of n and was able to come up with answers for almost all of them from n = 2 to 300, but try as I might I can't come up with an answer for n =202. Obviously the integers are going to be pretty large and there has to be a way to limit the search so I don't have to check each integer incrementally but I can't come up with one... Maybe someone can give me some ideas?
(a^2 + b) / (a + b^2) = n
a > b > 1 and a and b are both integers. Find the smallest pair of a and b for n = 202.
I tired solving it algebraically with no luck. I wrote a simple program to increment b starting at 2 and going up and then checking if a is an integer for any given value of b, but the program just runs forever and never quits. I tested the program out for other values of n and was able to come up with answers for almost all of them from n = 2 to 300, but try as I might I can't come up with an answer for n =202. Obviously the integers are going to be pretty large and there has to be a way to limit the search so I don't have to check each integer incrementally but I can't come up with one... Maybe someone can give me some ideas?
Re: Help me with this equations please!
This narrows things down a little:
If a and b satisfy the given equation, then (rearranging) we have a^2 + b = 202(a + b^2). Let's think about the remainder on each side on division by 4.
The remainder of a^2 + b divided by 4 depends on the remainder of a divided by 4 and the remainder of b divided by 4. Let r by the remainder of a divided by 4 and let s be the remainder of b divided by 4. We can now compute the following table:
For example, if r = 1 and s = 3, that means a = 4j + 1 and b = 4k + 3 (for some integers j and k), so a^2 + b = (4j + 1)^2 + 4k + 3 = 16j^2 + 8j + 1 + 4k + 3 = 4*(4j^2 + 2j + k + 1), so a^2 + b is divisible by 4 and the remainder is 0. This gives the second entry in the last row of the table. The rest are computed similarly.
The remainder of 202(a^2 + b) divided by 4 (the right side of the equation) depends only on whether a and b are even or odd.
If a and b are odd, then a^2 and b are odd, so (a^2 + b) is even, so 202(a^2 + b) is divisible by 4, and we get remainder 0.
If a and b are even, then a^2 and b are even, so (a^2 + b) is even, so again, we get remainder 0.
If a is odd and b is even, then a^2 is odd and b is even, so (a^2 + b) is odd, so 202(a^2 + b) has remainder 2 (when divided by 4).
If a is even and b is odd, then a^2 is even and b is odd, so (a^2 + b) is odd, so again, we get remainder 2.
Now we need the right and left sides of the equation to be equal, so in particular they must have the same remainder when divided by 4. If you compare the table for the left side of the equation with the information about the right side, you see that there are only two possibilites:
(1) b is divisible by 4, and a is even
(2) b has remainder 3 when divided by 4, and a is odd
Perhaps the solution space could be further reduced by thinking about other moduli besides 4. I'll think about it later if I get a chance. This essentially reduces the number of pairs to check by a factor of 4, though.
If a and b satisfy the given equation, then (rearranging) we have a^2 + b = 202(a + b^2). Let's think about the remainder on each side on division by 4.
The remainder of a^2 + b divided by 4 depends on the remainder of a divided by 4 and the remainder of b divided by 4. Let r by the remainder of a divided by 4 and let s be the remainder of b divided by 4. We can now compute the following table:
Code: Select all
r: 0 1 2 3
s: 0 0 1 0 1
1 1 2 1 2
2 2 3 2 3
3 3 0 3 0
For example, if r = 1 and s = 3, that means a = 4j + 1 and b = 4k + 3 (for some integers j and k), so a^2 + b = (4j + 1)^2 + 4k + 3 = 16j^2 + 8j + 1 + 4k + 3 = 4*(4j^2 + 2j + k + 1), so a^2 + b is divisible by 4 and the remainder is 0. This gives the second entry in the last row of the table. The rest are computed similarly.
The remainder of 202(a^2 + b) divided by 4 (the right side of the equation) depends only on whether a and b are even or odd.
If a and b are odd, then a^2 and b are odd, so (a^2 + b) is even, so 202(a^2 + b) is divisible by 4, and we get remainder 0.
If a and b are even, then a^2 and b are even, so (a^2 + b) is even, so again, we get remainder 0.
If a is odd and b is even, then a^2 is odd and b is even, so (a^2 + b) is odd, so 202(a^2 + b) has remainder 2 (when divided by 4).
If a is even and b is odd, then a^2 is even and b is odd, so (a^2 + b) is odd, so again, we get remainder 2.
Now we need the right and left sides of the equation to be equal, so in particular they must have the same remainder when divided by 4. If you compare the table for the left side of the equation with the information about the right side, you see that there are only two possibilites:
(1) b is divisible by 4, and a is even
(2) b has remainder 3 when divided by 4, and a is odd
Perhaps the solution space could be further reduced by thinking about other moduli besides 4. I'll think about it later if I get a chance. This essentially reduces the number of pairs to check by a factor of 4, though.
Xenomortis wrote:O(n^{2}) takes on new meaning when trying to find pairs of socks in the morning.

 Posts: 36
 Joined: Wed Sep 24, 2014 5:01 pm UTC
Re: Help me with this equations please!
This problem space reduces to "find B where sqrt(202B^2  B + 10201) is an integer" (then A is simply the resulting integer plus 101), and from there the last digits of perfect squares allow us to rule out any B that ends in 1, 2, 6, or 7. Additionally, ending digits of 0, 3, 4, and 8 must be accompanied by an even tens digit, while 5 and 9 must have an odd tens digit in front of them.
There are definitely no such B <= 20000, which rules out A values up to about 284,000.
There are definitely no such B <= 20000, which rules out A values up to about 284,000.
Re: Help me with this equations please!
Have you tried putting (a^2 + b) / (a + b^2) = 202 into Wolfram Alpha?
 Xenomortis
 Not actually a special flower.
 Posts: 1448
 Joined: Thu Oct 11, 2012 8:47 am UTC
Re: Help me with this equations please!
It tries, bless it.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Help me with this equations please!
I thought I might let gcd(a, b) = d and a = Ad, and b = Bd. We then get Ad+B = 202Bd + 202A. Now, A, B and d are all relatively prime, so we have
202 A = B (mod d)
202 d = 1 (mod A)
d = 202 (mod B)
Ad + B = 0 (mod 202)
So, this seems at least a little profitable... but still hard to see the way forward.
202 A = B (mod d)
202 d = 1 (mod A)
d = 202 (mod B)
Ad + B = 0 (mod 202)
So, this seems at least a little profitable... but still hard to see the way forward.
Last edited by jestingrabbit on Fri Nov 14, 2014 9:06 pm UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Help me with this equations please!
The smallest solution is:
a=1993602325, b=140269363
This is followed by:
a=2293775132, b=161389448
There are no other solutions with b<213682610. At that point my computer program suffered from integer overflow.
I haven't found a good algebraic solution method, but have found a parameterization for all rational solutions:
a = (k + 202^2) / (202  k^2)
b = (202k + 1) / (202  k^2)
where k is any rational number.
If you write k=r/s, with r and s coprime, then you get:
a = s(r + s*202^2) / (202s^2  r^2)
b = s(202r + s) / (202s^2  r^2)
I don't see how you can determine for which values of r and s you get integer values for a and b.
a=1993602325, b=140269363
This is followed by:
a=2293775132, b=161389448
There are no other solutions with b<213682610. At that point my computer program suffered from integer overflow.
I haven't found a good algebraic solution method, but have found a parameterization for all rational solutions:
a = (k + 202^2) / (202  k^2)
b = (202k + 1) / (202  k^2)
where k is any rational number.
If you write k=r/s, with r and s coprime, then you get:
a = s(r + s*202^2) / (202s^2  r^2)
b = s(202r + s) / (202s^2  r^2)
I don't see how you can determine for which values of r and s you get integer values for a and b.
Re: Help me with this equations please!
Thank you for all the input guys. I knew the numbers would be big and if I let my program run for a day or two it would eventually come up with the answer, but I wasn't willing to wait that long, that's why I was looking for some constraints. At least now that I know the answer I won't be losing sleep at night! Jaap must have access to a supercomputer... Thanks again.
Re: Help me with this equations please!
Amorydai wrote:Jaap must have access to a supercomputer...
No, just an ordinary laptop with an i5 processor. The Java program I used takes only 7.7 seconds to test all values of b up to 213682610. Here is my code:
Code: Select all
//(a101)^2 = 202 b^2  b + 101^2
public class Test {
public static void main(String[] args) {
long time = System.currentTimeMillis();
long b = 1;
while(true){
long q = (202*b1)*b+10201;
if( q<0) break;
long sq = (long)(Math.sqrt(q+0.5));
if( sq*sq==q ){
System.out.println("b="+b+" a="+(sq+101));
}
b++;
}
System.out.println(b);
time = System.currentTimeMillis()  time;
System.out.println((time/1000.)+" seconds elapsed.");
}
}
 eta oin shrdlu
 Posts: 451
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: Help me with this equations please!
jaap wrote:I don't see how you can determine for which values of r and s you get integer values for a and b.
One way to parametrize the integer solutions is to convert the equation to Pelllike form,
R^{2}  n S^{2} = (2nb1)^{2}  n (2an)^{2} = 1  n^{3} = 8242407 .
Given a solution (R_{0},S_{0}) in integers to the above equation, along with a solution (u,v) to the corresponding Pell equation
u^{2}  n v^{2} = 1 ,
you can generate an infinite family of solutions (R_{k},S_{k}) to the above equation, by expanding
R_{k} + S_{k}*sqrt(n) = (R_{0}+S_{0}*sqrt(n)) (u + v*sqrt(n))^{k} .
(This can be written as a linear firstorder recursion for (R_{k},S_{k}).) If (u,v) are chosen correctly then all integer solutions (R,S) are found as a union of some number of these infinite families; u/v is always a convergent in the continuedfraction expansion for sqrt(n). For n=202, we can take (u,v)=(19731763,1388322).
Of course not all of these (R_{k},S_{k}) will give integer (a_{k},b_{k})=( (S_{k}+n)/2, (R_{k}+1)/(2n) ). But the transformation from (R_{k},S_{k}) to (a,b) is linear, so if there is a solution then there are infinitely many, occurring periodically in the (R_{k},S_{k}) sequence.
One obvious solution (R_{0},S_{0}) is just (1,n). This doesn't give integer b, but the next few elements in this family are
(R_{1},S_{1}) = (56668822651,3987204448)
(R_{2},S_{2}) = (2236351556077127425,157349146400963446)
(R_{3},S_{3}) = (88254317778390119472977899),6209552130072223389066148
The k=1 case gives the minimal solution
(a,b) = (1993602325,140269363) .
k=2 again gives a nonintegral b; k=3 gives a larger solution
(a,b) = (3104776065036111694533175,218451281629678513546975) .
We can get another family of solutions by noticing that 1n^{3}=8242407=9(915823). We can factor the square 3^{2} into R and S and then look for a solution (R',S') to (R')^{2}  n (S')^{2} = 915823. Finding (R',S')=(135,68) we then multiply these by 3 to get another family based on (R,S)=(405,204). The first two solutions (a,b) from this family are
(a,b) = (2293775132,161389448)
(a,b) = (3572256154759519487778374,251343065963647140060824) .
Re: Help me with this equations please!
This is really interesting. Does the equation (a^2+b)/(a+b^2) = n have a name that anyone's aware of? Does the equation have infinitely many solutions for all n? Did the OP get the question from a textbook or paper or anything, or just from playing around?
Re: Help me with this equations please!
skullturf wrote:Did the OP get the question from a textbook or paper or anything, or just from playing around?
Found it on Project Eureka, problem 815. Don't really know anything else about it. Problem states that there are integer solutions for all n>1.
Thanks for your breakdown eta oin shrdlu, that's a lot more math than I'm used to.
Re: Help me with this equations please!
I was playing around with this a bit more, and I think I see how to prove that there are solutions for all n. Furthermore, using ideas suggested by eta oin shrdlu, I think it's possible to prove that there are infinitely many solutions when n is a nonsquare (this relies on knowing certain things about Pell's equation) but only finitely many solutions when n is a square.
I didn't write out all my steps in detail so it's possible I made a slipup, but I think that's right.
EDITED TO ADD MORE:
If n is an even square, say n=(2m)^2, then a nontrivial solution is given by
a = 8m^5 + 2m^2
b = 4m^4
Verification: a^2 = 64m^10 + 32m^7 + 4m^4
a^2 + b = 64m^10 + 32m^7 + 8m^4
a + b^2 = 16m^8 + 8m^5 + 2m^2
(a^2+b)/(a+b^2) = 4m^2
However, I'm not quite sure how to prove there is always at least one nontrivial solution when n is an odd square.
When n=9, a nontrivial solution is (a,b)=(20,5).
Verification: 20^2+5 = 400 + 5 = 405
20+5^2 = 20 + 25 = 45
405/45 = 9
When n=25, a nontrivial solution is (a,b)=(143,26).
Verification: 143^2+26 = 20475, 143+26^2 = 819, 20475/819 = 25
When n=49, a nontrivial solution is (a,b)=(550,75).
Verification: 550^2+75 = 302575, 550+75^2 = 6175, 302575/6175 = 49
This might be all the nontrivial solutions, or close to all the nontrivial solutions, for the above three values of n. But I don't see how the pairs (20,5), (143,26), (550,75) fit into any obvious general pattern.
EDITED YET AGAIN to point out that (a,b)=(36,4) is another nontrivial solution when n=25.
Also, (a,b)=(101,5) and (a,b)=(1517,164) are two nontrivial solutions when n=81.
I didn't write out all my steps in detail so it's possible I made a slipup, but I think that's right.
EDITED TO ADD MORE:
If n is an even square, say n=(2m)^2, then a nontrivial solution is given by
a = 8m^5 + 2m^2
b = 4m^4
Verification: a^2 = 64m^10 + 32m^7 + 4m^4
a^2 + b = 64m^10 + 32m^7 + 8m^4
a + b^2 = 16m^8 + 8m^5 + 2m^2
(a^2+b)/(a+b^2) = 4m^2
However, I'm not quite sure how to prove there is always at least one nontrivial solution when n is an odd square.
When n=9, a nontrivial solution is (a,b)=(20,5).
Verification: 20^2+5 = 400 + 5 = 405
20+5^2 = 20 + 25 = 45
405/45 = 9
When n=25, a nontrivial solution is (a,b)=(143,26).
Verification: 143^2+26 = 20475, 143+26^2 = 819, 20475/819 = 25
When n=49, a nontrivial solution is (a,b)=(550,75).
Verification: 550^2+75 = 302575, 550+75^2 = 6175, 302575/6175 = 49
This might be all the nontrivial solutions, or close to all the nontrivial solutions, for the above three values of n. But I don't see how the pairs (20,5), (143,26), (550,75) fit into any obvious general pattern.
EDITED YET AGAIN to point out that (a,b)=(36,4) is another nontrivial solution when n=25.
Also, (a,b)=(101,5) and (a,b)=(1517,164) are two nontrivial solutions when n=81.
Re: Help me with this equations please!
For n=m^{2}, there are at most n/2 different solutions, each with a different value of amb between n/2 and n. If n is an odd square, the largest such solution has amb=(n+1)/2, and is given by:
a=(m^{2}+1)(m^{2}m+2)/4
b=(m^{2}+1)(m1)/4
a=(m^{2}+1)(m^{2}m+2)/4
b=(m^{2}+1)(m1)/4
Who is online
Users browsing this forum: No registered users and 5 guests