
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 10th, 2017, 12:12 PM  #1 
Newbie 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 2a and 2b. 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. 
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. 