Question

A,b,c,d are integers and GCD(a,b)=1. if c divides a and d divides b, prove that GCD(c,d) = 1.

Answer 1

One proof can be as follows:

Explanation:

We have that
`g.c.d(a,b)=1` and
`a=cp, b=dq` for some integers
`p, q`, since
`c` divides
`a` and
`d` divides
`b`. By the Bezout identity two numbers
`a,b` are relatively primes if and only if there exists integers
`x,y` such that

`ax+by=1`

Then, we can write

`1=ax+by=(cp)x+(dq)y=c(px)+d(qy)=cx'+dy'`

Then
`c` and
`d` are relatively primes, that is to say,

`g.c.d(c,d)=1`