Proof: Combining coprime numbers

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

$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$

Answer 4

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.