![[dr. bob]](/dr-bob-sm.gif)
Dr. Bob is Robert Hsiung, MD,
bob@dr-bob.orgShown: posts 1 to 21 of 21. This is the beginning of the thread.
Posted by linkadge on January 11, 2007, at 17:17:02
If you are given that the GCD(a,b)=1, what is the value of GDD(a^2 + b^2,a+b)?
I've been struggling for hours.
Linkadge
Posted by AuntieMel on January 12, 2007, at 11:36:28
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
How fast do you need it? I aced number theory, but it's been quite a few years.
Let me think on it.
Posted by AuntieMel on January 12, 2007, at 11:37:57
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
I know what GCD is, but what is GDD?
Posted by linkadge on January 12, 2007, at 12:46:42
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
Posted by kid47 on January 12, 2007, at 13:18:35
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
Posted by AuntieMel on January 12, 2007, at 14:53:31
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
Well, the answer is 2, but getting there is another matter.
But it makes sense - for a and be to be relatively prime they must be odd and have no other factors in common. so a^2 + b^2 has to be even, and a + b has to be even - and there are no other factors in common. {but the last half of that sentence is what I still need to come up with}
Posted by AuntieMel on January 12, 2007, at 15:12:20
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
they don't have to be both be odd. one can be even.
so a + b can be odd...
back to the drawing board.
Posted by AuntieMel on January 12, 2007, at 16:36:20
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
Well, the answer seems to be 2 if both a and b are odd and 1 otherwise (one odd, one even)
It works when plugging numbers into it.
But I keep wanting the answer to be abs|(a - b)|
(a^2 + b^2) factors into (a + b) * (a - b) so it seems if you divide one by the other the remainder is always a - b
I'll pull my number theory book out of mothballs when I get home.
Posted by linkadge on January 12, 2007, at 16:54:19
In reply to Re: Well, the answer..., posted by AuntieMel on January 12, 2007, at 16:36:20
>(a^2 + b^2) factors into (a + b) * (a - b) so it >seems if you divide one by the other the >remainder is always a - b
Thats what I was thinking at first, but a^2 + b^2 doesn't factor into (a+b)(a-b). a^2 - b^2 (minus) factors into (a+b)(a-b).
>I'll pull my number theory book out of mothballs >when I get home.
Thanks a lot. Though, no worries either way.
Linkadge
Posted by AuntieMel on January 13, 2007, at 13:07:25
In reply to Re: Well, the answer..., posted by linkadge on January 12, 2007, at 16:54:19
Of course you are right with the factoring.
Hey - it's been 20 years!
Posted by linkadge on January 14, 2007, at 13:26:51
In reply to Re: Well, the answer..., posted by AuntieMel on January 13, 2007, at 13:07:25
You're right about the answer though, it is either 1 or 2, but just stuck showing it.
Linkadge
Posted by AuntieMel on January 15, 2007, at 8:28:43
In reply to Re: Well, the answer..., posted by linkadge on January 14, 2007, at 13:26:51
And I can't find my number theory book. There must be some boxes that haven't been unpacked.
I'm going to keep looking, but if you find out the answer let me know.
Posted by AuntieMel on January 15, 2007, at 12:15:27
In reply to Re: Well, the answer..., posted by linkadge on January 14, 2007, at 13:26:51
We know a and b can't both be even (or the gcd would include 2)
so a^2 is odd if a is odd, even otherwise
and b^2 is odd if b is odd, even otherwiseOdd + even = odd (explains the answer of "1")
odd + odd = even (explains the answer of "2")also put - (a^2 + b^2(mod 2)) = (a + b(mod2)) which is either 0 or 1
What I can't show is why there aren't any other, higher numbers that can fit.
Posted by AuntieMel on January 16, 2007, at 9:17:37
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
I found a property:GCD (a + b, b) = GCD (a, b)
So GCD (a^2 + b^2, a + b) = GCD (a^2, a + b).
The only possible cases for a and b are
1) a is odd, b is even
2) a is even, b is odd
3) a and b are both oddIn case 1, the GCD of (a^2, a + b) is 1
case 2, the GCD of (a^2, a + b) is 1 (a + b is odd)
case 3, the GCD of (a^2, a + b) is 2 (a + b is even)
Posted by Dr. Bob on January 17, 2007, at 1:06:50
In reply to Re: Well, the answer..., posted by linkadge on January 12, 2007, at 16:54:19
> GCD (a + b, b) = GCD (a, b)
>
> So GCD (a^2 + b^2, a + b) = GCD (a^2, a + b).I don't know, the first would seem to imply:
GCD (a^2 + a + b, a + b) = GCD (a^2, a + b)
> a^2 + b^2 doesn't factor into (a+b)(a-b).
I think that might be the direction to go, maybe think of it as:
GCD ((a + b)^2 - 2ab, a + b)
Bob
Posted by crazymaisie on January 17, 2007, at 22:40:45
In reply to Re: number theory, posted by Dr. Bob on January 17, 2007, at 1:06:50
sorry, i don't post much, but i do lurk
don't know if this will be of any use
but if you think of a as the product of primes:
p(1)...p(n) and b as the product of primes q(1)..q(m) with no p(i), q(j) equal, then
a^2 + b^2 would be p(1)^2...p(n)^2 + q(1)^2...q(m)^2
where you couldn't factor out any prime cause no p(i) equals any q(j)
similarly, p(1)...p(n) + q(1)...q(m) couldn't be factored either so they should be relatively primei could be completely wrong...it has been a while.
good luck, though!
Posted by Dinah on January 18, 2007, at 2:54:14
In reply to Re: number theory, posted by Dr. Bob on January 17, 2007, at 1:06:50
You ought to be careful.
That's how I fell in love with my now husband - in advanced math.
Posted by karen_kay on January 18, 2007, at 8:25:25
In reply to :-) » Dr. Bob, posted by Dinah on January 18, 2007, at 2:54:14
that's about enough of that dinah.
i don't want to have to fight you over mr. bob, but if you continue 'that' talk, i will be forced to.
watch your step missy! kk's an EXTREMELY jealous type of person.
oh, but there is something attractive about a man who can do math, isn't there?
Posted by Dinah on January 18, 2007, at 9:37:59
In reply to Re: hey! » Dinah, posted by karen_kay on January 18, 2007, at 8:25:25
No worries, my husband can still whisper sweet equations into my ears. AND he can do great impressions of TV characters, in context.
I am well content with my own math guy.
Posted by Klavot on January 20, 2007, at 16:18:58
In reply to Anyone good at number theory?, posted by linkadge on January 11, 2007, at 17:17:02
> If you are given that the GCD(a,b)=1, what is the value of GDD(a^2 + b^2,a+b)?
>
> I've been struggling for hours.
>
> LinkadgeLet p be a prime dividing both a^2 + b^2 and a+b. Then a^2 + b^2 = mp and a+b = np for some integers m,n. Since a^2 + b^2 = (a+b)^2 - 2ab then mp = n^2p^2 - 2ab, i.e. 2ab = (n^2p - m)p.
Thus p = 2 or p divides a or p divides b.Suppose p divides a. Since p divides a+b then p divides b as well, a contradiction because gcd(a,b) = 1. Hence p does not divide a, and likewise p does not divide b either. Hence p = 2.
Thus we have shown that if a prime p divides both a+b and a^2 + b^2 then p=2.
Regarding possible values of a and b, there are two cases to consider.
Case 1: a odd, b odd. Then a+b is even and a^2 + b^2 is even, so gcd(a^2 + b^2,a+b) >= 2. From the above it follows that gcd(a^2 + b^2,a+b) = 2.
Case 2: a odd, b even. Then a+b is odd and a^2 + b^2 is odd. From the above, since the only candidate prime to divide both a+b and a^2 + b^2 is 2, it follows that gcd(a^2 + b^2,a+b) = 1.
Klavot
Posted by AuntieMel on January 22, 2007, at 18:12:08
In reply to Re: Anyone good at number theory? » linkadge, posted by Klavot on January 20, 2007, at 16:18:58
That's what I was trying to get out but couldn't find the words.
Sometimes my language fails me.
This is the end of the thread.
Psycho-Babble Social | Extras | FAQ
Dr. Bob is Robert Hsiung, MD,
bob@dr-bob.org
Script revised: February 4, 2008
URL: http://www.dr-bob.org/cgi-bin/pb/mget.pl
Copyright 2006-17 Robert Hsiung.
Owned and operated by Dr. Bob LLC and not the University of Chicago.