Show that gcdam 1 and gcdbm 1 if and only if gcdabm 1 Hin

Show that: gcd(a,m) = 1 and gcd(b,m) = 1 if and only if gcd(ab,m) = 1

Hint: the easiest way is to use the fact that if we put d = gcd(a,b), then d is the smallest positive integer that can be written as a linear combination of a and b, i.e.

(i) d = ax+byforsomeintegersxandy,and (ii) d is the smallest positive integer that can be written like that.

Thank you

Solution

For the forward (or ==>) direction I make use of the well-known lemma that the gcd of two integers can be written as an integer linear combination of the two numbers which is true in the i f f setting.

We have: gcd(a, m) = 1 ==> there exists integers r, s such that ar + ms = 1

Similarly: gcd(b, m) = 1 ==> there exists integers t, u such that bt + mu = 1

Therefore (ar + ms)(bt + mu) = (1)(1) =1 ==> arbt + armu + msbt + m^2su = 1

==> ab(rt) + m(aru + sbt + msu) = 1. Let rt = h and aru + sbt + msu = k (both integers)

then abh + mk = 1 therefore gcd(ab, m) = 1.

For the reverse (or <==) direction, if EITHER gcd(a, m) is not 1, then there exists integer r > 1 such that a = hr and m = kr for some integers h and k, OR if gcd(b, m) is not 1, then there exists integer s > 1 such that b = ts and m = us for some integers t and u. Then the product ab = hrts will have either a factor or r > 1 (in case that m = kr) or a factor of s > 1 (in case that m = us) in common with m, which contradicts the assumption that gcd(ab, m) = 1.

The proof is complete.