gcd($x, pq$) = 1 $\Rightarrow$ gcd($x, p$) = 1 and gcd($x, q$) = 1

Question

I'm doing a little research on elementary number theory, and found this question online. I thought it should be easy for me to prove, but that seemed not to be true:

Let $p, q$ be primes.
Prove: gcd($x, pq$) = 1 $\Rightarrow$ gcd($x, p$) = 1 and gcd($x, q$) = 1

I tried rewriting this to: $1 = ax + bpq$ for some integers $a, b$ (using the extended euclidean algorithm) but I got stuck there, so I think that isn't the right approach.

Answer 1

Since $\operatorname{gcd}(x, pq)=1$, we have $ax+bpq=1$ for some $a, b\in \mathbb{Z}$. But then $ax+(bp) q=1$ gives $\operatorname{gcd}(x, q)=1$ whereas $ax+(bq) p=1$ gives $\operatorname{gcd}(x, p)=1$.

Answer 2

You have to fix the reasoning.

Because $gcd(x,pq) = 1$, there exist $a, b$ with $ax + bpq = 1$.

Then also $ax + (bp)q = ax + (bq)p = 1$ so you have numbers to prove the RHS.

(And it does not have to be $1$, it can be any $gcd$)

Answer 3

Because gcd(x,pq)=1gcd(x,pq)=1, there exist a,ba,b with ax+bpq=1ax+bpq=1.

Then also ax+(bp)q=ax+(bq)p=1ax+(bp)q=ax+(bq)p=1 so you have numbers to prove the RHS.