GCD prob: a,b,c,d natural, ad=bc; what is {a+b,c+d}?
- Thread starter masi
- Start date
pka
Elite Member
- Joined
- Jan 29, 2005
- Messages
- 11,976
Re: A GCD problem
I suspect that it is part of a larger problem, what is called a scenario problem.
Is it a sub problem of a larger problem?
What is GCD? Maybe it would help to know that.
As that stands, it does appear to have a clear-cut answer.masi said:
I suspect that it is part of a larger problem, what is called a scenario problem.
Is it a sub problem of a larger problem?
What is GCD? Maybe it would help to know that.
Thanks for the reply,
GCD is of course greatest common divisor. \(\displaystyle (x,y)\) denotes the gcd of x and y. It is not a subproblem, just a curious endeavor (In Apostol's "Introduction to Analytic Number Theory" he asks a somewhat similar, but much simpler question where \(\displaystyle ad - bc = \pm 1\). I thought this would be a fun challenge. The truth is, I've resigned to just trying to get decent lower bounds on \(\displaystyle (a+b,c+d)\), but I thought maybe I'd throw the harder problem out there to see what someone could do with it. The problem seemed innocent enough; I a probably being brainless for a bit, because any sort of real bound has completely escaped me.
GCD is of course greatest common divisor. \(\displaystyle (x,y)\) denotes the gcd of x and y. It is not a subproblem, just a curious endeavor (In Apostol's "Introduction to Analytic Number Theory" he asks a somewhat similar, but much simpler question where \(\displaystyle ad - bc = \pm 1\). I thought this would be a fun challenge. The truth is, I've resigned to just trying to get decent lower bounds on \(\displaystyle (a+b,c+d)\), but I thought maybe I'd throw the harder problem out there to see what someone could do with it. The problem seemed innocent enough; I a probably being brainless for a bit, because any sort of real bound has completely escaped me.
joeyjoejoe
New member
- Joined
- Apr 24, 2008
- Messages
- 3
Are there any restrictions as to what values a,b,c,d can take on? Like, is it so that a<b<c<d?
If this were the case, say a=3, b=5, c=6, d=10. Then [a+b,c+d]=min(a+b,c+d). This might work in general. I don't know how you'd go about proving it though.
If you don't have this restriction, the best you might be able to do is to get some bounds.
If a=b=c=d=10, then the answer would be 20.
If a=d=10, b=4, c=25, then the answer would be 7.
Have you tried breaking this into parity cases? Like, if a is odd and d is even, then......
If this were the case, say a=3, b=5, c=6, d=10. Then [a+b,c+d]=min(a+b,c+d). This might work in general. I don't know how you'd go about proving it though.
If you don't have this restriction, the best you might be able to do is to get some bounds.
If a=b=c=d=10, then the answer would be 20.
If a=d=10, b=4, c=25, then the answer would be 7.
Have you tried breaking this into parity cases? Like, if a is odd and d is even, then......
joeyjoejoe said:
Getting that bound is not hard:
\(\displaystyle GCD(x,y)=\frac{x}{LCM(x,y)}y \le |y|\).
The same argument shows it for x. Or one could simply show that z|x implies z<=|x|.
I ran a simulation for all possible values from -9 to 9 for a,b,c,d. It didn't look like a pattern to me, but I could be wrong.