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

 Number Theory Number Theory Math Forum

 September 10th, 2017, 12:12 PM #1 Newbie   Joined: Sep 2017 From: San Diego Posts: 8 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.
 September 10th, 2017, 01:27 PM #2 Global Moderator   Joined: Dec 2006 Posts: 19,177 Thanks: 1644 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

 Tags gcda, gcdb

 Thread Tools Display Modes Linear Mode

 Contact - Home - Forums - Cryptocurrency Forum - Top