Fun with maths: 2010/047) prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1 using Bézout's identity

Saturday, October 2, 2010

2010/047) prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1 using Bézout's identity

as GCD(a,b)= 1

so 1 = ax + by

so c = acx + bcy ...1

now GCD(a,c) = 1

so 1 = ma+ nc = ma + n(acx+ bcy) ftom 1
= a ( m + ncx) + bc(ny)

as we can put 1 as linear combination of a and bc so Gcd(a,bc) = 1

3 comments:

Anonymous said...: Awesome! Could not remember that trick of multiplying c! Gosh I need to practice this more. I used to be good at nbr theory.; February 2, 2011 at 5:35 PM
Unknown said...: It doesn't make sense. Gcd (a, b)=d means d has a linear combination of a and b s.t. ax+by, but ax+by does NOT imply that d=Gcd (a, b); February 7, 2014 at 2:45 PM
kaliprasad said...: but ax+by does NOT imply that d=Gcd (a, b)
but because 1 ls linear comtbination of multiple of a, and bc so 1 is multiple of GCD hence GCD is 1.; February 17, 2014 at 9:50 PM