Proof involving relatively prime numbers

Question

Let $a, b \in \mathbb{Z}$ and $m \in \mathbb{N}.$ Show that if $a$ and $b$ are both relatively prime to $m$, then $ab$ is relatively prime to $m$

WHAT I KNOW

Since $a$ and $b$ are both relatively prime to $m$, this means $gcd (a,m) = 1$ and $gcd(b,m) = 1.$ Perhaps Bezout's Identity would be useful to bring up into the proof, but do not know how to implement that into my explanation. So what can we say about the product $ab$? How do I show that it is relatively prime to $m$?

Answer 1

Assume otherwise that $\text{gcd}(ab,m) = n >1$. Then $n \mid ab, n \mid m$. Let $k$ be a prime divisor of $n$, then $k \mid ab, k \mid m$. Thus $k\mid a$ or $k\mid b$. So $k \mid \text{gcd}(a,m)=1$ or $k \mid \text{gcd}(b,m)=1$. Thus $k = 1$, contradicting it being a prime. The claim follows.

Answer 2

Easieast way: Unique factorization Theorem.

If you want to use Bezout's identity: there exists $x,y\in\mathbb{Z}$ such that $ax+my=1$, since $\text{gcd}(a,m)=1$. Similarly, there exists $u,v\in\mathbb{Z}$ such that $bu+mv=1$.

Multiply the first equation by $b$. You obtain $abx+m(yb)=b$. If you multiply this new equation by $u$ and sum $mv$, you obtain $$ ab(xu)+m(ybu)+mv=bu+vy=1. $$ In particular, call $x'=xu$ and $y'=ybu$, both integers. Then $$ abx'+my'=1, $$ and this implies $\text{gcd}(ab,m)=1$.

Answer 3

1) Let $p$ be prime and let $p|ab$ and $p|m$ then either $p|a$ or $p|b$. If $p$ divides both $a$ and $m$ then $p$ is a common factor of $a$ and $m$. But that's impossible. And if $p$ divides bothe $b$ and $m$ then $p$ is a common factor of $b$ and $m$. But that's impossible.

So there is not prime factor that $ab$ and $m$ have in common.

2) There exist, by Bezout, some $j,k,l,n$ so that $aj + mk = 1$ and and $bl + mn = 1$ so

$(aj + mk)(bl + mn) = ab*jl + m(kbl + naj + mnk) = 1$

So by Bezout $\gcd(ab,m) = 1$.

Answer 4

In my opinion, at least for integers the most intuitive way of understanding this is that coprime implies multiplicative inverse. Specifically:

Take any non-zero integers $m,n$. Then $\gcd(m,n)=1$ iff $mm' \equiv 1 \pmod{n}$ for some integer $m'$. Symmetrically also $\gcd(m,n)=1$ iff $nn' \equiv 1 \pmod{m}$ for some integer $n'$.

This viewpoint immediately solves many such problems in a quick and painless way. In your case:

---

Let $a',b'$ be positive integers such that $aa' \equiv bb' \equiv 1 \pmod{n}$.

Then $(ab)(a'b') \equiv (aa')(bb') \equiv 1 \pmod{n}$.

Therefore $\gcd(ab,n) = 1$.