Proof: Combining coprime numbers Let $N=pq$ for $p,q$ prime.
If $\gcd(a,N)=1$ and $\gcd(b,N)=1$ is it true that $\gcd(ab,N)=1$
That is to say that $a$ and $N$ being coprime, and $b$ and $N$ being coprime, implies that $ab$ and $N$ are coprime.
Could someone give me a simple proof either way please?
 A: Assume by contradiction that $\gcd(ab, N)\neq 1$. Then there exists some prime $p_0$ such that 
$$p_0|ab,\ p_0|N$$
However, by Euclid's Lemma, we then have $p_0|a$ or $p_0|b$. That means either
$$p_0|\gcd(a,N)$$
or $$p_0|\gcd(b,N)$$
so one of $\gcd(a,N),\gcd(b,N)$ is not $1$. Thus, we have a contradiction, so our initial assumption is not valid, finishing the proof.
A: By Bezout's Lemma (see this one), 
$$ax+Ny=1$$
$$bw+Nz=1$$
for some integers $x,y,z,w$. Simplifying we get
$$ab(xw)+N(ybw+axz+Nyz)=1$$ 
where $xw$ and $ybw+axz+Nyz$ are also integers. This implies that gcd$(ab,N)=1$.
A: $gcd(a,N)=1$ means that $a$ and $N$ have no factor in common (apart from 1). Ditto for $b$. In particular they have no prime factors in common.
Any prime factor of $ab$ is either a factor of $a$ or a factor of $b$ (or both). We know that $N$ has none of these, hence $gcd(ab,N)=1$
A: Hint $\ $ By the uniquness of prime factorizations, the prime factorization of $ab$ is that obtained by concatenating the unique prime factorizations of $\,a\,$ and $\,b.\,$ The hypotheses imply that the primes $\,p,q\,$ do not occur in either so they do not occur in their concatenation.
