My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Thanks Tree1Thanks
  • 1 Post By skipjack
LinkBack Thread Tools Display Modes
September 10th, 2017, 12:12 PM   #1
Joined: Sep 2017
From: San Diego

Posts: 5
Thanks: 0

If gcd(a,4)=2 and gcd(b,4)=2, then gcd(a+b,4)= 4

Is this proof right?

Prove: If gcd(a,4)=2 and gcd(b,4)=2, then gcd(a+b,4)= 4

Suppose the

gcd(a+b,4)= d.

Since the gcd(a,4)=2 and gcd(b,4)=2, it follows that 2|a and 2|b. Then there exist integers m and n so that,

a = 2m and b = 2n.

By substituting a and b into the left hand side of gcd(a+b,4)= d, we get

gcd(2m+2n,4)= gcd(2(m+n),4)

However m and n are each odd because if they were even, a and b would also be divisible by 4, then the gcd(a,4) and gcd(b,4) would not equal 2. Thus m+n is even, because the sum of two odd integers is even. Hence there exits an integer r such that

m+n = 2r.
Now by substituting in 2r in to gcd(2(m+n),4) we get

gcd(2(2r),4) = gcd(4r,4).

So we get,

gcd(4r , 4) = d.

It follows that d =4 because the biggest number that divides 4 and a multiple of 4 is 4. So, the gcd(a+b,4)= 4, which is what we needed to show.

Thank you for all the help and comments.

Last edited by skipjack; September 10th, 2017 at 01:29 PM.
Shadow89 is offline  
September 10th, 2017, 01:27 PM   #2
Global Moderator
Joined: Dec 2006

Posts: 17,919
Thanks: 1385

It's correct.

Alternatively, as a and b are divisible by 2, but not by 4,
a = 4p + 2 and b = 4q + 2 (where p and q are integers).

Hence a + b = 4p + 4q + 4, which is divisible by 4, and so gcd(a + b, 4) = 4.
Thanks from Shadow89
skipjack is offline  

  My Math Forum > College Math Forum > Number Theory

gcda, gcdb

Thread Tools
Display Modes

Copyright © 2017 My Math Forum. All rights reserved.