Greatest common divisor problem help

In summary: When is the gcd=1?I think the gcd is 1 iff ab is odd, because then (a+b)/2 is not an integer (and if ab is even, gcd is 2).Is there a better way of proving that gcd=1 iff ab is odd, rather than doing it case by case? (for n=1,2,3,4, …)int main(){cout<<"In summary, the gcd of (a^2+b^2, a+b) where a and b are relatively prime integers is either 1 or 2, depending on whether the power of (a+b) is odd or even. Additionally, the gcd is equal to (a+b) if the power is
  • #1
mafendee
11
0

Homework Statement


Given gcd(a,b)=1, what is the gcd(a^2+b^2, a+b) where ^=square.


Homework Equations





The Attempt at a Solution


gcd(a^2+b^2, a+b) = gcd ( (a+b)^2 -2ab, a+b) which i think, we can reduce to gcd(2ab, a+b). Here is where I stucked. I am not sure how to proceed. Please could anyone help me?
 
Physics news on Phys.org
  • #2
Welcome to PF!

mafendee said:
Given gcd(a,b)=1 …

… we can reduce to gcd(2ab, a+b). Here is where I stucked.

Hi mafendee! Welcome to PF! :smile:

Hint: if p divides 2ab, then either … :wink:
 
  • #3
thank you tiny-tim,

"if p divides 2ab, then either", p|2 and/or p|a (p not divide b)
or p|2 and/or p|b. (p not divide a)
p>1 cannot divide both a,b since (a,b)=1.

so gcd(2ab, a+b)=1. is this correct?
 
  • #4
mafendee said:
thank you tiny-tim,

"if p divides 2ab, then either", p|2 and/or p|a (p not divide b)
or p|2 and/or p|b. (p not divide a)
p>1 cannot divide both a,b since (a,b)=1.

so gcd(2ab, a+b)=1. is this correct?

hmm :frown:

you're not being logical …

why can't it be 2?
 
  • #5
you're right. I had a thinking that a and b should be even and odd which is not divisible by 2. But then it could also be the case where both of them are odds, hence a+b=even which is divisible by 2.

so, the gcd = 2.

is it correct to say that gcd(a^n+b^n, a+b) = n? (i haven't tried to prove this).
 
  • #6
mafendee said:
you're right. I had a thinking that a and b should be even and odd which is not divisible by 2. But then it could also be the case where both of them are odds, hence a+b=even which is divisible by 2.

so, the gcd = 2.

Yes, gcd = 2 if they're both odd, and 1 if one is even …

but can you prove that properly? :wink:
is it correct to say that gcd(a^n+b^n, a+b) = n? (i haven't tried to prove this).

(try using the X2 tag just above the Reply box :wink:)

Well, if n is odd, then a+b divides an + bn anyway.

For n = 4, for example, you would start with gcd(2ab(2a2 + 3ab + 2b2),a+b) …

what happens next? :smile:
 
  • #7
And what if a=7 and b=2 ?

gcd(7,2)=1

gcd(72+22,7+2)=gcd(53,9)=1

Where 2 came from?
 
  • #8
Дьявол said:
And what if a=7 and b=2 ?

gcd(7,2)=1

ah … 2 is even! :wink:
tiny-tim said:
Yes, gcd = 2 if they're both odd, and 1 if one is even …
 
  • #9
tiny-tim said:
Yes, gcd = 2 if they're both odd, and 1 if one is even

Ohh... I missed this one... Sorry...

Regards.

EDIT:

Here is my proof.

Let's say that p and k are integers.

If a is even and b is odd then a=2p and b=2k-1 so that a2+b2= 4p2 + 4k2-4k+1 and a+b = 2p+2k-1. As we can see there isn't number which is divisible by both of the terms.

If a and b are odd then a2+b2=(2k-1)2+(2p-1)2=4k2+4p2-4k-4p+2 and a+b=2p-2k-2, so that both terms are divisible by 2 so that gcd(a2+b2, a+b) = 2 :smile:
 
Last edited:
  • #10
thank you to both of you. i think Дьявол has proved the cases of +a,-b and -a,-b.

"For n = 4, for example, you would start with gcd(2ab(2a2 + 3ab + 2b2),a+b) "

Here is what I have:

Let say p|2ab(2a2 + 3ab + 2b2), this could be the cases where

case1: p|2 or p|a but not b, and p does not divide (2a2 + 3ab + 2b2)
OR
case2: p|2 or p|b but not a, and p does not divide (2a2 + 3ab + 2b2)

clearly in both cases if p|(a+b), this is the cases when p|2. so p=1,2.

If both a,b are odds. let a=2k+1, b=2p+1, then a2=4k2+4k+1, b2=4p2+4p+1, ab=4kp+2(k+p) +1.

2(4kp+2(k+p)+1)(8k2+8p2+14(k+p)+12kp+7) which is divisible by 2, so does a+b, so gcd=2.

If only one is odd, let a=2k+1, b=2p, then a2=4k2+4k+1, b2=4p2, ab=2p(2k+1).

2(2p)(2k+1)(8k2+4p2+2(4k+p)+2kp+2)=8(p)(2k+1)(4k2+2p2+(4k+p)+kp+1) which is divisible by 8, but a+b=2(k+p) +1 is only divisible by 1, so gcd=1.

Am i doing this correctly?
 
  • #11
mafendee, this a = 2k or 2k+1 stuff is really longwinded.

For the original case, if p is prime and p | 2ab, then p = 2 or p| a or p | b, and p can't divide both a and b, so if it divides one of them it can't divide a+b, so gcd = gcd(2,a+b) = 1 or 2.

For the (a+b)4 case, I was expecting you to carry on from gcd(2ab(2a2 + 3ab + 2b2),a+b), and reduce the 2a2 + 3ab + 2b2 even further, until you get something like gcd(2ab,a+b) again.
 
  • #12
tiny-tim, you are right.

from gcd(2ab(2a2 + 3ab + 2b2),a+b), we have
= gcd(2ab(2a+2b)(a+b) -4ab + 3ab),a+b) = gcd(2ab(ab), a+b))

if p|2a2b2 then p|2 or p|a2 (p|a) or p|b2 (p|b) but p does not divide both a and b at the same time so p does not divide a+b. So we have gcd(2, a+b) = 1 or 2.

For odd n, say n=3 we have gcd(a3+b3, a+b) =
gcd ((a+b)(a2+b2-ab), a+b) = a+b. So if n is odd, the gcd = a+b.

What happen if n is even, will the gcd always be 1 or 2? How to prove this, by induction or?
 
  • #13
mafendee said:
… So if n is odd, the gcd = a+b.

Yes. :smile:
What happen if n is even, will the gcd always be 1 or 2? How to prove this, by induction or?

Try expanding (a + b)2n using the binomial coefficents …

so 1 4 6 4 1 for n = 2

1 6 15 20 15 6 1 for n = 3 etc :wink:
 
  • #14
tiny-tim,

for even power, (a + b)2n,

let n=1,
1 2 1
we have gcd(2ab, a+b)
here gcd=1/2

let n=2,
1 4 6 4 1
we have gcd(2ab(2a2+3ab+2b2), a+b)
here gcd=1/2

let n=3,
1 6 15 20 15 6 1
we have gcd(ab(6a4+15a3b+20a2b2+15ab3+6b4), a+b)
here gcd=1

let n=4,
1 8 28 56 70 56 28 8 1
after taking 1 out after reduction, we can factorise 2 out. So i assume the gcd here is 1/2.

But then how to proof that when is the gcd=1 and when the gcd=1/2?
 
  • #15
(just got up :zzz:)
mafendee said:
let n=3,
1 6 15 20 15 6 1
we have gcd(ab(6a4+15a3b+20a2b2+15ab3+6b4), a+b)
here gcd=1

No, 6a4+15a3b+20a2b2+15ab3+6b4

= 6a4+(6+9)a3b+(9+2+9)a2b2+(6+9)ab3+6b4

= 2a2b2 + multiple of (a+b) …

and you should be able to prove that it will always be 2an-1bn-1 :smile:

(i expect there's a better way of proving it, but this is the most immediately obvious one :redface:)

EDIT: ah, I see the pattern now …

it's 6 - 15 + 20 - 15 + 6

(and n = 2 was -4 + 6 - 4) …

can you see what the general pattern is, and why it must always add to 2? :wink:

(hint: consider (a - b)2n)​
 
Last edited:
  • #16
here we go again,

for even power, (a + b)2n,

let n=1, we have (a + b)2
1 2 1
we have gcd(2ab, a+b)
here gcd=1/2

let n=2,
1 4 6 4 1
we have gcd(2ab(2a2+3ab+2b2), a+b) = gcd (2ab((2a+2b)(a+b) -ab), a+b) = gcd (2a2b2, a+b)
here gcd=1/2

let n=3,
1 6 15 20 15 6 1
we have
=gcd(ab(6a4+15a3b+20a2b2+15ab3+6b4), a+b)
=gcd(ab((6a2+6b2)(a2+b2)-12a2b2+15a3b+20a2b2+15ab3), a+b)
=gcd(ab(((6a+6b)(a+b)-12ab)((a+b)(a+b)-2ab)+15a3b+8a2b2+15ab3), a+b)
=gcd(ab(24a2b2+15a3b+8a2b2+15ab3)), a+b)
= gcd(a2b2(15a2+32ab+15b2), a+b)
= gcd(a2b2((15a+15b)(a+b)-30ab+32ab), a+b)
= gcd(a2b2(2ab), a+b)
= gcd(2a3b3, a+b)

here gcd=1/2

but what I've got here is the gcd is of the form (2anbn, a+b) different from what you pointed out (2an-1bn-1, a+b). am i missing something here?

The '2' that we managed to factor out after lengthy algebra there goes parallel to what you wrote on your 'edit' part. When we "sum" up the term, it will end up with 2. (6 - 15 + 20 - 15 + 6 = 2, -4 + 6 - 4 = 2 and so on).
 
Last edited:
  • #17
tiny-tim,

was my answer in previous post correct?
 
  • #18
mafendee said:
tiny-tim,

was my answer in previous post correct?

Hi mafendee! :smile:
Sorry … I somehow missed replying to this thread. :redface:

Yes, it's correct, but a little long-winded …

you get more marks in the exam if you can make the proofs shorter, and so that they clearly work for any n. :wink:
mafendee said:
but what I've got here is the gcd is of the form (2anbn, a+b) different from what you pointed out (2an-1bn-1, a+b). am i missing something here?

No, I just forgot what "n" was. :smile:
The '2' that we managed to factor out after lengthy algebra there goes parallel to what you wrote on your 'edit' part. When we "sum" up the term, it will end up with 2. (6 - 15 + 20 - 15 + 6 = 2, -4 + 6 - 4 = 2 and so on).

Yup … and can you do a simple proof why that works for any n?
 
  • #19
tiny-tim,

i will try to work on that simple proof you said. thank you.
 
  • #20
Hi mafendee! :smile:

In case you haven't got it yet, here's a hint:

expand (1 - 1)n :wink:
 

1. What is the greatest common divisor (GCD)?

The greatest common divisor, also known as the greatest common factor, is the largest positive integer that divides two or more numbers without any remainder.

2. How do you find the GCD of two numbers?

There are multiple methods for finding the GCD of two numbers, including using prime factorization, the Euclidean algorithm, or a GCD calculator. The most efficient method is using the Euclidean algorithm, which involves repeatedly dividing the larger number by the smaller number until the remainder is 0. The last non-zero remainder is the GCD.

3. What is the significance of the GCD in mathematics?

The GCD is an important concept in mathematics because it is used in many mathematical operations, such as simplifying fractions, finding common denominators, and solving equations involving fractions.

4. Can the GCD of two numbers be 1?

Yes, the GCD of two numbers can be 1. This means that the two numbers are relatively prime, or have no common factors other than 1.

5. How is the GCD related to the least common multiple (LCM)?

The GCD and LCM are related through the fundamental theorem of arithmetic, which states that every positive integer can be uniquely expressed as a product of prime numbers. The GCD and LCM of two numbers can be found using the same prime factors, with the GCD using the smallest exponents and the LCM using the largest exponents.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
921
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
875
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
855
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Back
Top