Question

Discrete Mathematics

***Make sure to give proofs in PARAGRAPH form using COMPLETE sentences. Use correct notation and terminology ***

2. Prove that if a, b, c are integers, c divides a + b, and gcd(a, b) = 1, then gcd(a, c) = 1.

Answer 1

let a, b, c ER and clatb 7 a+b=k. c, KER Also o cd ca, b) = 1 = 7 PIGER S. ap+bq = 1 We have ap+bq = 1 - ap + (kic - al q = 1 = a CP-1) + koc.q=1 = am cn=1 where m=pt n= kq i gcd ca, c) = 1

LET a,b and c be the integrs and c divides a+b. Thus a+b is a multiple of c.Therefore, a+b=kc ,where k is an integer.We also have gcd(a,b)=1. By using definition of gcd, there exists two intergs p and q such that ap+bq=1. Now using ap+bq=1 and a+b=kc we can say that a(p-1) +kqc=1. Letting p-1 =m and kq=n we have am+cn=1. This shows that gcd(a,c)=1.