Proof involving relatively prime numbers

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

• Write the Bezout identities for $gcd(a, m) = 1$ and $gcd(b, m) = 1$ and multiply them. – Lazward Mar 6 '18 at 2:08
• If $p$ is a prime and if $p|ab$ then either $p|a$ or $p|b$ so if $p|ab$ and $p|m$ then either $p|a$ and $m$, or $p|b$ and $m$. – fleablood Mar 6 '18 at 2:11

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.

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

• "If $p|a$ and $m$.."? Should that be "$p|a$ and $p|m$"? – ilkkachu Mar 6 '18 at 9:11
• Should it? I read "If p|a and m..."" as "if p divides a and m..." – fleablood Mar 6 '18 at 17:09

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

• Of course, one can easily say this is essentially Bezout's identity, but it is often easier to think of it in terms of multiplicative inverse in the ring of residues modulo some integer than to carry around all the unnecessary information obtained from Bezout's identity. – user21820 Mar 6 '18 at 7:56

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